Apa artinya membantah tesis Gereja-Turing?

83

Maaf untuk judul yang menarik. Saya ingin mengerti, apa yang harus dilakukan seseorang untuk menyangkal tesis Gereja-Turing? Di suatu tempat saya membaca secara matematis tidak mungkin untuk melakukannya! Mengapa?

Turing, Rosser dll menggunakan istilah yang berbeda untuk membedakan antara: "apa yang dapat dihitung" dan "apa yang dapat dihitung dengan mesin Turing".

Definisi Turing 1939 mengenai hal ini adalah: "Kami akan menggunakan ungkapan" fungsi yang dapat dihitung "untuk berarti fungsi yang dihitung oleh mesin, dan kami membiarkan" dihitung secara efektif "merujuk pada ide intuitif tanpa identifikasi khusus dengan salah satu dari definisi ini".

Jadi, tesis Church-Turing dapat dinyatakan sebagai berikut: Setiap fungsi yang dihitung secara efektif adalah fungsi yang dapat dihitung.

Jadi sekali lagi, bagaimana buktinya terlihat jika seseorang membantah dugaan ini?

computability proofs hypercomputation András Salamon
sumber
1
Periksa lampiran dalam makalah yang hebat ini (tetapi sulit dibaca) oleh L. Levin arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf
user2471
lihat juga penerapan tesis Church-Turing untuk model komputasi interaktif
vzn

Jawaban:

5

Tesis Church-Turing telah terbukti untuk semua tujuan praktis.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz dan Gurevich, Bulletin of Symbolic Logic, 2008.

(Referensi ini membahas sejarah pekerjaan Gereja dan Turing, dan berpendapat untuk pemisahan antara "Tesis Gereja" dan "Tesis Tesis" sebagai klaim logis yang berbeda, kemudian membuktikan keduanya, dalam aksiomatisasi komputasi yang intuitif.)

Aaron Sterling
sumber
24
Saya agak khawatir dengan jawaban ini. Mungkin memberi kesan yang salah kepada orang-orang bahwa tesis Gereja-Turing telah terbukti, padahal sebenarnya tidak (dan saya akan membayangkan kebanyakan orang berpikir itu tidak dapat dibuktikan).
Emil
5
Ini akan menjadi komentar terakhir saya di sini, tetapi saya pikir Anda mungkin ingin bertanya mengapa situs seperti ini diperlukan jika yang perlu kita lakukan hanyalah melihat buku pelajaran. Arora dan Barak adalah peneliti hebat, tetapi mereka bukan ahli logika, atau peneliti teori kompleksitas (mereka tetap menulis buku kompleksitas, meskipun ini bukan bidang penelitian utama mereka), atau ahli dalam semantik bahasa pemrograman (yang merupakan motivasi asli untuk mesin keadaan abstrak). Kearifan konvensional belum tentu benar, dan, pada akhirnya, kita harus berpikir untuk diri kita sendiri.
Aaron Sterling
8
Jika Dershowitz dan Gurevich membuktikan tesis Church dan Turing, maka mereka juga membuktikan bahwa di masa depan kita tidak akan dapat membangun komputer yang melakukan banyak langkah komputasi dalam waktu terbatas, lihat misalnya arxiv.org/ab/gr-qc/ 0104023 yang membahas kemungkinan seperti itu.
Andrej Bauer
50
Seperti yang biasanya dipahami, tesis Gereja-Turing bukanlah proposisi formal yang dapat dibuktikan. Ini adalah hipotesis ilmiah, sehingga dapat "dibantah" dalam arti bahwa itu dapat dipalsukan. "Bukti" apa pun harus memberikan definisi komputabilitas dengannya, dan buktinya hanya sebagus definisi itu. Saya yakin Dershowitz-Gurevich memiliki bukti yang bagus, tetapi masalah sebenarnya adalah apakah definisi tersebut benar-benar mencakup semua yang dapat dihitung. Menjawab "dapatkah itu dibantah?" dengan mengatakan "sudah terbukti" menyesatkan. Ini telah dibuktikan dengan definisi komputabilitas yang masuk akal (dapat dipalsukan!).
Ryan Williams
47
Makalah Dershowitz-Gurevich tidak mengatakan apa-apa tentang perhitungan probabilistik atau kuantum. Itu memang menulis serangkaian aksioma tentang perhitungan, dan membuktikan tesis Gereja-Turing dengan asumsi aksioma tersebut. Namun, kita dibenarkan dengan aksioma ini. Baik perhitungan probabilistik maupun kuantum tidak tercakup oleh aksioma-aksioma ini (mereka mengakui ini untuk perhitungan probabilistik, dan tidak menyebutkan komputasi kuantum sama sekali), jadi cukup jelas bagi saya aksioma-aksioma ini sebenarnya salah di dunia nyata, meskipun Church-Turing tesis mungkin benar.
Peter Shor
60

