Saya memahami bukti ketidaktentuan masalah penghentian (diberikan misalnya dalam buku teks Papadimitriou), berdasarkan diagonalisasi.

Sementara buktinya meyakinkan (saya mengerti setiap langkahnya), itu tidak intuitif bagi saya dalam arti bahwa saya tidak melihat bagaimana seseorang akan mendapatkannya, mulai dari masalahnya sendiri.

Dalam buku ini, buktinya seperti ini: "misalkan memecahkan masalah penghentian pada input , yaitu, memutuskan apakah mesin Turing M berhenti untuk input x . Buat mesin Turing D yang menggunakan mesin Turing M sebagai input , jalankan M_H (M; M) dan membalikkan output. " Kemudian menunjukkan bahwa D (D) tidak dapat menghasilkan output yang memuaskan.$M_H$$M;x$x D M M H ( M ; M ) D ( D $M$$x$$D$$M$$M_H(M;M)$$D(D)$

Ini adalah konstruksi D yang tampaknya sewenang-wenang $D$, terutama gagasan untuk memberi makan $M$ pada dirinya sendiri, dan kemudian $D$ untuk dirinya sendiri, yang ingin saya intuisi. Apa yang membuat orang mendefinisikan konstruksi dan langkah-langkah itu?

Apakah ada yang punya penjelasan tentang bagaimana seseorang akan masuk ke argumen diagonalisasi (atau bukti lain), jika mereka tidak tahu jenis argumen seperti itu?

Tambahan diberikan pada putaran pertama jawaban:

Jadi jawaban pertama menunjukkan bahwa membuktikan ketidakpastian masalah penghentian adalah sesuatu yang didasarkan pada pekerjaan Cantor dan Russell sebelumnya dan pengembangan masalah diagonalisasi, dan bahwa memulai "dari awal" hanya berarti harus menemukan kembali argumen itu.

Cukup adil. Namun, bahkan jika kita menerima argumen diagonalisasi sebagai pemberian yang dipahami dengan baik, saya masih menemukan ada "celah intuisi" dari itu ke masalah penghentian. Bukti Cantor tentang bilangan real yang tidak dapat dihitung, sebenarnya saya temukan cukup intuitif; Paradoks Russell bahkan lebih.

Apa yang saya masih tidak melihat adalah apa yang akan memotivasi seseorang untuk mendefinisikan $D(M)$ berdasarkan $M$ "aplikasi diri" $M;M$ , dan sekali lagi menerapkan $D$ untuk dirinya sendiri. Itu tampaknya kurang terkait dengan diagonalisasi (dalam arti bahwa argumen Cantor tidak memiliki sesuatu seperti itu), meskipun itu jelas bekerja dengan baik dengan diagonalisasi setelah Anda mendefinisikannya.

PS

@Babou merangkum apa yang lebih mengganggu saya daripada diri saya sendiri: "Masalah dengan banyak versi buktinya adalah bahwa konstruksi tampaknya ditarik dari topi ajaib."

Dalam hasil edit Anda, Anda menulis:

Apa yang saya masih tidak melihat adalah apa yang akan memotivasi seseorang untuk mendefinisikan berdasarkan "aplikasi diri" , dan sekali lagi menerapkan untuk dirinya sendiri. Itu tampaknya kurang terkait dengan diagonalisasi (dalam arti bahwa argumen Cantor tidak memiliki sesuatu seperti itu), meskipun itu jelas bekerja dengan baik dengan diagonalisasi setelah Anda mendefinisikannya.M M ; M $D(M)$$M$$M;M$$D$

Peringkasan "populer" yang umum dari bukti Turing berbunyi seperti ini:

"Jika kita memiliki mesin yang bisa memutuskan apakah lain Turing perhentian mesin atau tidak, kita bisa menggunakan ini untuk membangun komputer lain itu, diberi Turing mesin , akan menghentikan jika dan hanya jika lakukan tidak berhenti. Tapi kemudian kita bisa berikan sebagai input untuk dirinya sendiri, dan dengan demikian memperoleh paradoks: mesin ini akan berhenti jika dan hanya jika tidak berhenti! " D M M $M_H$$D$$M$$M$$D$

Sekarang, mudah untuk melihat bahwa peringkasan di atas menjelaskan detail penting - penghentian mesin Turing juga tergantung pada inputnya, yang belum kami tentukan! Tetapi masalah ini dapat diperbaiki dengan cukup mudah: kita hanya perlu meminta memilih beberapa input sesuai untuk setiap mesin input , sebelum meneruskan keduanya ke .D x M M M $M$$D$$x_M$$M$$M_H$

Apa pilihan yang cocok untuk , mengingat pada akhirnya kami ingin mendapatkan kontradiksi? Nah, pilihan alami disarankan langsung oleh bukti "handwavy" di atas, di mana kita akhirnya mendapatkan kontradiksi dengan menjalankan mesin pada dirinya sendiri.$x_M$$D$

Jadi, untuk perilaku benar-benar paradoks dalam kasus ini, yaitu ketika dipanggil sebagai , yang kita inginkan adalah penghentian bergantung pada perilaku ketika dipanggil sebagai . Dengan cara ini, kita akan mendapatkan kontradiksi yang kita inginkan dengan menetapkan .$D$D ( M ) M M ( M ) M = $D(D)$$D(M)$$M$ $M(M)$$M = D$

Pikiran Anda, ini bukan satu-satunya pilihan; kita juga bisa mendapatkan kontradiksi yang sama dengan, katakanlah, membangun mesin sedemikian rupa sehingga berhenti jika dan hanya jika (bukan ) tidak berhenti. Tapi, sementara jelas bahwa mesin dapat dengan mudah menduplikasi inputnya sebelum meneruskannya ke , itu tidak begitu jelas bagaimana membangun mesin yang akan memanggil dengan kode sendiri sebagai input. Jadi, menggunakan bukannya akan mempersulit pembuktian, dan membuatnya kurang intuitif.D ′ ( M ) M ( D ′ ) M ( M ) D M H D ′ M H D ′$D'$$D'(M)$$M(D')$$M(M)$$D$$M_H$$D'$$M_H$$D'$$D$

Mungkin semata-mata keliru untuk berpikir bahwa seseorang akan beralasan dalam argumen ini tanpa membuat argumen serupa di beberapa titik sebelumnya, dalam konteks "sederhana".

Ingat bahwa Turing tahu bukti diagonalisasi Cantor tentang tak terhitungnya real. Selain itu karyanya adalah bagian dari sejarah matematika yang mencakup paradoks Russell (yang menggunakan argumen diagonisasi) dan teorema ketidaklengkapan pertama Gödel (yang menggunakan argumen diagonisasi). Faktanya, hasil Gödel sangat terkait dengan bukti keraguan terhadap Masalah Pemutusan (dan karenanya jawaban negatif untuk Hilts's Entscheidungsproblem).

Jadi pendapat saya adalah bahwa pertanyaan Anda dalam arti buruk didirikan dan bahwa Anda tidak dapat mencapai Masalah Henti tanpa melewati sisanya (atau sesuatu yang sangat mirip) terlebih dahulu. Sementara kami menunjukkan hal-hal ini kepada siswa tanpa melalui sejarah, jika Anda seorang ahli matematika yang bekerja, tampaknya tidak mungkin bahwa Anda beralih dari ketiadaan ke Mesin Turing tanpa ada apa-apa di antaranya - inti dari semuanya adalah memformalkan perhitungan, masalah yang dihadapi banyak orang. telah bekerja selama beberapa dekade pada saat itu.

Cantor bahkan tidak menggunakan diagonisasi sebagai bukti pertamanya tentang tak terhitung banyaknya real, jika kita menganggap tanggal publikasi sebagai perkiraan ketika dia memikirkan ide itu (tidak selalu merupakan hal yang dapat diandalkan), butuh sekitar 17 tahun sejak dia mengetahui bahwa real tidak terhitung, untuk menyelesaikan argumen diagonisasi.

Mengacu pada "penerapan diri" dalam bukti yang Anda sebutkan, ini juga merupakan bagian integral dari paradoks Russell (yang sepenuhnya bergantung pada referensi diri), dan teorema ketidaklengkapan pertama Gödel seperti versi bertenaga tinggi dari paradoks Russell . Bukti dari ketidakpastian Masalah Pemutusan sangat banyak diinformasikan oleh karya Gödel sehingga sulit untuk membayangkan pergi ke sana tanpanya, maka gagasan "aplikasi mandiri" sudah menjadi bagian dari latar belakang pengetahuan yang Anda butuhkan untuk Masalah Pemutusan. . Demikian pula, karya Gödel adalah pengerjaan ulang paradoks Russell, jadi Anda tidak bisa sampai di sana tanpa yang lain (perhatikan bahwa Russell bukan yang pertama mengamati paradoks seperti ini, jadi prototipe argumen diagonisasi telah ada dalam logika formal sejak sekitar 600BCE). Karya Turing dan Gödel (bit yang kita bicarakan di sini) dapat dilihat sebagai demonstrasi yang semakin kuat dari masalah dengan referensi-diri, dan bagaimana hal itu tertanam dalam matematika. Jadi sekali lagi, sangat sulit untuk menyarankan bahwa ide-ide ini pada tingkat yang dihadapi Turing datang dengannyaa priori , mereka adalah puncak dari karya ribuan tahun di bagian filsafat, matematika dan logika.

Referensi-diri ini juga merupakan bagian dari argumen Cantor, hanya saja tidak disajikan dalam bahasa yang tidak wajar seperti karya Turing yang lebih mendasar secara logis. Diagonisasi Cantor dapat diulangi sebagai pemilihan elemen dari set daya set (pada dasarnya bagian dari Teorema Cantor). Jika kita menganggap himpunan real (positif) sebagai himpunan bagian dari naturals (perhatikan bahwa kita tidak benar-benar membutuhkan digit untuk dipesan agar ini berfungsi, itu hanya membuat presentasi yang lebih sederhana) dan mengklaim ada penolakan dari naturals ke real, maka kita dapat menghasilkan elemen dari set daya (yaitu nyata) yang tidak sesuai dengan gambar dari surject (dan karenanya mendapatkan kontradiksi) dengan mengambil elemen ini menjadi set natural yang tidak di dalam mereka sendiri gambar di bawah surjection. Begitu kita mengucapkannya dengan cara ini, itu

Penerapan sendiri bukanlah unsur penting dari pembuktian

Pendeknya

Jika ada mesin Turing yang memecahkan masalah penghentian, maka dari mesin itu kita dapat membangun mesin Turing dengan perilaku penghentian (fungsi karakteristik penghentian) yang tidak bisa menjadi perilaku penghentian dari mesin Turing.$H$$L$

Paradoks yang dibangun di atas fungsi yang diterapkan sendiri (disebut dalam jawaban ini - maaf tentang ketidakkonsistenan notasi) bukan merupakan unsur yang diperlukan dari buktinya, tetapi sebuah perangkat yang dapat digunakan dengan konstruksi satu kontradiksi tertentu, menyembunyikan apa yang tampaknya menjadi "nyata" tujuan "dari konstruksi. Itu mungkin sebabnya itu tidak intuitif.$D$$L$

Tampaknya lebih langsung untuk menunjukkan bahwa hanya ada sejumlah perilaku penghentian (tidak lebih dari mesin Turing), yang dapat didefinisikan sebagai fungsi penghentian karakteristik yang terkait dengan setiap mesin Turing. Seseorang dapat mendefinisikan secara konstruktif fungsi penghentian karakteristik yang tidak ada dalam daftar, dan membangun dari itu, dan dari mesin yang memecahkan masalah penghentian, mesin yang memiliki fungsi penghentian karakteristik yang baru. Tapi karena, dengan konstruksi, itu bukan fungsi penghentian karakteristik mesin Turing, tidak bisa menjadi satu. Karena dibangun dari menggunakan teknik bangunan mesin Turing, tidak bisa menjadi mesin Turing.L L L H $H$$L$$L$$L$$H$$H$

Penerapan diri pada dirinya sendiri, yang digunakan dalam banyak bukti, adalah cara untuk menunjukkan kontradiksi. Tapi itu hanya berfungsi ketika fungsi penghentian karakteristik yang mustahil dibangun dari diagonal daftar Turing yang memungkinkan fungsi penghentian karakteristik, dengan membalik diagonal ini (menukar dan ). Tetapi ada banyak cara lain untuk membangun fungsi penghentian karakteristik baru. Maka non-Turing-ness tidak bisa lagi dibuktikan dengan paradoks pembohong (setidaknya bukan hanya). Konstruksi penerapan diri tidak intuitif karena tidak penting, tetapi terlihat licin ketika ditarik keluar dari topi ajaib.0 $L$$0$$1$

Pada dasarnya, bukan mesin Turing karena dirancang sejak awal untuk memiliki perilaku berhenti yang bukan dari mesin Turing, dan yang dapat ditampilkan lebih langsung, maka lebih intuitif.$L$

Catatan : Mungkin saja, untuk setiap pilihan konstruktif dari fungsi penghentian karakteristik yang mustahil, ada penataan ulang yang dapat dihitung dari enumerasi mesin Turing sedemikian rupa sehingga menjadi diagonal (saya tidak tahu). Tapi, ya, ini tidak mengubah fakta bahwa penerapan diri adalah teknik bukti tidak langsung yang menyembunyikan fakta yang lebih intuitif dan menarik.

Analisis terperinci dari bukti-bukti

Saya tidak akan menjadi historis (tapi terima kasih kepada mereka yang, saya menikmatinya), tetapi saya hanya mencoba untuk mengerjakan sisi intuisi.

Saya pikir presentasi yang diberikan @vzn , yang saya temui sejak lama (saya lupa), sebenarnya agak intuitif, dan bahkan menjelaskan nama diagonalisasi. Saya mengulanginya secara terperinci hanya karena saya merasa @vzn tidak cukup menekankan kesederhanaannya.

Tujuan saya adalah memiliki cara intuitif untuk mengambil bukti, mengetahui bahwa Cantor. Masalah dengan banyak versi pembuktiannya adalah bahwa konstruksi tampaknya ditarik dari topi ajaib.

Bukti yang saya berikan tidak persis sama dengan yang ada di pertanyaan, tetapi itu benar, sejauh yang saya bisa lihat. Jika saya tidak membuat kesalahan, itu cukup intuitif karena saya bisa mengambilnya setelah bertahun-tahun daripada yang saya perhitungkan, mengerjakan masalah yang sangat berbeda.

Kasing himpunan bagian (Cantor)$\mathbb N$

Bukti Cantor mengasumsikan (itu hanya sebuah hipotesis) bahwa ada enumerasi himpunan bagian bilangan bulat, sehingga semua subset dapat dijelaskan oleh fungsi karakteristiknya yaitu jika dan adalah sebaliknya.$S_j$$C_j(i)$$1$$i\in S_j$$0$

Ini dapat dilihat sebagai tabel , sehingga$T$$T[i,j]=C_j(i)$

Kemudian, dengan mempertimbangkan diagonal, kita membangun fungsi karakteristik sedemikian rupa sehingga , yaitu identik dengan diagonal tabel dengan setiap bit diputar ke nilai lainnya.$D$$D(i)=\overline{T[i,i]}$

Tidak ada yang istimewa tentang diagonal, kecuali bahwa itu adalah cara mudah untuk mendapatkan fungsi karakteristik yang berbeda dari yang lainnya, dan hanya itu yang kita butuhkan.$D$

Oleh karena itu, himpunan bagian yang ditandai dengan tidak dapat di enumerasi. Karena itu akan menjadi kenyataan pencacahan apapun, tidak mungkin ada penghitungan yang menyebutkan semua himpunan bagian dari .$D$$\mathbb N$

Ini diakui, menurut pertanyaan awal, cukup intuitif. Bisakah kita membuat bukti dari masalah berhenti sebagai intuitif?

Kasus masalah terputus-putus (Turing)

Kami berasumsi kami memiliki penghitungan mesin Turing (yang kami tahu mungkin). Perilaku penghentian mesin Turing dapat dijelaskan dengan fungsi penghentian karakteristiknya yaitu jika berhenti pada input dan sebaliknya.$M_j$$H_j(i)$$1$$M_j$$i$$0$

Ini dapat dilihat sebagai tabel , sehingga$T$$T[i,j]=H_j(i)$

Kemudian, dengan mempertimbangkan diagonal, kita membangun fungsi penghentian karakteristik sedemikian rupa sehingga , yaitu identik dengan diagonal tabel dengan setiap bit diputar ke nilai lainnya.$D$$D(i)=\overline{T[i,i]}$

Tidak ada yang istimewa tentang diagonal, kecuali bahwa itu adalah cara mudah untuk mendapatkan fungsi penghentian karakteristik yang berbeda dari yang lainnya, dan hanya itu yang kita butuhkan (lihat catatan di bagian bawah).$D$

Oleh karena itu, perilaku terputus-putus yang ditandai dengan tidak mungkin seperti mesin Turing dalam penghitungan. Karena kami menyebutkan semuanya, kami menyimpulkan bahwa tidak ada mesin Turing dengan perilaku itu.$D$

Sejauh ini tidak ada penghentian oracle, dan tidak ada hipotesis komputabilitas : Kami tidak tahu apa-apa tentang dan fungsi .$T$$H_j$

Sekarang anggaplah kita memiliki mesin Turing yang dapat menyelesaikan masalah penghentian, sehingga selalu berhenti dengan sebagai hasilnya.$H$$H(i,j)$$H_j(i)$

Kami ingin membuktikan bahwa, mengingat , kita dapat membangun sebuah mesin yang memiliki karakteristik tersendat-sendat fungsi . Mesin hampir identik dengan , sehingga meniru , kecuali bahwa setiap kali akan berakhir dengan nilai , masuk ke loop infinite dan tidak berakhir.$H$$L$$D$$L$$H$$L(i)$$H(i,i)$$H(i,i)$$1$$L(i)$

Cukup jelas bahwa kita dapat membangun mesin jika ada. Karenanya mesin ini harus dalam pencacahan awal kami semua mesin (yang kami tahu mungkin). Tapi itu tidak bisa karena perilaku menghentikan nya bersesuaian dengan tidak ada mesin disebutkan. Mesin tidak bisa ada, yang menyiratkan bahwa tidak bisa ada.$L$$H$$D$$L$$H$

_{Saya sengaja meniru bukti pertama dan masuk ke detail kecil}

Perasaan saya adalah bahwa langkah-langkah tersebut datang secara alami dengan cara ini, terutama ketika seseorang menganggap bukti Cantor sebagai hal yang cukup intuitif.

Yang pertama menyebutkan konstruk hukum. Kemudian seseorang mengambil dan memodifikasi diagonal sebagai cara yang nyaman untuk menyentuh mereka semua untuk mendapatkan yang tak terhitung untuk perilaku, kemudian mendapat kontradiksi dengan menunjukkan objek yang memiliki catatan untuk perilaku ... jika beberapa hipotesis benar: keberadaan enumerasi untuk Cantor, dan keberadaan oracle penghentian yang dapat dihitung untuk Turing.

Catatan: Untuk mendefinisikan fungsi , kita bisa mengganti diagonal yang dibalik dengan fungsi penghentian karakteristik lainnya, berbeda dari semua yang tercantum dalam , yang dapat dihitung (dari yang tercantum dalam , misalnya) asalkan tersedia oracle halting . Maka mesin harus dibangun sesuai, untuk memiliki sebagai fungsi penghentian karakteristik, dan akan menggunakan mesin , tetapi tidak meniru jadi langsung . Pilihan diagonal membuatnya lebih sederhana.$D$$T$$T$$L$$D$$L(i)$$H$$H(i,i)$

Perbandingan dengan bukti "lain"

Fungsi didefinisikan di sini adalah analog dari fungsi dalam bukti yang dijelaskan dalam pertanyaan.$L$$D$

Kami hanya membangunnya sedemikian rupa sehingga memiliki fungsi penghentian karakteristik yang sesuai dengan tidak ada mesin Turing, dan mendapatkan langsung kontradiksi dari itu. Ini memberi kita kebebasan untuk tidak menggunakan diagonal (apa pun nilainya).

Gagasan tentang bukti "biasa" tampaknya mencoba membunuh apa yang saya lihat sebagai ikan mati. Dikatakan: mari kita asumsikan bahwa adalah salah satu mesin yang terdaftar (yaitu, semuanya). Kemudian ia memiliki indeks dalam enumerasi itu: . Kemudian jika berhenti, kita memiliki , sehingga akan diulang dengan konstruksi. Sebaliknya, jika tidak berhenti, maka sehingga akan berhenti oleh konstruksi. Dengan demikian kita memiliki kontradiksi. Tetapi hasil kontradiksi dari cara fungsi menghentikan karakteristik$L$$j_L$$L=M_{j_L}$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=1$$L(j_L)$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=0$L $L(j_L)$$L$dibangun, dan tampaknya jauh lebih sederhana hanya untuk mengatakan bahwa tidak dapat menjadi mesin Turing karena dibangun untuk memiliki fungsi penghentian karakteristik yang bukan dari mesin Turing.$L$

Sebuah titik sisi adalah bahwa bukti biasa ini akan jauh lebih menyakitkan jika kita tidak memilih diagonal, sedangkan pendekatan langsung yang digunakan di atas tidak ada masalah dengan itu. Apakah itu bisa bermanfaat, saya tidak tahu.

Ada juga bukti dari fakta ini yang menggunakan paradoks yang berbeda, paradoks Berry, yang saya dengar dari Ran Raz.

Misalkan masalah penghentian dapat dihitung. Misalkan adalah bilangan alami terkecil yang tidak dapat dihitung dengan program C panjang . Yaitu, jika adalah himpunan bilangan asli yang dihitung oleh program C dengan panjang , maka adalah bilangan alami terkecil yang tidak ada dalam .n S ( n ) n B ( n ) S ( n $B(n)$$n$$S(n)$$n$$B(n)$$S(n)$

Pertimbangkan program berikut:

1. Periksa semua program C dengan panjang maksimal .$n$

2. Untuk setiap program semacam itu, periksa apakah itu berhenti; jika tidak, tambahkan ke daftar .$L$

3. Output jumlah alam pertama tidak di .$L$

Ini adalah program untuk menghitung . Seberapa besar program ini? Pengkodean mengambil karakter , dan sisa program tidak bergantung pada , jadi total panjangnya adalah , katakan paling banyak . Pilih sehingga . Kemudian program kami, yang panjangnya paling banyak , menghitung , bertentangan dengan definisi .n O ( log n ) n O ( log n ) C log n N C log N ≤ N N B ( N ) B ( N $B(n)$$n$$O(\log n)$$n$$O(\log n)$$C\log n$$N$$C\log N \leq N$$N$$B(N)$$B(N)$

Gagasan yang sama dapat digunakan untuk membuktikan teorema ketidaklengkapan Gödel, seperti yang ditunjukkan oleh Kritchman dan Raz .

Ada ide yang lebih umum yang terlibat di sini disebut "teorema rekursi" yang mungkin lebih intuitif: mesin Turing dapat menggunakan deskripsi mereka sendiri (dan dengan demikian menjalankannya sendiri). Lebih tepatnya, ada teorema:

Untuk mesin Turing T, ada mesin Turing Ryang menghitung R(x) = T(R;x).

Jika kita memiliki mesin Turing yang dapat memecahkan masalah penghentian, maka menggunakan ide yang dijelaskan di atas, kita dapat dengan mudah membangun berbagai mesin "pembohong" turing: misalnya dalam notasi seperti python,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

Argumen yang lebih rumit pada dasarnya hanya mencoba melakukan ini secara langsung tanpa menarik teorema rekursi. Artinya, itu mengulangi resep untuk membangun fungsi "referensial diri". misalnya diberi mesin Turing T, berikut adalah salah satu resep untuk membangun yang Rmemuaskan

R(x) = T(R; x)

Pertama, definisikan

S(M; x) = T(M(M; -); x)

dimana M(M; -), apa yang saya maksudkan adalah kita menghitung (menggunakan deskripsi M) dan memasukkan deskripsi mesin Turing yang, pada input y, mengevaluasi M(M; y).

Sekarang, kita amati bahwa jika kita pasang Ssendiri

S(S; x) = T(S(S; -); x)

kami mendapatkan duplikasi yang kami inginkan. Jadi jika kita atur

R = S(S; -)

maka kita miliki

R(x) = T(R; x)

seperti yang diinginkan.

bukti Turing sangat mirip dengan bukti Cantors bahwa kardinalitas real ("terhitung") lebih besar dari kardinalitas rasional ("dapat dihitung") karena mereka tidak dapat dimasukkan ke dalam korespondensi 1-1 tetapi ini tidak dicatat / ditekankan dalam sangat banyak referensi (adakah yang tahu?). (iirc) seorang profesional CS pernah menunjukkan ini tahun lalu di kelas (tidak yakin dari mana dia mendapatkannya sendiri). di Cantors bukti satu bisa membayangkan grid dengan dimensi horizontal n ^th digit dari jumlah dan dimensi vertikal n ^th jumlah set.

konstruksi bukti terputus-putus Turing sangat mirip kecuali bahwa isi tabel adalah Berhenti / Nonhalt untuk 1/0 sebagai gantinya, dan sumbu horizontal adalah input ^ke- n , dan sumbu vertikal adalah program komputer ^ke- n . dengan kata lain kombinasi program komputer dan input dapat dihitung tetapi tabel / array tak terhingga tidak terhitung berdasarkan konstruksi simulator mesin universal yang dapat "membalik" penghentian ke case tanpa henti dengan asumsi mesin penghenti detektor ada (karenanya reductio ad absurdam ) .

beberapa bukti bahwa Turing memiliki konstruksi Cantors sebagian dalam pikiran adalah bahwa makalahnya yang sama dengan bukti penghentian berbicara tentang angka yang dapat dihitung sebagai (sepanjang garis) angka nyata dengan angka yang dapat dihitung.

Pada titik ini patut dicatat karya Emil Post yang (secara adil) dikreditkan sebagai penemu bersama dari hasil dasar komputabilitas, meskipun sayangnya diterbitkan terlambat untuk dianggap sebagai penemu bersama solusi untuk Entscheidungsproblem . Dia tentu saja berpartisipasi dalam penjabaran dari apa yang disebut tesis Church-Turing .

Post itu dimotivasi oleh pertimbangan yang sangat filosofis, yaitu keterbatasan teoritis dari kemampuan manusia untuk menghitung, atau bahkan mendapatkan jawaban yang tepat secara konsisten . Dia merancang sebuah sistem, sekarang disebut sistem kanonik Post , yang detailnya tidak penting, yang dia klaim dapat digunakan untuk memecahkan masalah yang dapat diselesaikan dengan manipulasi simbol . Menariknya, ia secara eksplisit menganggap keadaan mental sebagai bagian dari "ingatan" secara eksplisit, sehingga kemungkinan ia setidaknya menganggap model komputasinya sebagai model pemikiran manusia secara keseluruhan.

Entscheidungsproblem mempertimbangkan kemungkinan menggunakan sarana perhitungan seperti itu untuk mengatakan, menentukan teorema dari setiap proposisi yang diungkapkan dalam sistem Principia Mathematica . Tetapi PM adalah sistem yang secara eksplisit dirancang untuk dapat mewakili semua penalaran matematika, dan, dengan ekstensi (setidaknya pada saat itu, ketika Logicism masih dalam mode) semua penalaran manusia!

Oleh karena itu sangat tidak mengejutkan, untuk mengalihkan perhatian dari sistem seperti itu ke sistem kanonik Post sendiri, seperti halnya pikiran manusia, melalui karya-karya Frege, Russel dan ahli logika dari pergantian abad telah mengalihkan perhatian mereka ke fakultas penalaran dari pikiran manusia itu sendiri.

Jadi jelas pada titik ini, bahwa referensi diri, atau kemampuan sistem untuk menggambarkan diri mereka sendiri, adalah subjek yang agak alami pada awal 1930-an. Bahkan, David Hilbert berharap untuk "bootstrap" penalaran matematis itu sendiri, dengan memberikan deskripsi formal dari semua matematika manusia, yang kemudian dapat secara matematis terbukti konsisten sendiri!

Setelah langkah menggunakan sistem formal untuk berpikir tentang dirinya diperoleh, itu adalah lompatan dan lompatan dari paradoks referensial diri yang biasa (yang memiliki sejarah yang cukup tua ).

Karena semua pernyataan di Principia dianggap "benar" dalam arti metafisik, dan Principia dapat mengekspresikan

phasil pengembalian program truepada inputn

jika ada program untuk memutuskan semua teorema dalam sistem itu, cukup sederhana untuk secara langsung mengekspresikan paradoks pembohong:

Program ini selalu bohong.

dapat diungkapkan oleh

Program ini pselalu mengembalikan kebalikan dari apa yang dikatakan Principia Mathematica pakan kembali.

Kesulitannya adalah membangun program p. Tetapi pada titik ini, agak alami untuk mempertimbangkan kalimat yang lebih umum

Program pselalu mengembalikan kebalikan dari apa yang dikatakan PM qakan kembali.

untuk beberapa sewenang-wenang q. Tetapi mudah untuk membangun p(q)untuk apa pun yang diberikan q! Hitung saja apa yang diprediksi oleh PM akan menghasilkan, dan kembalikan jawaban yang berlawanan. Kita tidak bisa hanya mengganti qdengan ppada titik ini, karena pmenganggap qsebagai input, dan qtidak (tidak mengambil input). Mari kita mengubah kalimat kita sehingga p tidak masukan take:

Program pmengembalikan kebalikan dari apa yang dikatakan PM q(r)akan kembali.

Arg! Tapi sekarang pmengambil 2 buah masukan: qdan r, sedangkan qhanya membutuhkan waktu 1. Tapi tunggu: kami ingin pdi kedua tempat anyways, jadi rbukan baru sepotong informasi, tetapi hanya bagian yang sama dari data lagi, yaitu q! Ini adalah pengamatan kritis.

Jadi akhirnya kami dapatkan

Program pmengembalikan kebalikan dari apa yang dikatakan PM q(q)akan kembali.

Mari kita lupakan bisnis "PM bilang" konyol ini, dan kita dapatkan

Program p(q)mengembalikan kebalikan dari apa yang q(q)akan kembali.

Ini adalah program yang sah asalkan kami memiliki program yang selalu memberi tahu kami apa yang q(q)kembali . Tetapi sekarang setelah kita memiliki program p(q)kita, kita dapat menggantinya qdengan pdan mendapatkan paradoks pembohong kita.