Mesin teoritis yang lebih kuat dari mesin Turing

39

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

pengguna1561358
sumber
5
Pertanyaan seperti "adalah X karakteristik dari luar (mendefinisikan sic ) alam semesta?" adalah pertanyaan fisika karena fisika adalah studi tentang "hukum alam semesta". Ilmu komputer adalah tentang objek matematika yang kadang-kadang dapat diimplementasikan melalui sarana fisik.
Bakuriu
2
Saya akan merekomendasikan melihat ke "mesin super turing", terutama yang diusulkan oleh Have Siegelmann: umass.edu/newsoffice/article/… dan binds.cs.umass.edu/papers/1995_Siegelmann_Science.pdf
nobillygreen
1. Kami mohon Anda hanya menanyakan satu pertanyaan per posting. Jika Anda memiliki pertanyaan lain, Anda dapat mempostingnya secara terpisah, setelah melihat jawaban untuk ini. Juga, pertanyaan tentang karakteristik yang menentukan alam semesta kita adalah pertanyaan fisika, dan di luar topik di sini. Saya mengedit pertanyaan tambahan, untuk membantu Anda fokus pada satu pertanyaan. Anda dapat mempostingnya secara terpisah (lihat riwayat revisi untuk menemukannya lagi). 2. Penelitian apa yang telah Anda lakukan? Apa yang kamu pikirkan? Pertanyaan satu kalimat terlalu pendek. Coba edit untuk menyempurnakannya; itu akan membantu memberi Anda jawaban yang lebih baik.
DW
3. "Bisakah kita menganggap itu ...." - tidak, tentu saja tidak. Mengapa Anda berpikir bahwa Anda dapat menganggapnya? Anda tidak dapat hanya berasumsi sesuatu karena itu akan baik jika itu benar, atau sepertinya itu mungkin benar, atau karena kita tidak segera melihat alasan mengapa itu akan salah. Ilmu komputer adalah tentang bukti, bukan hanya tentang asumsi. Apa pertanyaan Anda sebenarnya?
DW

Jawaban:

26

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.

Yuval Filmus
sumber
Sebenarnya blog Scotts saya sudah ada bookmarknya. :) Pokoknya karena tesis CT masih berlaku hari ini (kecuali sesuatu terjadi saya tidak menyadari) semua yang tersisa adalah berbicara tentang definisi komputer atau mencari mesin yang entah bagaimana menyangkal CT.
user1561358
3
"Sebagaimana dibahas dalam esai ini, teori kompleksitas kini telah berkembang jauh melampaui mesin Turing deterministik, untuk menggabungkan (misalnya) mekanika kuantum, komputasi paralel dan terdistribusi, dan proses stokastik seperti evolusi Darwin." ( Mengapa Para filsuf Harus Peduli Dengan Kompleksitas Komputasi , oleh Scott Aaronson , hlm. 49)
reinierpost
1
Saya pikir juga patut dicatat bahwa komputer kuantum tidak mempercepat tugas sembarang AFAIK. Dan mereka "hanya" mempercepatnya dengan maksimum 2 ^ N di mana N adalah jumlah bit kuantum.
Semoga bermanfaat
13

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".

reinierpost
sumber
dengan "perhitungan oleh prosesor tunggal yang menjalankan langkah-langkah ketat secara berurutan tanpa gangguan eksternal", apakah maksud Anda bahwa jika komputer memiliki gangguan eksternal, atau dapat bekerja secara paralel, itu jauh lebih kuat daripada mesin turing?
kate
1
Tidak terlalu. Jika yang ingin Anda ketahui adalah pemetaan dari input hingga hingga output hingga dapat dihitung, maka menambahkan ini tidak akan memberi Anda lebih banyak kekuatan: Anda tidak akan dapat menghitung pemetaan lebih dari sebelumnya.
reinierpost
5

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. )

Π20 Alasan itu sendiri muncul dari percakapan dengan Thomas yang lain, yaitu Thomas Chust.)

Thomas Klimpel
sumber