Ada hal halus yang jarang saya singgung dalam diskusi semacam ini dan saya pikir patut mendapat perhatian lebih.

ff

fff. OKE, baiklah, tapi sekarang anggaplah kita membangun hypercomputer dan bertanya apakah mesin Turing yang mencari kontradiksi di ZFC akan pernah berhenti. Anggap lebih jauh bahwa hypercomputer menjawab, "Tidak." Apa yang kita simpulkan? Apakah kita menyimpulkan bahwa hypercomputer telah "menghitung" konsistensi ZFC? Bagaimana kita mengesampingkan kemungkinan bahwa ZFC sebenarnya tidak konsisten dan kita baru saja melakukan percobaan yang telah memalsukan teori fisik kita?

Fitur penting dari definisi Turing adalah bahwa asumsi filosofisnya sangat lemah. Ini mengasumsikan, tentu saja harus, fitur sederhana tertentu dari pengalaman kita sehari-hari, seperti stabilitas dasar dunia fisik, dan kemampuan untuk melakukan operasi yang terbatas dengan cara yang andal, berulang, dan dapat diverifikasi. Hal-hal ini diterima semua orang (di luar kelas filsafat, yaitu!). Namun, penerimaan komputer hypercacu tampaknya mengharuskan kita menerima ekstrapolasi tanpa batastentang teori fisik, dan semua pengalaman kita dengan fisika telah mengajarkan kita untuk tidak bersikap dogmatis tentang validitas teori dalam rezim yang jauh melampaui apa yang dapat kita verifikasi secara eksperimen. Untuk alasan ini, tampaknya sangat tidak mungkin bagi saya bahwa setiap jenis konsensus besar pernah akan mengembangkan bahwa setiap hypercomputer tertentu hanya komputasi sebagai lawan hypercomputing , yaitu, melakukan sesuatu yang bisa disebut "computing" hanya jika Anda menerima beberapa filosofis kontroversial atau asumsi fisik tentang ekstrapolasi yang tak terbatas.

Cara lain untuk menjelaskannya adalah bahwa menyanggah tesis Church-Turing tidak hanya membutuhkan pembuatan perangkat yang dijelaskan Andrej, tetapi juga membuktikan kepuasan semua orang bahwa perangkat berkinerja seperti yang diiklankan. Meskipun tidak dapat dibayangkan, ini adalah hal yang sulit. Untuk komputer saat ini, sifat perhitungan yang terbatas berarti bahwa jika saya tidak percaya hasil dari "perhitungan" komputer tertentu, saya pada prinsipnya dapat melakukan serangkaian langkah terbatas dalam beberapa cara yang sangat berbeda untuk memeriksa hasilnya. Jenis "fallback" seperti ini yang masuk akal dan verifikasi terbatas tidak tersedia jika kita ragu dengan hypercomputer.

