Tesis Gereja-Turing dan kekuatan komputasi jaringan saraf

Tesis Gereja-Turing menyatakan bahwa segala sesuatu yang secara fisik dapat dihitung, dapat dihitung pada Mesin Turing. Makalah "Komputasi analog melalui jaringan saraf" (Siegelmannn dan Sontag, Theoretical Computer Science , 131: 331-360, 1994; PDF ) mengklaim bahwa jaring saraf dari bentuk tertentu (pengaturannya disajikan dalam makalah) lebih kuat. Para penulis mengatakan bahwa, dalam waktu eksponensial, model mereka dapat mengenali bahasa yang tidak dapat diperhitungkan dalam model mesin Turing.

Bukankah ini bertentangan dengan tesis Church-Turing?

Tidak, ini masih konsisten dengan tesis Church-Turing, model mereka dilengkapi dengan bilangan real asli (seperti dalam elemen sewenang-wenang ), yang hampir secara langsung memperluas kekuatan di luar Turing Machine. Sebenarnya, judul 1.2.2 adalah "Arti dari bobot nyata (tidak dapat dihitung)", di mana mereka mendiskusikan mengapa model mereka dibuat untuk memasukkan komponen yang tidak dapat dihitung.$\mathbb{R}$

Sebenarnya ada banyak model komputasi yang melebihi kekuatan Turing Machines (qv Hypercomputation ). Tangkapannya adalah tidak satu pun dari ini yang tampaknya dapat dibangun di dunia nyata (tapi mungkin di dunia - maaf, tidak bisa menahan)$\mathbb{R}$

Untuk sedikit memperluas jawaban Luke , secara fisik membangun jaringan saraf untuk menyelesaikan bahasa apa pun membutuhkan pembuatan komponen elektronik dengan resistensi yang sangat akurat dan seterusnya. Ini tidak mungkin, dalam berbagai cara:

1. $\mathrm{2\,\Omega}$

2. Perubahan resistensi dengan suhu dan arus yang mengalir melalui resistor akan mengubah suhu.

3. Bahkan seandainya Anda mengenal seorang insinyur / penyihir elektronik yang dapat menghasilkan resistor dengan nilai tepat apa pun yang Anda pilih dan yang tidak mengubah resistansi terhadap suhu, menyiapkan mesin Anda untuk memutuskan bahasa yang tidak dapat diperhitungkan akan membutuhkan nilai resistansi yang tidak dapat diperhitungkan. Jadi tidak mungkin Anda benar-benar dapat memberi tahu insinyur elektronik / tukang sihir Anda berapa nilai resistansi yang Anda butuhkan.

Jadi, meskipun, pada prinsipnya, mesin ini dapat memutuskan bahasa apa pun, mereka tidak melanggar Gereja – Turing karena mereka tidak dapat dibangun secara fisik.

Anda mungkin ingin terlibat dalam beberapa aturan hukum dan mengklaim bahwa seseorang dapat memberikan Anda salah satu dari mesin ini dan berkata, "Hei, lihat, mesin ini kebetulan memiliki nilai resistansi yang tepat untuk menyelesaikan masalah penghentian!" Namun, mereka tidak memiliki cara untuk membuktikan klaim ini, karena mereka tidak dapat mengukur komponen hingga presisi yang tak terbatas, sehingga yang terbaik yang dapat mereka klaim dengan justifikasi adalah "Saya menguji ini pada beberapa input yang terbatas dan dengan benar memutuskan masalah penghentian pada input tersebut. " Nah, setiap himpunan terbatas masalah penghentian sudah Turing-decidable sehingga tidak ada yang menarik.