Kesalahpahaman tesis Gereja-Turing?

Pemahaman saya tentang tesis Gereja-Turing adalah:

• Menempatkan batas pada apa yang dapat dihitung dengan setiap proses diskrit dan terbatas.
• Meskipun masih merupakan tesis, bukan teorema, jika itu akan dibantah, ini tidak berarti hanya pembaruan untuk model perhitungan kita saat ini. Ini akan menjadi hasil pergeseran paradigma untuk matematika dan fisika secara umum.

Namun banyak diskusi tentang Philosophy SE (di mana saya biasanya nongkrong) beralih ke kemungkinan perhitungan "Super-Turing", dan argumen dalam filsafat pertanyaan pikiran sering bergantung pada proposisi bahwa Gereja-Turing hanyalah sebuah tesis dan ada ada beberapa proposal untuk komputasi super-Turing atau komputasi hyper.

Sumber yang paling sering dikutip untuk ini adalah artikel Stanford Encyclopedia of Philosophy (SEP) mengenai tesis Gereja-Turing .

Secara khusus artikel tersebut memiliki bagian berjudul "Kesalahpahaman tesis" , yang menyatakan sebagai berikut:

Sebuah mitos tampaknya telah muncul mengenai makalah Turing tahun 1936, yaitu bahwa ia di sana memberikan perlakuan terhadap batas-batas mekanisme dan menetapkan hasil mendasar pada efek bahwa mesin Turing universal dapat mensimulasikan perilaku mesin apa pun. Mitos telah masuk ke dalam filsafat pikiran, umumnya memberi efek merusak.

[...] Turing tidak menunjukkan bahwa mesinnya dapat menyelesaikan masalah apa pun yang dapat diselesaikan "dengan instruksi, aturan, atau prosedur yang dinyatakan secara eksplisit", juga ia tidak membuktikan bahwa mesin Turing universal "dapat menghitung fungsi apa pun yang dimiliki komputer mana pun, dengan arsitektur apa pun, dapat menghitung ". Dia membuktikan bahwa mesin universal-nya dapat menghitung fungsi apa pun yang bisa dihitung oleh mesin Turing; dan dia mengajukan, dan mengajukan argumen filosofis untuk mendukung, tesis di sini disebut tesis Turing. Tetapi sebuah tesis mengenai sejauh mana metode yang efektif - yaitu, mengenai sejauh mana prosedur dari jenis tertentu yang dapat dilakukan manusia tanpa bantuan mesin - tidak membawa implikasi mengenai sejauh mana prosedur yang dilakukan mesin. mampu melakukan, bahkan mesin yang bertindak sesuai dengan 'aturan yang dinyatakan secara eksplisit'. Untuk di antara repertoar mesin tentang operasi atom, mungkin ada yang tidak dapat dilakukan manusia tanpa bantuan mesin.

Bagian yang disebutkan di atas dan terutama bagian-bagian yang dikutip tampak jelas salah bagi saya, seolah-olah penulis bahkan tidak mendapatkan konsep mesin Turing atau apa tesis Gereja-Turing. Namun, artikel ini terus-menerus dikutip sebagai sumber oleh mereka yang menentang tesis Gereja-Turing, tidak hanya dalam SE Filsafat, tetapi bahkan oleh para filsuf yang relatif terkenal seperti Massimo Pigliucci . Alasan utama mengapa artikel tersebut memiliki bobot yang sangat besar adalah bahwa SEP dianggap sebagai sumber yang memiliki reputasi baik dalam komunitas filsafat, dan artikel-artikel di sana harus ditinjau, dan bahwa penulis artikel tersebut, Jack Copeland , adalah seorang filsuf mapan yang telah menerbitkan banyak buku. pada Turing dan AI.

Namun dari cara saya melihatnya, artikel ini pada dasarnya salah dalam presentasi tesis, reputasi sumber dan penulis tidak tahan.

Pertanyaan saya:

1. Apakah interpretasi saya terhadap tesis Church-Turing benar?

2. Bagaimana orang bisa membantah mereka yang menggunakan bagian "Kesalahpahaman" artikel itu sebagai pembenaran untuk gagasan bahwa komputasi di luar batas Turing adalah prospek yang realistis?

3. Apakah komputasi hiper dianggap serius oleh ahli teori komputabilitas arus utama, atau apakah CS setara dengan fusi dingin dan gerakan abadi?

Bidang filsafat dan CS rupanya memiliki definisi / interpretasi yang berbeda dari tesis. Dalam CS, saya percaya itu adalah standar / diterima untuk mendefinisikan tesis Gereja-Turing sebagai bagian "Kesalahpahaman" artikel "Tesis M" (di bawah pandangan sempit / duniawi). Namun, artikel itu mengklaim bahwa ini adalah definisi yang salah dari Gereja-Turing. Jadi kami tidak setuju. (Dan mari kita coba untuk menghindari memulai pertengkaran dengan mereka tentang hal itu ... bagaimanapun juga, argumen yang tidak berguna adalah keahlian mereka .)