Timothy Chow
sumber
1
Tim, jelas, tesis Gereja-Turing dapat disangkal oleh demonstrasi model komputasi efektif yang berhasil yang melampaui ruang lingkup umum dari model yang setara yang diidentifikasi Gereja dan Turing. Orang bisa berargumen betapa tidak masuk akalnya hal itu, tetapi saya percaya itu masih diperlukan. (Perhatikan bahwa saya menghindari "membuktikan" dan "membantah" dalam konteks ini.)
orcmid
2
22250
6
@Neel: Sebaliknya, maksud saya justru bahwa sangat masuk akal untuk meragukan fisika mewah yang mendasari komputer, baik yang ada saat ini atau hypercomputer masa depan. Alasan utama kita mentolerir komputer saat ini adalah karena mereka ditugaskan dengan perhitungan terbatas yang pada prinsipnya dapat kita tiru tanpa fisika mewah. Tetapi membangun komputer yang benar yang secara inheren bergantung pada ekstrapolasi teori-teori fisik tanpa batas di luar rezim yang dapat diakses secara eksperimental, dan kami tidak memiliki cara untuk mengetahui apakah perhitungannya benar atau apakah teori kami salah.
Timothy Chow
6
@orcmid: Fisika harus memasukkan gambar di suatu tempat; jika tidak, apa yang menghentikan kita dari menyatakan bahwa semua fungsi dapat dihitung? Untuk pantas namanya, "perhitungan" harus menjadi sesuatu yang dapat kita bayangkan benar-benar dilakukan. Itu sebabnya proposal untuk hypercomputer bersusah payah menjelaskan bagaimana mereka dapat dibangun secara fisik. Maksud saya adalah bahwa kita harus mengambil percobaan pikiran selangkah lebih maju: Dihadapkan dengan komputer yang diduga hiper, bagaimana kita tahu bahwa itu benar-benar berfungsi seperti yang diiklankan? Jika kita tidak bisa tahu, apakah benar sah untuk menyebut hasilnya sebagai "perhitungan"?
Timothy Chow
1
Ini menarik, mungkin kita tidak bisa benar-benar tahu bahwa mesin itu menghitung f, karena kita baru saja menyelesaikan Turing. Mungkin perlu pengamat
komputasi hiper
58

Walaupun tampaknya cukup sulit untuk membuktikan tesis Gereja-Turing karena sifat informal dari "fungsi yang dapat dihitung secara efektif", kita dapat membayangkan apa artinya menolaknya. Yaitu, jika seseorang membuat perangkat yang (andal) menghitung fungsi yang tidak dapat dihitung oleh mesin Turing apa pun, itu akan menyanggah tesis Gereja-Turing karena itu akan membangun keberadaan fungsi yang dapat dihitung secara efektif yang tidak dapat dihitung oleh mesin Turing.

Andrej Bauer
sumber
1
Dalam arti apa seseorang harus "membangun" mesin? Kita hidup di dunia yang terbatas yang hanya berisi komputer yang benar-benar lebih lemah daripada mesin Turing. Mungkin dia harus menciptakan karakterisasi logis baru yang menarik secara intuitif? Seperti apa itu?
Vag
2
Dan alam semesta kita semakin terbatas dari pada teori Finite State Mashines karena keterbatasan massa / energi oleh konstanta beton dan Batas Bremmermann pespmc1.vub.ac.be/ASC/Bremer_limit.html sehingga ada perhitungan yang dapat dilakukan FSM imajiner yang lebih besar selain komputer fisik. tidak bisa (masalah transkomputasi).
Vag
2
Tentu saja akan diperlukan bagi manusia untuk dapat mensimulasikan mesin, untuk membantah tesis asli Turing yang mengidentifikasi kalkulasi efektif dengan kalkulasi manusia.
Carl Mummert
35

Menyangkal tesis Gereja-Turing tampaknya memang sangat tidak mungkin dan secara konsep sangat sulit dibayangkan. Ada berbagai "dunia fisik hipotetis" yang berada dalam ketegangan dengan tesis Gereja-Turing (tetapi apakah mereka bertentangan itu dengan sendirinya merupakan pertanyaan filosofis yang menarik). Sebuah makalah oleh Pitowsky " Tesis Gereja Fisik dan Kompleksitas Komputasi Fisik", Iyun 39, 81-99 (1990) berkaitan dengan dunia fisik hipotetis semacam itu. Lihat juga kertas oleh Itamar Pitowsky dan Oron Shagrir: " Tesis Gereja-Turing dan Komputasi Hiper ", Minds and Machines 13, 87-101 (2003). Oron Shagrir telah menulis beberapa makalah filosofis tentang tesis Gereja-Turing melihat halaman web-nya . (Lihat juga posting blog ini .)

