"Mesin yang paling penting tidak pernah dibina", Alan Turing dan Mesin Turing

Pengiraan ialah konsep biasa yang kebanyakan kita fahami secara intuitif. Mari kita ambil fungsi f (x) = x + 3 sebagai contoh Apabila x ialah 3, f (3) = 3 + 3. Jawapannya ialah 6, sangat mudah. Jelas sekali, fungsi ini boleh dikira. Tetapi sesetengah fungsi tidak semudah itu, dan menentukan sama ada ia boleh dikira bukanlah perkara remeh, bermakna ia mungkin tidak pernah membawa kepada jawapan muktamad.

Pada tahun 1928, ahli matematik Jerman David Hilbert dan Wilhelm Ackermann mencadangkan masalah yang dipanggil Entscheidungsproblem ("masalah keputusan"). Dari masa ke masa, soalan yang mereka ajukan akan membawa kepada definisi formal kebolehkiraan, definisi yang membolehkan ahli matematik menjawab pelbagai soalan baharu dan meletakkan asas untuk sains komputer teori.

Seorang pelajar siswazah berusia 23 tahun bernama Alan Turing mencadangkan definisi ini Dia menulis kertas mani pada tahun 1936, yang bukan sahaja memformalkan konsep pengkomputeran, tetapi juga membuktikan soalan Asas matematik mencipta asas pengetahuan untuk ciptaan itu. komputer elektronik. Visi hebat Turing adalah untuk memberikan jawapan konkrit kepada masalah pengkomputeran dalam bentuk mesin abstrak, yang kemudiannya dinamakan mesin Turing oleh penyelia kedoktorannya Alonzo Church.

Mesin Turing adalah abstrak kerana ia tidak (dan tidak boleh) wujud secara fizikal sebagai peranti ketara. Sebaliknya, ia adalah model pengiraan konseptual: jika mesin ini boleh mengira fungsi, maka fungsi itu boleh dikira.

Apabila Alan Turing mencipta mesin Turing pada tahun 1936, dia juga mencipta pengkomputeran moden.

Alan Turing dan Mesin Turingnya

Ia berfungsi seperti ini: Mesin Turing boleh membaca dan menukar simbol pada pita panjang yang tidak terhingga mengikut jadual peraturan. Pita itu terdiri daripada "sel", dan setiap sel hanya boleh menyimpan satu simbol. Mesin Turing menggunakan kepala pita untuk membaca dan menulis semula kandungan sel. Setiap peraturan dalam jadual peraturan menentukan perkara yang perlu dilakukan oleh mesin Turing berdasarkan keadaan semasa dan simbol yang dibacanya. Mesin Turing boleh memasuki keadaan akhir ("keadaan terima" atau "keadaan tolak") berdasarkan tempat ia berhenti, memutuskan untuk menerima atau menolak input. Atau mesin Turing tersangkut dalam gelung tak terhingga dan tidak pernah berhenti membaca pita itu.

