Apakah Mesin Turing “menurut definisi” adalah mesin yang paling kuat?

Saya setuju bahwa Mesin Turing dapat melakukan "semua kemungkinan masalah matematika". Tapi itu karena itu hanya representasi mesin dari suatu algoritma: pertama lakukan ini, kemudian lakukan itu, akhirnya keluaran itu.

Maksud saya apa pun yang dapat dipecahkan dapat diwakili oleh suatu algoritma (karena itulah definisi 'dipecahkan'). Itu hanya tautologi. Saya mengatakan tidak ada yang baru di sini.

Dan dengan membuat representasi mesin dari suatu algoritma, itu juga akan menyelesaikan semua masalah yang mungkin juga bukan hal baru. Ini juga hanya tautologi. Jadi pada dasarnya ketika dikatakan bahwa Mesin Turing adalah mesin yang paling kuat, apa artinya secara efektif adalah bahwa mesin yang paling kuat adalah mesin yang paling kuat!

Definisi "paling kuat": Itu yang bisa menerima bahasa apa pun.
Definisi "Algoritma": Proses untuk melakukan apa saja. Representasi mesin "Algoritma": Mesin yang dapat melakukan apa saja.

Oleh karena itu hanya logis bahwa representasi mesin dari suatu algoritma akan menjadi mesin yang paling kuat. Apa hal baru yang diberikan Alan Turing kepada kami?

Saya setuju bahwa Mesin Turing dapat melakukan "semua masalah matematika yang mungkin".

Yah, seharusnya tidak, karena itu tidak benar. Misalnya, mesin Turing tidak dapat menentukan apakah polinomial dengan koefisien integer memiliki solusi integer ( masalah kesepuluh Hilbert ).

Apakah Mesin Turing "menurut definisi" mesin yang paling kuat?

Tidak. Kita bisa memimpikan hierarki tak terbatas dari mesin yang lebih kuat . Namun, mesin Turing adalah mesin paling kuat yang kita tahu, setidaknya pada prinsipnya, cara membuat. Namun, itu bukan definisi: tetapi kami tidak memiliki petunjuk bagaimana membangun sesuatu yang lebih kuat, atau jika itu mungkin.

Apa hal baru yang diberikan Alan Turing kepada kami?

Definisi formal algoritma. Tanpa definisi seperti itu (misalnya, mesin Turing), kami hanya memiliki definisi algoritma informal, di sepanjang baris "Prosedur yang ditentukan secara spesifik untuk menyelesaikan sesuatu." OK bagus. Tetapi langkah individual apa yang diperbolehkan untuk diambil oleh prosedur ini?

Apakah langkah dasar operasi aritmatika? Apakah menemukan gradien kurva adalah langkah? Apakah menemukan akar polinomial adalah langkah? Apakah menemukan akar bilangan bulat dari polinomial adalah langkah? Masing-masing tampaknya alami. Namun, jika Anda mengizinkan semuanya, "prosedur yang ditentukan secara spesifik" Anda lebih kuat daripada mesin Turing, yang berarti mereka dapat menyelesaikan hal-hal yang tidak dapat diselesaikan dengan algoritma. Jika Anda mengizinkan semua kecuali yang terakhir, Anda masih berada dalam ranah perhitungan Turing.

Jika kami tidak memiliki definisi formal dari algoritma, kami bahkan tidak akan dapat mengajukan pertanyaan ini. Kami tidak akan mampu untuk mendiskusikan apa algoritma dapat dilakukan, karena kita tidak akan tahu apa algoritma adalah .

Anda tidak benar ketika berulang kali membuat pernyataan tentang ini atau itu "hanya sebuah tautologi". Jadi izinkan saya untuk menempatkan klaim Anda ke dalam sedikit konteks sejarah.