Tesis Church-Turing yang efektif atau efisien adalah pernyataan yang jauh lebih kuat daripada pernyataan Church-Turing asli yang menyatakan bahwa setiap perhitungan yang mungkin dapat disimulasikan secara efisien oleh mesin Turing. Komputer kuantum memang akan menunjukkan bahwa tesis Church-Turing yang efisien tidak valid (modulo beberapa dugaan kompleksitas matematika komputasional, dan modulo "interpretasi asimptotik"). Saya pikir dugaan Church-Turing yang efisien pertama kali dirumuskan pada tahun 1985 oleh Wolfram, makalah ini dikutip dalam makalah Pitowsky yang terkait di atas. Bahkan, Anda bahkan tidak perlu komputer kuantum universal untuk menyangkal tesis CT efisien, dan itu adalah garis penelitian yang menarik (bahwa Aaronson antara studi lain) untuk mengusulkan sesederhana mungkin demonstrasi keunggulan komputasi dari sistem kuantum.

Ini juga merupakan masalah yang menarik jika ada cara yang lebih sederhana untuk menunjukkan keunggulan komputasi komputer kuantum di hadapan kebisingan, daripada memiliki toleransi kesalahan kuantum penuh (yang memungkinkan perhitungan kuantum universal). (Scott A. memang tertarik juga dengan masalah ini.)

Gil Kalai
sumber
Saya pikir mesin Turing dapat mensimulasikan komputer kuantum? (Tentu saja sangat kehilangan efisiensi.) (Sunting: ah, saya perhatikan Anda mengatakan "tesis CT Efektif" - apakah ini tesis yang dapat disimulasikan oleh perangkat TM mana pun secara efisien?)
Emil
5
Saya pikir Gil sedang berbicara tentang tesis Turing Gereja "diperpanjang" (yang ia sebut tesis Turing Gereja "efektif") bahwa segala sesuatu yang dapat dihitung secara efisien di alam juga dapat dihitung pada mesin Turing polytime.
Ryan Williams
2
Saya menambahkan kalimat untuk memperjelasnya.
Gil Kalai
Gil, terima kasih untuk kiriman bagus ini! Untuk mengekspresikan sudut pandang rekayasa sistem kuantum, kita manusia ada di alam semesta yang bising di mana (koreksi kesalahan tidak ada) ECT secara empiris benar --- di mana proses dinamika kuantum dapat disimulasikan secara efisien --- melalui formalisme di mana (Secara efektif) superposisi kuantum adalah perkiraan lokal, dalam arti yang hampir sama dengan geometri Euclidean adalah perkiraan lokal untuk geometri Riemann. Apakah Alam merangkul aliran kuantum yang sama, sehingga dapat menghitung dirinya sendiri secara efisien? Itu adalah pertanyaan terbuka ... dan IMHO yang sangat menarik.
John Sidles
Terinspirasi oleh pos Gil dan oleh pos Timothy Chow (di bawah), saya telah mempromosikan komentar di atas untuk pertanyaan TCS formal: "Apa peran yang tepat validasi dalam pengambilan sampel kuantum, simulasi, dan pengujian extended-Church-Turing (ECT)? " Terima kasih, Gil dan Timothy.
John Sidles
24

Sejauh yang saya mengerti, "ketidakmungkinan" untuk membuktikan atau menyangkal tesis ini adalah bahwa tidak ada definisi formal "dapat dihitung secara efektif". Hari ini, kami menganggapnya tepat "dapat dihitung dengan mesin Turing", tapi itu malah menimbulkan pertanyaan.

Model-model perhitungan yang benar-benar lebih kuat daripada mesin Turing telah dipelajari, lihatlah di http://en.wikipedia.org/wiki/Hypercomputation untuk beberapa contoh. Atau ambil saja mesin Turing dengan oracle untuk Masalah Pemutusan untuk Mesin Turing. Mesin seperti itu akan memiliki Masalah Berhenti sendiri, tetapi dapat menyelesaikan Masalah Berhenti asli dengan baik. Tentu saja, kita tidak memiliki ramalan seperti itu, tetapi secara matematis tidak ada yang mustahil tentang gagasan itu.

Evgenij Thorstensen
sumber
Terima kasih atas jawabannya. Jadi, datang dengan fungsi yang secara matematis dapat direalisasikan (tetapi tidak secara fisik) oleh beberapa model tetapi tidak dengan mesin Turing tidak menyangkal tesis?
1
Dershowitz dan Gurevich 2008 aksioma "dihitung secara efektif" dengan menggunakan mesin negara abstrak.
Aaron Sterling
4
Jadi, mereka mendefinisikan model komputasi lain, dan membuktikannya setara dengan yang ada, bukan? Mengapa model komputasi lebih dapat dipercaya daripada yang ada?
Blaisorblade
Kita dapat menggunakan kekuatan manusia sebagai ramalan seperti itu, menyusun bukti formal untuk penghentian (bukan). Runtime yang buruk, ...
Raphael
10