Cara terbaik untuk memahami mesin Turing adalah dengan memikirkan contoh mudah seperti ini. Mari kita bayangkan bahawa mesin Turing direka untuk memberitahu kita sama ada input yang diberikan ialah nombor sifar. Kami akan memasukkan nombor 0001 dengan simbol ruang putih (#), yang bermaksud "#0001#" ialah bahagian yang berkaitan dalam pita kami.

Mesin Turing bermula dari keadaan awal, mari kita panggil ia q0, dan ia membaca sel paling kiri pita dan mencari kawasan kosong. Sebagai peraturan, apabila dalam keadaan q0, jika tanda ialah #, biarkan ia seperti sedia ada, kemudian gerakkan satu sel ke kanan dan tukar keadaan mesin kepada q1. Selepas langkah ini, mesin berada dalam keadaan q1 dan kepalanya akan membaca simbol kedua 0.

Sekarang kami mencari peraturan yang terpakai untuk syarat ini. Kami mendapati peraturan yang mengatakan, "Kekalkan keadaan q1 dan gerakkan kepala satu sel ke kanan Ini meninggalkan kami dalam kedudukan yang sama (dalam keadaan q1, bacaan masih 0), jadi kami terus bergerak ke kanan sehingga kepala." akhirnya Nombor 1 yang berbeza dibaca.

Apabila kami merujuk jadual peraturan sekali lagi, kami menemui peraturan baharu: "Jika 1 ditemui, peralihan kepada q2, iaitu keadaan penolakan." Mesin Turing berhenti berjalan dan menjawab soalan asal "Adakah 0001 sifar? ?" Jawab "Tidak".

Sebaliknya, jika input ialah "#0000#", mesin Turing akan menemui # selepas semua sifar tersebut. Apabila kita merujuk jadual peraturan, kita dapati peraturan yang mengatakan ini bermakna mesin memasuki keadaan q3, keadaan "menerima". Mesin kini menjawab "ya" kepada soalan "Adakah '0000' sifar?"

Alan Turing membantu mentakrifkan pengiraan, algoritma dan mesin Turing.

Menjawab soalan penghakiman dengan mesin abstrak

Turing menggunakan mesin abstraknya untuk membina model pengiraan untuk menjawab masalah Entscheidungs, yang secara rasmi bertanya: diberikan satu set aksiom matematik, sama ada terdapat proses mekanikal ( Iaitu, satu set arahan, hari ini kita akan memanggilnya algoritma) yang sentiasa boleh menentukan sama ada pernyataan yang diberikan adalah benar?

Andaikan kita ingin mencari algoritma untuk memberitahu kita sama ada kedudukan kepingan dalam permainan catur tertentu boleh dilaksanakan. Dalam hal ini, aksiom adalah peraturan yang mengawal pergerakan yang munasabah dalam catur. Bolehkah kita sampai ke sana dengan mengikuti urutan terhingga proses langkah demi langkah? Walaupun sesetengah kedudukan catur mungkin mengambil masa lebih lama daripada jangka hayat kami untuk dianalisis, algoritma mungkin menjana semua kedudukan yang mungkin dan membandingkannya satu demi satu dengan input, algoritma sedemikian wujud dalam permainan catur. Oleh itu, kami mengatakan bahawa catur adalah "boleh diputuskan".

Walau bagaimanapun, pada tahun 1936, ahli matematik Amerika Church dan Turing menggunakan kaedah yang berbeza untuk membuktikan bahawa "tiada kaedah umum yang boleh menyelesaikan setiap contoh masalah Entscheidungs ​​​​Sebagai contoh, beberapa permainan seperti John Conway's Game of Kehidupan tidak dapat ditentukan: tiada algoritma boleh menentukan sama ada corak tertentu akan muncul daripada corak awal.

Turing menunjukkan bahawa fungsi boleh dikira jika terdapat algoritma yang boleh melaksanakan tugas yang diperlukan. Pada masa yang sama, beliau juga menunjukkan bahawa algoritma adalah proses yang boleh ditakrifkan oleh mesin Turing. Oleh itu, fungsi boleh dikira ialah fungsi yang boleh dikira oleh mesin Turing. Ini kelihatan seperti cara bulat untuk menentukan kebolehkiraan, tetapi ini adalah yang terbaik yang kami ada.

Michael Sipser, seorang saintis komputer teori di MIT, berkata: "Bukannya anda boleh memilih untuk mentakrifkannya dengan cara lain. Saya fikir orang ramai bersetuju bahawa tesis Church-Turing mencadangkan bahawa algoritma Konsep tidak formal ialah apa mana-mana model pengiraan yang munasabah boleh dilakukan oleh ahli matematik lain telah mencadangkan model pengiraan yang berbeza, walaupun secara dangkal, sebenarnya adalah sama: mereka boleh melakukan apa yang boleh dilakukan oleh mesin Turing dan sebaliknya.

Hanya beberapa tahun selepas ahli falsafah, ahli logik, dan ahli matematik Kurt Gödel menunjukkan bahawa matematik tidak lengkap, Church dan Turing juga menunjukkan bahawa masalah tertentu dalam matematik diselesaikan dengan lembaran kerja ini tidak dapat diputuskan. Tidak kira betapa rumitnya algoritma itu, ia tidak dapat memberitahu kami sama ada jawapannya adalah ya atau tidak. Kedua-dua peristiwa itu adalah tamparan hebat kepada Hilbert, yang berharap bahawa matematik akan memberikan jawapan yang mudah dan ideal. Tetapi itu tidak buruk: jika terdapat penyelesaian umum kepada Entscheidungsproblem, ini bermakna semua masalah dalam matematik boleh dikurangkan kepada pengiraan mekanikal yang mudah.

Mesin Turing Universal dan Probabilistik

Selain menjawab soalan asas ini, mesin Turing juga secara langsung mempengaruhi perkembangan komputer moden melalui varian yang dipanggil Mesin Turing Universal. Ia adalah mesin Turing khas yang boleh mensimulasikan sebarang input daripada mesin Turing lain. Ia boleh membaca huraian (dan peraturan dan pita input) mesin Turing lain dan mensimulasikan kelakuannya pada pita inputnya sendiri, menghasilkan output yang sama seperti mesin simulasi, sama seperti komputer hari ini boleh membaca sebarang program dan melaksanakannya Sama.

Pada tahun 1945, ahli matematik Hungary-Amerika, saintis komputer, dan ahli fizik John von Neumann mencadangkan seni bina komputer - seni bina von Neumann, yang menjadikan konsep mesin Turing universal menjadi mesin Nyata menjadi mungkin.

Apabila ahli sains komputer teori Universiti Princeton Sanjeev Arora mengajar konsep ini, dia menekankan gambaran falsafah yang lebih luas. Dia berkata, "Terdapat dua konsep universal, satu ialah ia boleh menjalankan mana-mana mesin Turing yang lain, tetapi konsep lain yang lebih besar ialah ia boleh menjalankan apa-apa pengiraan yang anda buat di alam semesta dalam fizik klasik Di dunia, sebarang proses fizikal boleh dimodelkan atau disimulasikan menggunakan algoritma, dan algoritma boleh disimulasikan oleh mesin Turing.

Satu lagi varian yang patut diberi perhatian dan semakin berguna ialah mesin Turing yang berkemungkinan. Tidak seperti mesin Turing konvensional, yang mempunyai respons yang jelas untuk setiap input, mesin Turing yang berkemungkinan boleh membuat berbilang respons berdasarkan kebarangkalian. Ini bermakna ia boleh menghasilkan hasil yang berbeza untuk input yang sama pada titik masa yang berbeza. Ia juga menghairankan bahawa untuk beberapa masalah strategi kebarangkalian ini lebih berkesan daripada pendekatan deterministik semata-mata. Konsep mesin Turing probabilistik telah terbukti sangat berguna dalam bidang seperti pengoptimuman dan pembelajaran mesin.

Mesin abstrak ini mungkin merupakan bukti terbaik bahawa bertanya soalan asas boleh menjadi salah satu perkara paling berguna yang boleh dilakukan oleh saintis.

Atas ialah kandungan terperinci "Mesin yang paling penting tidak pernah dibina", Alan Turing dan Mesin Turing. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!