Pertama-tama, Anda perlu membuat konsep yang Anda gunakan tepat. Apa masalahnya? Apa itu algoritma? Apa itu mesin? Anda mungkin berpikir ini jelas, tetapi sebagian besar dari tahun 1920-an dan 1930-an dihabiskan oleh para ahli logika yang mencoba untuk memecahkan masalah ini. Ada beberapa proposal, salah satunya adalah mesin Turing, yang merupakan yang paling sukses. Kemudian ternyata proposal lain setara dengan mesin Turing. Anda harus membayangkan era ketika kata "komputer" menandakan seseorang, bukan mesin. Anda hanya menunggangi ombak dan konsekuensi dari penemuan-penemuan cemerlang oleh pikiran-pikiran cemerlang dari seratus tahun yang lalu, tanpa menyadarinya.

Mesin Turing dijelaskan secara konkret dalam hal status, kepala, dan pita kerja. Jauh dari jelas bahwa ini menguras kemungkinan komputasi dari alam semesta yang kita tinggali. Tidak bisakah kita membuat mesin yang lebih kuat menggunakan listrik, atau air, atau fenomena kuantum? Bagaimana jika kita menerbangkan mesin Turing ke dalam lubang hitam dengan kecepatan dan arah yang tepat, sehingga dapat melakukan banyak langkah tak terhingga dalam waktu yang terbatas bagi kita? Anda tidak bisa hanya mengatakan "jelas tidak" - Anda perlu melakukan beberapa perhitungan dalam relativitas umum terlebih dahulu. Dan bagaimana jika fisikawan menemukan cara untuk berkomunikasi dan mengendalikan alam semesta paralel, sehingga kita dapat menjalankan banyak mesin Turing dalam waktu paralel?

Itu tidak peduli bahwa saat ini kita tidak bisa melakukan hal-hal ini. Yang penting, bagaimanapun, adalah Anda memahami bahwa Turing harus memikirkan apa yang secara fisik mungkin (berdasarkan pengetahuan fisika pada saat itu). Dia tidak hanya menuliskan "tautologi belaka". Jauh dari itu, ia dengan hati-hati menganalisis apa artinya komputasi dalam arti informal, kemudian ia mengusulkan model formal, dengan sangat hati-hati berpendapat bahwa model ini menangkap apa yang dipahami orang dengan "perhitungan", dan ia mendapatkan beberapa teorema penting tentangnya. Salah satu teorema ini mengatakan bahwa mesin Turing tidak dapat menyelesaikan semua masalah matematika (bertentangan dengan salah satu pernyataan salah Anda). Semua ini, dalam satu makalah, ditulis selama vaksinasi musim panas, ketika dia masih mahasiswa.adalah penemuan gagasan komputer tujuan umum modern. Setelah itu hanya masalah teknik sederhana.

Apakah itu menjawab apa yang kontribusi Turing bagi umat manusia di luar tautologi belaka? Dan apakah Anda benar-benar membaca makalahnya ?

Bahwa "apa pun yang dapat dipecahkan dapat diwakili oleh suatu algoritma" sama sekali tidak jelas.

Ini telah menjadi objek perdebatan sengit, karena Alan Turing, yang mengerjakan ulang ide-ide Gereja Alonzo, mengusulkan definisi angka yang dapat dihitung yang mengambil bentuk mesin yang Anda maksud. Yang penting, mereka bukan satu-satunya orang yang mengerjakan hal semacam ini, pada saat itu.

Kami masih menyebutnya tesis - atau dugaan - karena "apa pun yang dapat dihitung" jelas bukan objek matematika yang tepat, yang struktur dan jangkauannya dapat dipelajari dengan cara yang tidak spekulatif.

Pertama, penting untuk diingat bahwa Mesin Turing pada awalnya dirancang oleh Turing bukan sebagai model dari semua jenis komputer yang dapat direalisasikan secara fisik melainkan sebagai batas ideal untuk apa yang dapat dihitung oleh manusia yang menghitung dalam mekanis langkah-demi-langkah cara (tanpa menggunakan intuisi). Poin ini banyak disalahpahami - lihat [1] untuk penjelasan yang bagus tentang ini dan topik terkait.