Penonaktifan hiperkomputasi umumnya mengasumsikan validitas terikat Bekenstein, yang menegaskan batas tertentu pada jumlah informasi yang dapat dikandung oleh ruang yang terbatas. Ada kontroversi mengenai ikatan ini, tetapi saya pikir sebagian besar fisikawan menerimanya.

Jika ikatan Bekenstein dilanggar dengan buruk, dan tidak ada batasan pada jumlah informasi yang terkandung di wilayah tertentu (katakanlah, lubang hitam, atau ukiran yang sangat halus dan kuat), dan ada mekanisme yang dapat disempurnakan lagi secara sewenang-wenang untuk memeriksa konten yang wilayah (katakanlah, dengan hati-hati memeriksa radiasi yang dipancarkan sebagai objek yang dibangun dengan hati-hati jatuh ke dalam lubang hitam, atau dengan menjalankan stylus di atas alur ukiran), orang dapat menganggap bahwa artefak kebetulan sudah ada yang mengkode oracle yang berhenti .

Semua sangat tidak mungkin, tetapi itu menunjukkan bahwa klaim bahwa hiperkomputasi tidak mungkin bukan kebenaran matematika, tetapi didasarkan pada fisika. Yang mengatakan bahwa Andrej benar ketika dia mengatakan kita bisa membayangkan apa artinya menyangkal [tesis Gereja-Turing]. Yaitu, jika seseorang membuat perangkat yang (andal) menghitung fungsi yang tidak dapat dihitung oleh mesin Turing apa pun .

Charles Stewart
sumber
Ikatan Bekenstein masih berlaku namun perhitungan yang berlebihan masih mungkin terjadi.
András Salamon
@ András: Pada prinsipnya ya: kita membutuhkan lebih banyak teori fisik untuk mendapatkan argumen negatif agar berhasil. Tetapi upaya untuk "menggambarkan" mesin hypercomputing yang saya lihat semua melanggar itu.
Charles Stewart
Apakah yang melibatkan loop tertutup dekat lubang hitam melanggar batas?
András Salamon
@ András: Saya tidak tahu yang Anda maksud. Teori string umumnya kompatibel dengan ikatan Bekenstein.
Charles Stewart
Maksud saya hal-hal seperti arxiv.org/abs/gr-qc/0209061 yang alih-alih mengandalkan teori string, "hanya" menganggap seseorang dapat mengirim perhitungan ke masa lalu.
András Salamon
9

Mengenai Tesis Diperpanjang Gereja-Turing (dimaksudkan sebagai "mesin Turing probabilistik dapat secara efisien mensimulasikan setiap fungsi yang dapat dihitung secara fisik."):

Satu kemungkinan adalah perbedaan antara komputer klasik dan kuantum. Khususnya pertanyaan, "Apakah ada tugas yang dapat dilakukan komputer kuantum yang tidak bisa dilakukan komputer klasik?" Sebuah laporan ECCC baru-baru ini oleh Scott Aaronson (lihat dugaan 9 di halaman 5) menyoroti dugaan bahwa, jika terbukti, akan memberikan bukti kuat terhadap Tesis Church-Turing yang Diperpanjang.

Jika seseorang menyangkal Tesis Gereja-Turing Diperpanjang, bisa terlihat seperti itu - khususnya, dengan menunjukkan tugas yang dapat dihitung secara efisien bahwa mesin Turing (klasik) tidak dapat menghitung secara efisien.

