Mesin teoritis yang lebih kuat dari mesin Turing

Apakah ada mesin teoritis yang melebihi kemampuan mesin Turing di setidaknya beberapa daerah?

Tesis Gereja – Turing (dalam satu formulasi) menyatakan bahwa segala sesuatu yang dapat dihitung secara fisik juga dapat dihitung pada mesin Turing. Dengan asumsi Anda percaya tesis ini, dan mengingat bahwa Anda tertarik pada fungsi-fungsi yang dapat dikomputasi oleh mesin tersebut (dan tidak dalam, katakanlah, komputasi interaktif), maka tidak ada komputasi hiper mungkin.

Tesis Church-Turing hanya menyangkut dirinya sendiri dengan apa yang dapat dihitung, tetapi tidak dengan efisiensi perhitungan. Diketahui bahwa mesin Turing tidak begitu efisien, walaupun mereka mensimulasikan secara polinomi komputer klasik. Komputer kuantum diyakini secara eksponensial lebih efisien daripada mesin Turing. Dalam pengertian ini, Anda bisa mengalahkan mesin Turing (jika Anda hanya bisa membangun komputer kuantum yang dapat diskalakan).

Scott Aaronson mungkin memiliki lebih banyak bicara tentang ini - saya akan membiarkan Anda mencari sendiri.

Ya, ada mesin teoretis yang melebihi mesin Turing dalam kekuatan komputasi, seperti mesin Oracle dan mesin Turing waktu tak terbatas . Kata kunci yang harus Anda masukkan ke Google adalah hiperkomputasi .

Tesis Gereja – Turing tidak perlu dianggap sebagai artikel iman; mungkin lebih masuk akal untuk menganggapnya sebagai menyatakan deskripsi, definisi , dari apa yang kita maksud dengan istilah "perhitungan", dan itu juga merupakan gagasan sempit tentang perhitungan, juga: perhitungan dengan prosesor tunggal menjalankan langkah-langkah yang secara ketat berurutan tanpa eksternal gangguan. Aspek-aspek perhitungan tertentu yang perlu kita pertimbangkan tidak tercakup oleh gagasan ini, dan banyak potongan tambahan teori matematika telah dikembangkan dalam ilmu komputer untuk mengatasi masalah tersebut.

Jadi tesis Gereja – Turing bukanlah karakteristik yang menentukan dari alam semesta kita, tetapi juga merupakan karakteristik yang menentukan dari cara tertentu dalam melakukan hal-hal tertentu di alam semesta kita.

Dalam hal ini, dapat disamakan dengan geometri Euclidean. Apakah alam semesta kita secara inheren Euclidean? Mengapa metode kami mengukur tanah dibatasi oleh prinsip-prinsipnya? Tidak bisakah kita memiliki hypergeometry yang memungkinkan pengukuran tanah yang lebih kuat? Jawabannya adalah: kita bisa dan kita lakukan, tetapi kita tidak selalu menyebut hasilnya "pengukuran tanah" atau "geometri".

Demikian pula, teori dan praktik kami tentang perhitungan melampaui apa yang dapat dijelaskan mesin Turing (misalnya ada proses kalkulus untuk menggambarkan sistem bersamaan), tetapi kami tidak perlu menyebut ekstensi itu "komputasi".

Salah satu kelemahan teoritis dari mesin Turing adalah prediktabilitasnya. Lawan yang kuat dan mahatahu bisa mengeksploitasi kelemahan ini saat bermain gim melawan mesin Turing. Jadi jika mesin teoretis memiliki akses ke sumber acak yang tidak dapat diprediksi lawannya (dan bisa menyembunyikan keadaan internalnya dari lawannya), maka mesin teoretis ini akan lebih kuat daripada mesin Turing.

Masalah dengan jenis mesin teoretis dalam kehidupan nyata bukanlah apakah sumber acak adalah acak sempurna atau tidak (dengan asumsi itu adalah acak sempurna adalah idealisasi tidak berbahaya), tetapi kita tidak pernah bisa yakin apakah kita berhasil menyembunyikan internal kita negara dari lawan kita. Jadi dalam kasus konkret, orang tidak pernah bisa memastikan apakah itu sah untuk mengidealisasi contoh situasi saat ini dengan mesin seperti itu. Ini hanya sedikit lebih baik daripada situasi untuk sebagian besar jenis hiperkomputasi, di mana tidak jelas bagi saya situasi ideal mana yang harus dimodelkan oleh mereka (saya pernah menjawab: Jadi saya perlu beberapa jenis mesin ajaib yang tahu segalanya untuk menyelesaikan "RE", Saya tidak tahu bahwa mesin seperti itu ada. )

$\Pi_2^0$ Alasan itu sendiri muncul dari percakapan dengan Thomas yang lain, yaitu Thomas Chust.)