Keterbatasan keterbatasan yang didalilkan oleh Turing untuk Mesin Turingnya didasarkan pada keterbatasan yang dipostulasikan dari alat sensorik manusia. Generalisasi analisis Turing untuk perangkat komputasi yang dapat direalisasikan secara fisik (dan tesis Church-Turing yang analog) tidak muncul sampai kemudian (1980) karena Robin Gandy - dengan keterbatasan berdasarkan pada hukum fisika. Seperti yang Odifreddi katakan di hlm. 51 dari [2] (Alkitab Teori Rekursi Klasik)

Mesin Turing adalah perangkat teoretis, tetapi telah dirancang dengan memperhatikan keterbatasan fisik. Secara khusus, kami telah memasukkan dalam batasan model kami yang berasal dari:

• (a) ATOMISME, dengan memastikan bahwa jumlah informasi yang dapat dikodekan dalam konfigurasi mesin apa pun (sebagai sistem hingga) dibatasi; dan

• (B) RELATIVITAS, dengan mengecualikan tindakan di kejauhan, dan membuat efek kausal menyebar melalui interaksi lokal. Gandy [1980] telah menunjukkan bahwa gagasan mesin Turing cukup umum untuk merangkum, dalam arti yang tepat, setiap perangkat komputasi memenuhi batasan yang sama.

dan pada hal. 107: (Teori umum perangkat diskrit dan deterministik)

Analisis (Gereja [1957], Kolmogorov dan Uspenskii [1958], Gandy [1980]) dimulai dari asumsi atomisme dan relativitas. Yang pertama mereduksi struktur materi menjadi sekumpulan partikel dasar hingga dimensi terbatas, dan dengan demikian membenarkan kemungkinan teoretis pembongkaran sebuah mesin ke sekumpulan konstituen dasar. Yang terakhir memaksakan batas atas (kecepatan cahaya) pada kecepatan propagasi dari perubahan sebab-akibat, dan dengan demikian membenarkan kemungkinan teoretis untuk mengurangi efek sebab-akibat yang dihasilkan dalam t instan pada daerah ruang V yang terbatas, pada tindakan yang dihasilkan oleh daerah titik-titik yang berada dalam jarak c * t dari beberapa titik V. Tentu saja, asumsi tidak memperhitungkan sistem akun yang kontinu, atau yang memungkinkan aksi-di-a-jarak yang tidak terbatas (seperti sistem gravitasi Newton).

Analisis Gandy menunjukkan bahwa PERILAKU ADALAH REKURSIF, UNTUK PERANGKAT APA PUN DENGAN TETAP TERTENTU PADA KOMPLEKSITAS KONFIGURASI YANG MUNGKINNYA (dalam arti bahwa kedua tingkat pembentukan konseptual dari konstituen, dan jumlah konstituen di setiap bagian terstruktur dari konfigurasi apa pun, dibatasi), DAN TETAP TETAP, SET DETERMINISTIK INSTRUKSI UNTUK TINDAKAN LOKAL DAN GLOBAL (yang pertama mengatakan bagaimana menentukan efek suatu tindakan pada bagian terstruktur, yang terakhir bagaimana merakit efek lokal). Selain itu, analisisnya optimal dalam arti bahwa, ketika dibuat dengan tepat, segala pelonggaran kondisi menjadi kompatibel dengan perilaku apa pun, dan dengan demikian memberikan deskripsi yang cukup dan perlu tentang perilaku rekursif.

Analisis Gandy memberikan perspektif yang sangat mencerahkan tentang kekuatan dan keterbatasan Turing Machines. Adalah bacaan yang layak untuk mendapatkan wawasan lebih lanjut tentang masalah ini. Akan tetapi, diperingatkan sebelumnya bahwa makalah Gandy 1980 [3] dianggap sebagai hal yang sulit bahkan oleh beberapa orang yang sadar. Anda mungkin terbantu untuk membaca dulu karya-karya di [4] oleh J. Shepherdson, dan A. Makowsky.