Daniel Apon
sumber
2
Untuk memperjelas, perhitungan kuantum hanya mempertanyakan tesis Turing Gereja Efisien / Diperpanjang / Kuat yang menyatakan bahwa semua model komputasi yang dapat direalisasi dapat disimulasikan pada mesin Turing dalam waktu polinomial. Tesis Gereja-Turing yang normal tidak membatasi efisiensi. Komputer kuantum tidak memiliki harapan untuk menggulingkan versi ini karena mesin Turing dapat mensimulasikan semua cabang komputasi kuantum dalam waktu terbatas secara eksponensial.
Ian
Ya, terima kasih untuk ini - Saya telah memperbaiki penggunaan kedua istilah ini dengan ceroboh.
Daniel Apon
Hmmm ... tetapi menurut definisi standar, bukankah ECT sudah terbukti secara meyakinkan? Alice: "Inilah contoh digit biner acak yang dihitung oleh jaringan optik kuantum (satu mode)". Bob: "Ini contoh angka pseudo-acak yang dihitung oleh mesin Turing klasik." Alice: "Maaf Bob ... sampel Anda secara algoritmik dapat dikompresi, dan milik saya tidak. Oleh karena itu, data saya menunjukkan bahwa ECT salah!" Secara formal, alasan Alice sangat sempurna. Namun pengujian validasi absen atas klaim Alice, haruskah kita puas?
John Sidles
4

Makalah berikut dari Selim Akl mungkin menarik dan relevan dengan diskusi:

Akl, SG, "Tiga contoh tandingan untuk menghilangkan mitos tentang komputer universal", Parallel Processing Letters, Vol. 16, No. 3, September 2006, hlm. 381 - 403.

Akl, SG, "Bahkan mesin akselerasi tidak universal", International Journal of Unconventional Computing, Vol. 3, No. 2, 2007, hlm. 105 - 121.

Nagy, M. dan Akl, SG, "Paralelisme dalam pemrosesan informasi kuantum mengalahkan Komputer Universal", Surat Pemrosesan Paralel, Edisi Khusus tentang Masalah Komputasi yang Tidak Konvensional, Vol. 17, No. 3, September 2007, hlm. 233 - 262.

Ini adalah abstrak dari yang pertama:

Terlihat bahwa konsep Universal Computer tidak dapat diwujudkan. Secara khusus, instance dari fungsi yang dapat dihitung F diperlihatkan yang tidak dapat dihitung pada setiap mesin U yang hanya mampu sejumlah operasi terbatas dan tetap per langkah. Ini tetap benar bahkan jika mesin U dianugerahi dengan memori tak terbatas dan kemampuan untuk berkomunikasi dengan dunia luar ketika ia sedang mencoba untuk menghitung F. Ini juga tetap benar jika, di samping itu, U diberi jumlah waktu yang tidak terbatas untuk menghitung F. Hasil ini berlaku tidak hanya untuk model perhitungan ideal, seperti Mesin Turing dan sejenisnya, tetapi juga untuk semua komputer tujuan umum yang dikenal, termasuk komputer konvensional yang ada (baik berurutan dan paralel), serta yang tidak konvensional seperti yang dimaksud. sebagai komputer biologis dan kuantum.

Massimo Cafaro
sumber
Bisakah Anda memberikan tautan ke koran pertama yang tidak berada di belakang paywall? Apa definisi mereka tentang "fungsi yang dapat dihitung?" Di bawah definisi standar (ada mesin Turing yang menghitung fungsi) klaim mereka secara definisi salah ...
Christopher Monsanto
Saya baru saja mengirim Anda kertas melalui email.
Massimo Cafaro
Berikut adalah salah satu makalah ini: research.cs.queensu.ca/home/akl/techreports/even.pdf . Lebih lanjut di sini: research.cs.queensu.ca/Parallel/projects.html . Tidak ada definisi sebenarnya dari "komputer" di koran, hanya deskripsi bergelombang tangan. Agaknya deskripsi bergelombang tangan itu dapat diformalkan dengan sedikit pekerjaan, menggunakan model mesin Turing atau sesuatu yang serupa dengan dasarnya.
Sasho Nikolov
W(t)tcW(t)>ct
Sasho Nikolov
-6

Bagaimana itu bisa benar? Komputer klasik tidak dapat secara efisien mensimulasikan komputer kuantum. Ada algoritma kuantum yang memberikan kecepatan eksponensial lebih dari komputer klasik yang menjalankan algoritma klasik: Algoritma Shor menjadi satu.

Robert McGwier
sumber
3
1) Mungkin ada algoritma factoring polytime klasik. Kita tidak tahu satu, tetapi keberadaannya sepenuhnya konsisten dengan keadaan teori kompleksitas. 2) Tesis Church-Turing yang asli adalah tentang komputabilitas, bukan tentang komputabilitas yang efisien .
Sasho Nikolov