Pendekatan yang diambil oleh para filsuf sangat disayangkan, karena orang awam rata-rata mungkin tertarik dengan tesis CS-Turing CS, bukan filosofi yang dianut dalam artikel. Jadi mereka akan mengutip artikel sambil berpikir itu merujuk pada definisi praktis / masuk akal kita, ketika tidak.

Jadi jawaban saya untuk pertanyaan spesifik Anda:

1. Ya, sejauh yang saya tahu.

2. Saya akan memberi tahu mereka bahwa artikel itu merujuk pada filosofi yang sangat terspesialisasi - definisi Church-Turing. Tetapi terlepas dari apa yang disebut tesis Gereja-Turing "benar", tesis berikut hampir secara universal diyakini di kalangan ilmuwan komputer: "Setiap mesin komputasi yang dapat digunakan yang dapat dibangun di alam semesta ini dapat disimulasikan oleh Mesin Turing".

3. Jika dengan hiperkomputasi yang Anda maksud secara fisik dimungkinkan / dapat diwujudkan, maka tidak, itu tidak dianggap serius. Tapi itu menarik untuk mempelajari model komputasi hiper meskipun mereka tidak dapat muncul di dunia nyata, dan kami melakukannya sepanjang waktu. Sebagai contoh, kami dapat mempertimbangkan Mesin Turing yang memiliki akses ke oracle yang memecahkan masalah penghentian. Objek ini dipelajari sepanjang waktu dalam teori dan tidak kontroversial, tetapi tidak ada yang percaya bahwa seseorang sebenarnya dapat dibangun.

Artikel Stanford Encyclopedia of Philosophy tampaknya kehilangan poin yang sangat penting. Tidak ada komputer ketika Turing menulis makalahnya tahun 1936. Saya percaya dia sudah memikirkan mereka, tetapi untuk menjelaskan teorinya kepada ahli matematika di jalan, yang tidak pernah bermimpi mesin komputasi yang memiliki kemampuan di luar mesin kantor yang relatif terbatas yang dibangun oleh perusahaan seperti IBM, dia harus membingkai mereka dalam hal prosedur efektif yang dilakukan oleh manusia.

Makalah Gandy "Tesis dan Prinsip-prinsip Mekanisme Gereja," dalam The Kleene Symposium (1980) menyatakan bahwa tesis Gereja-Turing tidak berlaku untuk mesin. Ini kemudian memberikan tujuan apa yang membuktikannya untuk kelas mesin yang sangat terbatas. Di antara hal-hal yang diklaim Gandy adalah bahwa tesis Church-Turing yang asli tidak memperhitungkan paralelisme.

Mesin-mesin Gandy tidak memperhitungkan kemungkinan keacakan, fisika non-mekanis, aksi di kejauhan, asinkronisitas, variabel kontinu, dan hal-hal lain yang mungkin digunakan untuk membangun mesin fisik aktual.

Jadi apakah tesis Church-Turing yang asli dimaksudkan oleh Gereja atau Turing untuk diterapkan pada mesin? Andrew Hodges memiliki makalah yang mempertimbangkan pertanyaan ini, di mana ia mengutip ulasan Gereja tentang makalah Turing:

Penulis [Turing] mengusulkan sebagai kriteria bahwa urutan angka 0 dan 1 yang tak terhingga “dapat dihitung” sehingga memungkinkan untuk membuat mesin komputasi, menempati ruang terbatas dan dengan bagian kerja dengan ukuran terbatas, yang akan menuliskan urutan ke sejumlah syarat yang diinginkan jika dibiarkan berjalan untuk waktu yang cukup lama. Demi kenyamanan, pembatasan lebih lanjut tertentu diberlakukan dalam karakter mesin, tetapi ini sifatnya yang jelas tidak menyebabkan hilangnya sifat umum — khususnya, kalkulator manusia, dilengkapi dengan pensil dan kertas dan instruksi eksplisit, dapat dianggap sebagai semacam mesin Turing.

Jadi Gereja jelas berpikir tesis Gereja-Turing diperluas ke mesin.

Di sisi lain, tampaknya tidak ada upaya yang dilakukan oleh Gereja atau Turing untuk mempertimbangkan konsekuensi fisika kuantum (atau non-elementer lainnya) dalam perhitungan, jadi itu jelas merupakan kelas mesin yang sangat terbatas yang mereka pertimbangkan.

Kutipan yang dikutip sudah benar. Mereka menyoroti perbedaan antara Tesis Gereja-Turing (pernyataan yang tidak dapat dibuktikan tentang sifat komputasi) dan keberadaan Mesin Turing Universal (teorema matematika).

Keberadaan Mesin Universal Turing adalah fakta nontrivial pada saat Turing menulis makalahnya. Saat ini, itu dianggap sepele, dan di bidang pemrograman Universal Turing Machine disebut interpreter , yaitu program yang dapat menjalankan program lain yang ditulis dalam bahasa tertentu.

Apa yang dikutip dengan tepat adalah bahwa keberadaan penafsir tidak dapat membuktikan Tesis Gereja-Turing.