[1] Sieg, Wilfried. Prosedur mekanik dan pengalaman matematika. [pp. 71--117 dalam Matematika dan pikiran. Makalah dari Konferensi tentang Filsafat Matematika diadakan di Amherst College, Amherst, Massachusetts, 5-7 April 1991. Diedit oleh Alexander George. Komputasi Logika. Philos., Oxford Univ. Press, New York, 1994. ISBN: 0-19-507929-9 MR 96m: 00006 (Reviewer: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Teori rekursi klasik. Teori fungsi dan set bilangan alami. Dengan kata pengantar oleh GE Sacks. Studi Logika dan Yayasan Matematika, 125. North-Holland Publishing Co, Amsterdam-New York, 1989. xviii + 668 hal. ISBN: 0-444-87295-7 MR 90d: 03072 (Reviewer: Rodney G. Downey ) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. Tesis dan prinsip-prinsip Gereja untuk mekanisme. Simposium Kleene. Prosiding Simposium diadakan di University of Wisconsin, Madison, Wis., 18--24 Juni 1978. Diedit oleh Jon Barwise, H. Jerome Keisler dan Kenneth Kunen. Studi Logika dan Yayasan Matematika, 101. North-Holland Publishing Co, Amsterdam-New York, 1980. xx + 425 hlm. ISBN: 0-444-85345-6 MR 82h: 03036 (Reviewer: Douglas Cenzer) 03D10 (03A05)

[4] Mesin Turing universal: survei setengah abad. Edisi kedua. Diedit oleh Rolf Herken. Computerkultur [Budaya Komputer], II. Springer-Verlag, Vienna, 1995. xvi + 611 hlm. ISBN: 3-211-82637-8 MR 96j: 03005 03-06 (01A60 03D10 03D15 68-06)

Diskusi populer terbaik dari pertanyaan ini yang pernah saya baca adalah esai profesor MIT Scott Aaronson Who Can Name the Bigger Number? , di mana ia mengeksplorasi, antara lain, implikasi dari mesin super-Turing, mesin super-duper-Turing, dan mesin-Turing super-duper-pooper.

Tidak, TM tidak paling kuat. Dua contoh:

a) Mungkin ada mesin lain yang menghitung hasil yang sama seperti TM tetapi secara algoritmik lebih cepat (misalnya komputer kuantum menghitung faktor utama). "Lebih cepat" adalah jenis kekuatan.

b) TM tidak dapat mewakili bilangan real umum dengan presisi sempurna. Tetapi Komputer Analog (AC) mungkin dapat mewakili dan melakukan aritmatika dengan bilangan real dengan presisi sempurna. Ini akan lebih kuat daripada TM mana pun.

Tentu saja (b) mengharuskan alam semesta kita memiliki beberapa sifat kontinu (gravitasi?) Yang dapat digunakan AC untuk mewakili nilai-nilai nyata. Mungkin setiap sifat fisik, termasuk gravitasi, diukur. Tapi kita bisa berspekulasi tentang mesin di alam semesta yang berkelanjutan. Jadi TM tidak paling kuat "menurut definisi".

Jika Anda melihat kompleksitas komputasi, Mesin Turing adalah mesin yang paling kuat - karena memiliki memori tidak terbatas, dan tidak ada mesin nyata yang memilikinya. Setiap mesin nyata tidak dapat memecahkan masalah ukuran sewenang-wenang; mereka bahkan tidak bisa membaca masalah, apalagi menyelesaikannya.

Di sisi lain, jika Anda mencoba menerapkan Mesin Turing nyata, katakanlah dengan ketentuan bahwa itu berhenti dan membunyikan alarm jika kehabisan kaset, Anda akan menemukan bahwa itu akan mengambil banyak langkah lagi untuk melakukan segala jenis perhitungan daripada katakanlah mesin nyata di telepon murah, dan akan jauh lebih lambat dalam memecahkan masalah nyata. Anda juga akan menemukan bahwa menulis jawaban pada kaset bukanlah antarmuka pengguna yang sangat baik. Dan Anda akan menemukan bahwa banyak orang menggunakan komputer bukan untuk menyelesaikan masalah, tetapi untuk mengirim foto telanjang ke teman-teman mereka dan untuk menonton video kucing, dan Mesin Turing tidak ada gunanya sama sekali.