Sampai saat ini, mudah bagi kita untuk mengacu pada pengalaman programmer ketika berbicara tentang algoritma, program, interpreter, eksekusi langkah demi langkah, dll. Hal ini memungkinkan kami untuk mengabaikan detail konstruksi algoritma tertentu dengan dalih bahwa pembaca akan dengan mudah memulihkannya (atau setidaknya percaya bahwa tidak setiap pembaca dalam hidupnya menulis penerjemah Pascal dalam Pascal).

Namun dalam beberapa kasus hal ini tidak cukup. Misalkan, kita ingin membuktikan keragu-raguan algoritmik suatu masalah, yang definisinya tidak menjelaskan apa pun tentang program (di bagian ini, misalnya, kita akan membuktikan keragu-raguan masalah persamaan kata dalam semigrup yang ditentukan oleh generator dan relasi). Biasanya dilakukan seperti ini. Kami menunjukkan bahwa masalah penghentian mengurangi masalah ini. Untuk melakukan ini, kami memodelkan pengoperasian algoritma arbitrer dalam kaitannya dengan masalah yang sedang dipertimbangkan (artinya akan jelas dari contoh di bawah). Pada saat yang sama, penting bagi kami untuk mendefinisikan algoritma sesederhana mungkin.

Jadi rencana kami adalah ini. Kita akan mendeskripsikan kelas mesin yang dapat didefinisikan dengan cukup sederhana (dapat dipilih dengan berbagai cara; kita akan menggunakan apa yang disebut mesin Turing), kemudian mendeklarasikan bahwa setiap fungsi yang dapat dihitung dapat dihitung pada mesin tersebut, dan kemudian menunjukkan bahwa pertanyaan tentang menghentikan mesin Turing dapat direduksi menjadi pertanyaan tentang persamaan kata dalam semigrup.

Alasan lain mengapa model komputasi sederhana itu penting (ada banyak jenis mesin Turing, mesin alamat, dll.) terkait dengan teori kompleksitas komputasi, ketika kita mulai tertarik pada waktu tunggu program. Namun pertanyaan ini melampaui teori algoritma klasik.

Mesin Turing: definisi

Mesin turing memiliki tak terhingga di kedua arah tape, dibagi menjadi kotak ( sel). Setiap sel dapat berisi beberapa simbol dari himpunan terbatas tetap (untuk mesin tertentu) yang disebut alfabet dari mesin ini. Salah satu karakter alfabet disorot dan disebut "spasi"; diasumsikan bahwa awalnya seluruh pita kosong, yaitu diisi spasi.

Mesin Turing dapat mengubah isi kaset menggunakan pembaca dan penulis khusus. kepala, yang bergerak sepanjang rekaman itu. Setiap saat kepala berada di salah satu sel. Mesin Turing menerima informasi dari kepala tentang simbol apa yang dilihatnya, dan bergantung pada ini (dan pada keadaan internalnya) memutuskan apa yang harus dilakukan, yaitu simbol mana yang akan ditulis di sel saat ini dan ke mana harus pindah setelah itu (kiri, benar, atau tetap di lokasi). Pada saat yang sama, keadaan internal mesin juga berubah (kami berasumsi bahwa mesin, tidak termasuk rekamannya, memiliki memori yang terbatas, yaitu sejumlah keadaan internal yang terbatas). Kita juga perlu menyepakati di mana kita memulai dan kapan kita menyelesaikan pekerjaan.

Jadi, untuk mendefinisikan mesin Turing, Anda perlu menentukan objek berikut:

Tabel transisi disusun sebagai berikut: untuk setiap pasangan ditunjukkan tripel. Disini yang bergeser adalah salah satu angka -1 (ke kiri), 0 (di tempat) dan 1 (ke kanan). Jadi, tabel transisi adalah fungsi bertipe S x A -> S x A x (-1,0,1) yang didefinisikan pada pasangan yang keadaannya belum final.

Masih menjelaskan perilaku mesin Turing. Setiap saat ada beberapa konfigurasi, terdiri dari isi rekaman (secara formal, isi rekaman adalah pemetaan sembarang Z -> A), posisi kepala saat ini (beberapa bilangan bulat) dan keadaan mesin saat ini (elemen S). Transformasi konfigurasi ke konfigurasi berikutnya terjadi sesuai dengan aturan alami: kita melihat di tabel apa yang perlu dilakukan untuk keadaan tertentu dan untuk simbol tertentu, yaitu, kita mengetahui keadaan baru mesin, mengubah simbol ke yang ditentukan lalu gerakkan kepala ke kiri, kanan atau biarkan di tempatnya. Terlebih lagi, jika keadaan baru tersebut merupakan salah satu keadaan terakhir, maka pengoperasian mesin akan berakhir. Masih disepakati bagaimana kami memberikan informasi pada input mesin dan apa yang dianggap sebagai hasil kerjanya. Kami berasumsi bahwa alfabet mesin, selain spasi, berisi karakter 0 dan 1 (dan mungkin beberapa karakter lainnya). Input dan output mesin akan berupa rangkaian nol dan satu yang terbatas (kata biner). Kata masukan ditulis pada pita kosong, kepala mesin ditempatkan di sel pertama, mesin dibawa ke keadaan awal dan dihidupkan. Jika mesin berhenti, hasilnya adalah kata biner, yang dapat dibaca mulai dari posisi kepala dan bergerak ke kanan (hingga muncul karakter selain 0 dan 1).

Jadi, setiap mesin Turing mendefinisikan beberapa fungsi parsial pada kata-kata biner. Wajar jika memanggil semua fungsi tersebut dapat dihitung pada mesin Turing.

Mesin Turing: diskusi

Tentu saja, definisi kami mengandung banyak detail spesifik yang dapat diubah. Misalnya saja, sebuah kaset hanya bisa tidak ada habisnya dalam satu arah. Anda bisa memberi mobil itu dua pita. Kita dapat menganggap bahwa mesin dapat menulis karakter baru atau memindahkannya, namun tidak keduanya. Anda dapat membatasi alfabet, dengan mempertimbangkan, katakanlah, alfabet tersebut harus memiliki tepat 10 karakter. Anda dapat meminta agar pada akhirnya tidak ada apa pun di rekaman itu kecuali hasil pekerjaan (sel yang tersisa harus kosong). Semua perubahan di atas dan banyak perubahan lainnya tidak mengubah kelas fungsi yang dapat dihitung pada mesin Turing. Tentu saja, ada juga beberapa perubahan yang tidak berbahaya. Misalnya, jika Anda melarang mobil bergerak ke kiri, hal ini akan mengubah keadaan secara radikal; pada dasarnya, rekaman itu akan menjadi tidak berguna, karena rekaman lama tidak dapat lagi dikembalikan.

Bagaimana Anda mengetahui perubahan mana yang tidak berbahaya dan mana yang tidak? Tampaknya, beberapa pengalaman dalam pemrograman praktis pada mesin Turing diperlukan di sini, setidaknya sedikit. Setelah ini, Anda sudah dapat membayangkan kemampuan mesin tanpa menuliskan keseluruhan program, tetapi hanya dipandu oleh deskripsi perkiraan. Sebagai contoh, kita akan mendeskripsikan mesin yang menggandakan kata masukan (menghasilkan kata XX jika masukannya adalah kata X).

Jika mesin melihat spasi (kata masukan kosong), mesin berhenti bekerja. Jika tidak, ia akan mengingat karakter saat ini dan memberi tanda (dalam alfabet, selain karakter 0 dan 1, juga akan ada “varian yang ditandai” dan ). Dia kemudian berpindah ke kanan ke sel kosong, setelah itu dia menulis salinan simbol yang dihafal di sana. Dia kemudian bergerak ke kiri sampai ditandai; Setelah mengubur dirinya dalam tanda tersebut, dia bergerak mundur dan mengingat karakter berikutnya, dan seterusnya, hingga dia menyalin keseluruhan kata.

Dengan memiliki pengalaman tertentu, Anda dapat melihat di balik semua frasa ini bagian spesifik dari program mesin Turing. Misalnya, kata “mengingat simbol dan bergerak ke kanan” berarti ada dua kelompok keadaan, satu untuk situasi ketika angka nol diingat, yang lain ketika angka satu diingat, dan dalam masing-masing kelompok terjadi pergerakan ke angka nol. kanan diprogram ke sel kosong pertama.

Dengan sedikit lebih banyak pengalaman, Anda dapat memahami bahwa ada kesalahan dalam deskripsi ini; tidak ada mekanisme untuk berhenti ketika seluruh kata disalin, karena salinan karakter tidak berbeda dengan karakter kata aslinya. Cara memperbaiki kesalahan juga jelas: Anda perlu menulis karakter khusus dan sebagai salinan, dan pada tahap terakhir, menghapus semua tanda.

77 . Tunjukkan bahwa fungsi pembalikan, yang membalikkan sebuah kata, dapat dihitung dengan mesin Turing.

Contoh lain dari penalaran informal: mari kita jelaskan mengapa tidak mungkin menggunakan karakter tambahan selain 0, 1 dan karakter kosong. Misalkan ada mesin dengan alfabet besar yang terdiri dari N karakter. Mari kita buat mesin baru yang akan mensimulasikan pengoperasian mesin lama, tetapi setiap sel mesin lama akan berhubungan dengan blok k sel mesin baru. Ukuran blok (angka k) akan ditetapkan sehingga di dalam blok semua karakter alfabet besar dapat dikodekan dengan nol dan satu. Karakter asli 0 , 1 , dan blank akan dikodekan sebagai 0 diikuti oleh (k-1) karakter kosong, 1 diikuti oleh (k-1) karakter kosong, dan sekelompok k karakter kosong. Pertama, Anda perlu memindahkan huruf-huruf dari kata masukan sejauh k, yang dapat dilakukan tanpa simbol tambahan (saat Anda mencapai huruf terluar, pindahkan, lalu saat Anda mencapai huruf berikutnya, pindahkan dan huruf terluar. satu, dan seterusnya); Anda hanya perlu memahami bahwa Anda dapat mengidentifikasi akhir kata sebagai posisi yang diikuti oleh lebih dari k karakter kosong. Jelasnya, dalam proses ini kita harus menyimpan sejumlah informasi yang terbatas dalam memori, sehingga hal ini mungkin dilakukan. Setelah ini, sudah dimungkinkan untuk mensimulasikan pengoperasian mesin asli langkah demi langkah, dan untuk ini, memori yang terbatas (e sejumlah negara yang terbatas) juga cukup, karena hanya sebagian kecil dari kepala mesin yang disimulasikan adalah penting bagi kami. Terakhir, kita perlu mengompres kembali hasilnya.

Untuk mengakhiri diskusi, kami menyajikan argumen yang dijanjikan di atas yang mendukung fakta bahwa setiap fungsi yang dapat dihitung dapat dihitung pada mesin Turing. Misalkan ada fungsi yang bisa dihitung seseorang. Pada saat yang sama, dia secara alami harus menggunakan pensil dan kertas jumlah informasi jumlah yang dapat dia simpan “dalam pikirannya” terbatas. Kami berasumsi bahwa dia menulis pada lembaran kertas terpisah. Selain lembaran saat ini, ada tumpukan kertas di sebelah kanan dan tumpukan di sebelah kiri; Anda dapat meletakkan lembar saat ini ke salah satu lembar tersebut, setelah menyelesaikan pekerjaannya, dan mengambil lembar berikutnya dari tumpukan lainnya. Seorang pria memiliki pensil dan penghapus. Karena huruf-huruf yang sangat kecil tidak terlihat, jumlah keadaan lembaran yang dapat dibedakan dengan jelas adalah terbatas, dan kita dapat berasumsi bahwa pada setiap saat satu huruf dari suatu alfabet yang terbatas (walaupun sangat besar) ditulis pada lembaran tersebut. Seseorang juga memiliki ingatan yang terbatas, sehingga keadaannya merupakan elemen dari suatu himpunan yang terbatas. Dalam hal ini, Anda dapat membuat tabel yang di dalamnya tertulis bagaimana pekerjaannya pada lembar dengan konten tertentu, dimulai dalam keadaan tertentu, akan berakhir (apa yang akan ada di lembar itu, dalam keadaan apa orang tersebut berada. dan dari bungkus mana lembar berikutnya akan diambil). Sekarang jelas bahwa tindakan manusia sama persis dengan pengoperasian mesin Turing dengan alfabet yang besar (tetapi terbatas) dan sejumlah keadaan internal yang besar (tetapi terbatas).

Perkenalan

Pada tahun 1936, Alan Turing mengusulkan eksekutor universal abstrak untuk memperjelas konsep suatu algoritma. Keabstrakannya terletak pada kenyataan bahwa ia mewakili konstruksi komputasi logis, dan bukan mesin komputasi nyata. Istilah "pemain universal" berarti bahwa pemain tertentu dapat meniru pemain lainnya. Misalnya, operasi yang dilakukan oleh komputer nyata dapat disimulasikan pada pelaksana universal. Selanjutnya, desain komputasi yang ditemukan oleh Turing disebut mesin Turing.

Tujuan dari tugas mata kuliah ini adalah untuk membuat program yang mengimplementasikan mesin Turing dalam bahasa pemrograman fungsional Haskell. Sebagai contoh, kita akan menerapkan mesin Turing yang dirancang untuk mengalikan angka desimal dengan 2.

Untuk mencapai tujuan ini, perlu untuk menyelesaikan tugas-tugas berikut: mempelajari prinsip-prinsip pengoperasian mesin Turing, strukturnya, mempertimbangkan masalah yang tidak dapat diselesaikan secara algoritmik, memilih struktur data, menjelaskan fungsi yang diterapkan, dan juga memberikan contoh program. .

Ketentuan dasar mesin Turing

Mesin Turing mendapatkan namanya dari matematikawan Inggris Alan Turing, yang pada tahun 1937 mengusulkan metode untuk menentukan algoritma secara formal menggunakan beberapa mesin abstrak. Inti dari pekerjaan ini adalah sebagai berikut. Ada pita yang berpotensi tak terbatas, dibagi menjadi sel-sel, yang masing-masing dapat berisi satu karakter dari beberapa alfabet terbatas. Mesin Turing memiliki kepala baca/tulis yang memungkinkan Anda membaca karakter di sel saat ini, menulis karakter ke sel, dan memindahkan kepala ke kiri atau kanan ke sel yang berdekatan. Mesin beroperasi secara terpisah, dalam siklus, dan pada setiap siklus, mesin berada dalam salah satu keadaan yang mungkin, yang jumlahnya terbatas. Untuk setiap pasangan (keadaan, simbol yang diamati), triple didefinisikan (karakter sedang ditulis, gerakan kepala, keadaan baru). Sebelum pengoperasian dimulai, mesin Turing berada dalam keadaan awal, dan kepala baca-tulis memindai sel paling kiri yang tidak kosong pada pita. Jadi, saat meninjau simbol berikutnya, mesin menulis simbol baru (mungkin simbol yang sama), menggerakkan kepala ke kiri, ke kanan, atau tetap di tempatnya dan masuk ke keadaan baru atau tetap dalam keadaan yang sama.

Mesin Turing terdiri dari tiga bagian: pita, kepala baca (tulis) dan perangkat logika, seperti yang ditunjukkan dengan jelas pada Gambar 1.

Rekaman itu bertindak sebagai memori eksternal. Itu dianggap tidak terbatas (infinite). Hal ini saja menunjukkan bahwa mesin Turing adalah perangkat model, karena tidak ada perangkat nyata yang dapat memiliki memori tak terbatas.

Gambar 1 - Rangkaian mesin turing

Mesin Turing beroperasi dalam alfabet terbatas sembarang A = (_, a1…an) - alfabet ini disebut eksternal. Ini berisi karakter khusus - _, disebut tanda kosong - mengirimkannya ke sel mana pun akan menghapus karakter yang sebelumnya ada di sana dan membiarkan sel kosong. Hanya satu karakter yang dapat ditulis ke setiap sel rekaman. Informasi yang disimpan dalam rekaman itu diwakili oleh urutan terbatas karakter alfabet eksternal selain karakter kosong.

Kepala selalu terletak di atas salah satu sel pita. Pekerjaan terjadi dalam siklus (langkah). Sistem perintah yang dijalankan oleh kepala sangatlah sederhana: pada setiap siklus jam, ia mengganti tanda di sel ai yang diamati dengan tanda aj. Dalam hal ini, kombinasi dimungkinkan:

1) aj = ai - berarti tanda pada sel yang diamati tidak berubah;

2) ai? _, аj = _ - tanda yang disimpan di dalam sel diganti dengan yang kosong, mis. dihapus;

3) ai = _, aj ? _ - karakter kosong diganti dengan karakter tidak kosong (dengan nomor j dalam alfabet), mis. sebuah tanda dimasukkan;

4) ai? ya? _ - berhubungan dengan mengganti satu karakter dengan karakter lainnya.

Dengan demikian, mesin Turing mengimplementasikan sistem perintah pemrosesan informasi yang sangat sederhana. Sistem perintah pemrosesan ini juga dilengkapi dengan sistem perintah yang sangat sederhana untuk memindahkan pita: satu sel ke kiri, satu sel ke kanan dan tetap di tempatnya, mis. Sebagai hasil dari eksekusi perintah, alamat sel yang dipantau dapat berubah menjadi 1 atau tetap tidak berubah.

Namun, meskipun pergerakan sebenarnya dari rekaman itu terjadi, pergerakan kepala relatif terhadap bagian yang dilihat biasanya dipertimbangkan. Oleh karena itu, perintah untuk menggeser pita ke kiri diberi tanda R (Kanan), perintah untuk menggeser ke kanan adalah L (Kiri), dan tidak ada pergeseran yang diberi tanda S (Stop). Kita akan berbicara secara khusus tentang menggeser kepala dan menganggap R, L dan S sebagai perintah untuk pergerakannya.

Sifat dasar dari perintah-perintah ini berarti bahwa jika diperlukan untuk mengakses konten sel tertentu, itu hanya ditemukan melalui rantai pergeseran individu oleh satu sel. Tentu saja, ini secara signifikan memperpanjang proses pemrosesan, tetapi ini memungkinkan Anda melakukannya tanpa memberi nomor pada sel dan menggunakan perintah untuk menuju ke alamat, mis. mengurangi jumlah langkah yang benar-benar mendasar, yang penting dari sudut pandang teoretis.

Pemrosesan informasi dan pemberian perintah untuk menulis tanda, serta menggeser pita pada mesin Turing, dilakukan oleh perangkat logika (LU). LU dapat berada dalam salah satu keadaan yang membentuk himpunan berhingga dan dilambangkan dengan Q =(q1...qm, q0), dan keadaan q0 berhubungan dengan penyelesaian pekerjaan, dan q1 adalah keadaan awal (awal) . Q bersama dengan tanda R, L, S membentuk alfabet internal mesin. LU memiliki dua saluran masukan (ai, qi) dan tiga saluran keluaran (ai+1, qi+1, Di+1). Diagram LU mesin Turing ditunjukkan pada Gambar 2.

Gambar 2 - Diagram LU mesin Turing

Perlu dipahami rangkaiannya sebagai berikut: pada siklus i, tanda dari sel yang sedang dilihat (ai) disuplai ke salah satu input LU, dan tanda yang menunjukkan keadaan LU saat ini (qi) disuplai. ke masukan lainnya. Bergantung pada kombinasi tanda yang diterima (ai, qi) dan aturan pemrosesan yang ada, LU menghasilkan dan mengirimkan tanda baru (ai+1) ke sel yang diamati melalui saluran keluaran pertama, mengeluarkan perintah untuk menggerakkan kepala (Di +1 dari R, L dan S), dan juga memberikan perintah untuk transisi ke keadaan berikutnya (qi+1). Jadi, langkah (siklus) dasar pengoperasian mesin Turing adalah sebagai berikut: kepala membaca simbol dari sel yang dipantau dan, bergantung pada statusnya dan simbol yang dibaca, menjalankan perintah yang menentukan simbol mana yang akan ditulis ( atau menghapus) dan gerakan apa yang harus dilakukan. Pada saat yang sama, kepala memasuki keadaan baru. Diagram operasi mesin tersebut ditunjukkan pada Gambar 3.

Gambar 3 - Diagram fungsi mesin Turing

Diagram ini mencerminkan pembagian memori menjadi eksternal dan internal. Yang eksternal disajikan, seperti yang ditunjukkan, dalam bentuk pita tak berujung - ini dirancang untuk menyimpan informasi yang dikodekan dalam simbol alfabet eksternal. Memori internal diwakili oleh dua sel untuk menyimpan perintah berikutnya selama siklus jam saat ini: keadaan berikutnya (qi+1) ditransfer ke Q dari LU dan disimpan, dan perintah shift (Di+1) disimpan di D . Dari Q, melalui jalur umpan balik, qi+1 memasuki LU, dan dari D, perintah dikirim ke aktuator, yang, jika perlu, menggerakkan pita satu posisi ke kanan atau kiri.

Aturan umum cara kerja mesin Turing dapat direpresentasikan dengan notasi berikut: qi aj > qi" aj" Dk, yaitu. setelah melihat simbol aj oleh kepala dalam keadaan qi, simbol aj ditulis ke dalam sel, kepala masuk ke keadaan qi, dan pita membuat gerakan Dk. Untuk setiap kombinasi qi aj terdapat tepat satu aturan transformasi (tidak ada aturan hanya untuk q0, karena mesin berhenti setelah memasuki keadaan ini). Ini berarti bahwa blok logika mengimplementasikan fungsi yang menghubungkan setiap pasangan sinyal masukan qi aj dengan satu dan hanya satu tiga kali lipat sinyal keluaran qi "aj" Dk - ini disebut fungsi logika mesin dan biasanya direpresentasikan dalam bentuk sebuah tabel (diagram fungsional mesin), kolom-kolomnya ditandai dengan simbol negara, dan garis-garisnya adalah tanda-tanda alfabet eksternal. Jika terdapat n tanda alfabet luar, dan jumlah status LU adalah m, maka jumlah total aturan transformasinya adalah n×m.

Mesin Turing tertentu ditentukan dengan menghitung elemen himpunan A dan Q, serta fungsi logis yang diimplementasikan LU, yaitu. seperangkat aturan transformasi. Jelas bahwa terdapat banyak sekali himpunan A, Q dan fungsi logika yang berbeda, mis. dan ada juga mesin Turing yang jumlahnya tak terhingga banyaknya.

Penting juga untuk memperkenalkan konsep konfigurasi mesin, yaitu. kumpulan status semua sel pita, status LU, dan posisi kepala. Jelas bahwa konfigurasi mesin dapat berisi sejumlah karakter dari alfabet eksternal dan hanya satu karakter dari alfabet internal.

Sebelum mulai bekerja, kata awal a yang panjangnya berhingga dalam alfabet A ditulis pada pita kosong; head dipasang di atas karakter pertama kata a, LU dipindahkan ke status q1 (yaitu, konfigurasi awal terlihat seperti q1a). Karena hanya satu aturan transformasi yang diterapkan di setiap konfigurasi, konfigurasi awal secara unik menentukan semua operasi mesin selanjutnya, yaitu. seluruh urutan konfigurasi hingga penghentian operasi.

Tergantung pada konfigurasi awal, ada dua skenario yang mungkin terjadi:

1) setelah sejumlah siklus terbatas, mesin berhenti pada perintah berhenti; dalam hal ini, konfigurasi akhir yang sesuai dengan informasi keluaran muncul di rekaman;

2) tidak ada hentinya.

Dalam kasus pertama mereka mengatakan bahwa mesin ini dapat diterapkan pada informasi awal, dalam kasus kedua - tidak. Seluruh rangkaian konfigurasi masukan yang digunakan mesin untuk memberikan hasil membentuk kelas masalah yang harus dipecahkan. Jelas, tidak masuk akal menggunakan mesin Turing untuk masalah yang tidak termasuk dalam kelas masalah yang dapat dipecahkan.

Ada hipotesis Turing: jika suatu prosedur terdefinisi dengan baik dan bersifat mekanis, maka kita dapat berasumsi bahwa akan ada mesin Turing yang mampu melaksanakannya. Hal ini tidak dapat dibuktikan karena menghubungkan definisi longgar dari konsep suatu algoritma dengan definisi ketat dari mesin Turing. Dugaan ini dapat terbantahkan jika dapat memberikan contoh algoritma yang tidak dapat diimplementasikan menggunakan rangkaian fungsi Turing. Namun, semua algoritma yang diketahui sejauh ini dapat dispesifikasikan menggunakan rangkaian fungsional Turing.

simulator untuk mempelajari pemain universal

Apa itu?

Simulator Mesin Turing adalah model pelatihan pelaksana universal (mesin komputasi abstrak), diusulkan pada tahun 1936 oleh A. Turing untuk memperjelas konsep suatu algoritma. Menurut tesis Turing, algoritma apa pun dapat ditulis sebagai program untuk mesin Turing. Telah terbukti bahwa mesin Turing memiliki kemampuan yang setara dengan mesin Post dan algoritma Markov normal.

Mesin Turing terdiri dari kereta (kepala baca dan tulis) dan pita tak berujung yang dibagi menjadi beberapa sel. Setiap sel rekaman dapat berisi karakter dari beberapa alfabet A=(a 0 ,a 1 ,…,a N ) . Alfabet apa pun berisi karakter spasi, yang dilambangkan dengan 0 atau Λ. Saat memasukkan perintah, spasi diganti dengan garis bawah "_".

Mesin Turing adalah mesin otomat yang dikendalikan oleh sebuah meja. Baris dalam tabel sesuai dengan karakter alfabet A yang dipilih, dan kolom sesuai dengan status mesin Q=(q 0 ,q 1 ,…,q M ) . Pada awal pengoperasiannya, mesin Turing dalam keadaan q 1 . Status q 0 adalah status akhir: setelah berada di dalamnya, mesin mengakhiri operasinya.

Di setiap sel tabel, sesuai dengan beberapa simbol a i dan beberapa keadaan q j, terdapat perintah yang terdiri dari tiga bagian:

1. karakter dari alfabet A;
2. arah gerakan: > (kanan),
3. keadaan mesin yang baru

Berita

1. Falina I.N. Topik “Mesin Turing” dalam kursus ilmu komputer sekolah (inf.1september.ru).
2. Mayer R.V. Mesin Post dan Turing (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Mesin Turing dan Algoritma Markov. Pemecahan masalah, M.: MSU, 2006.
4. Bekman I.N. Ilmu Komputer. Kuliah 7. Algoritma (profbeckman.narod.ru)
5. Solovyov A. Matematika diskrit tanpa rumus (lib.rus.ec)
6. Ershov S.S. Elemen teori algoritma, Chelyabinsk, SUSU Publishing Center, 2009.
7. Varpakhovsky F.L. Unsur teori algoritma, M: Prosveshchenie, 1970.
8. Vereshchagin N.K., Shen A. Fungsi yang dapat dihitung, M: MTsNMO, 1999.

Apa yang harus dilakukan tentang hal itu?

Di bagian atas program terdapat kolom editor di mana Anda dapat memasukkan kondisi masalah dalam bentuk bebas.

Pita bergerak ke kiri dan ke kanan menggunakan tombol yang terletak di kiri dan kanannya. Dengan mengklik dua kali sel pita (atau mengklik kanan) Anda dapat mengubah isinya.

Menggunakan menu Pita Anda dapat menyimpan status rekaman itu di buffer internal dan memulihkan rekaman itu dari buffer.

Di lapangan Alfabet Karakter alfabet yang dipilih ditentukan. Spasi secara otomatis ditambahkan ke karakter yang dimasukkan.

Program diketik pada tabel di bagian bawah jendela. Kolom pertama berisi karakter alfabet dan terisi secara otomatis. Baris pertama mencantumkan semua kemungkinan status. Anda dapat menambah dan menghapus kolom tabel (negara bagian) menggunakan tombol yang terletak di atas tabel.

Saat memasukkan perintah ke dalam sel tabel, Anda harus memasukkan karakter baru terlebih dahulu, lalu arah transisi dan nomor negara bagian. Jika sebuah karakter dihilangkan, karakter tersebut tidak akan berubah secara default. Jika nomor negara bagian dihilangkan, secara default keadaan mesin tidak berubah.

Tepat di lapangan Komentar Anda dapat memasukkan komentar dalam bentuk bebas tentang solusinya. Paling sering ini menjelaskan arti setiap keadaan mesin Turing.

Program dapat dijalankan secara terus menerus (F9) atau bertahap (F8). Perintah yang sekarang akan dijalankan disorot dengan latar belakang hijau. Kecepatan eksekusi dapat disesuaikan menggunakan menu Kecepatan.

Masalah mesin turing dapat disimpan dalam file. Kondisi tugas, alfabet, program, komentar dan keadaan awal rekaman itu disimpan. Ketika tugas dimuat dari file dan disimpan ke file, status rekaman secara otomatis di-buffer.

Jika Anda melihat kesalahan atau memiliki saran, komentar, keluhan, permintaan atau pernyataan, tulislah.

Persyaratan teknis

Program ini berjalan di bawah sistem operasi saluran jendela di komputer modern mana pun.

Lisensi

Program ini gratis untuk penggunaan non-komersial. Kode sumber program tidak didistribusikan.

Programnya datang " dengan adanya Artinya, penulis tidak bertanggung jawab atas segala akibat yang mungkin timbul dari penggunaannya, termasuk kerugian moral dan materi, kegagalan peralatan, cedera fisik dan mental.

Saat memposting program di situs web lain, diperlukan tautan ke sumber aslinya.

1. 1) publikasi materi dalam bentuk apapun, termasuk penempatan materi di situs Web lain;
2. 2) pendistribusian bahan yang tidak lengkap atau diubah;
3. 3) pencantuman materi dalam koleksi di media apapun;
4. 4) memperoleh manfaat komersial dari penjualan atau penggunaan bahan lainnya.

Mengunduh materi berarti Anda menerima ketentuan perjanjian lisensi ini.

Unduh

Setelah membongkar arsip, program ini berfungsi dengan baik dan tidak memerlukan instalasi tambahan apa pun.

1. Deskripsi mesin Turing. 3

1.1 Properti mesin Turing sebagai suatu algoritma. 5

2. Kompleksitas algoritma. 7

2.1 Kompleksitas masalah... 9

3. Mesin turing dan masalah yang tidak dapat dipecahkan secara algoritmik.. 12

Kesimpulan. 16

Referensi..18

Perkenalan

Mesin Turing adalah perangkat komputasi yang sangat sederhana. Ini terdiri dari pita dengan panjang tak terbatas, dibagi menjadi beberapa sel, dan kepala yang bergerak di sepanjang pita dan mampu membaca dan menulis karakter. Selain itu, mesin Turing memiliki karakteristik keadaan, yang dapat dinyatakan sebagai bilangan bulat dari nol hingga nilai maksimum tertentu. Tergantung pada keadaannya, mesin Turing dapat melakukan salah satu dari tiga tindakan: menulis simbol ke dalam sel, memindahkan satu sel ke kanan atau kiri, dan mengatur keadaan internal.

Desain mesin Turing sangat sederhana, namun dapat menjalankan hampir semua program. Untuk melakukan semua tindakan ini, tabel aturan khusus disediakan, yang menentukan apa yang perlu dilakukan untuk berbagai kombinasi keadaan saat ini dan simbol yang dibaca dari rekaman itu.

Pada tahun 1947, Alan Turing memperluas definisinya dengan menggambarkan "mesin Turing universal". Kemudian, untuk memecahkan kelas masalah tertentu, variasinya diperkenalkan, yang memungkinkan untuk melakukan bukan hanya satu tugas, tetapi beberapa tugas.

1. Deskripsi mesin Turing

Latar belakang terciptanya karya ini terkait dengan rumusan masalah matematika yang belum terpecahkan oleh David Hilbert pada Kongres Matematika Internasional di Paris pada tahun 1900. Salah satunya adalah tugas membuktikan konsistensi sistem aksioma aritmatika biasa, yang kemudian diklarifikasi Hilbert sebagai "masalah decidability" - menemukan metode umum untuk menentukan kepuasan pernyataan tertentu dalam bahasa logika formal.

Makalah Turing justru memberikan jawaban atas masalah ini - masalah kedua Hilbert ternyata tidak terpecahkan. Namun arti penting makalah Turing jauh melampaui masalah penulisannya.

Berikut adalah deskripsi dari karya John Hopcroft ini: "Mengerjakan masalah Hilbert, Turing harus memberikan definisi yang jelas tentang konsep metode. Dimulai dari gagasan intuitif tentang metode sebagai semacam algoritma, yaitu prosedur yang dapat dilakukan secara mekanis, tanpa intervensi kreatif”, ia menunjukkan bagaimana ide tersebut dapat diwujudkan dalam bentuk model proses komputasi yang detail. Model komputasi yang dihasilkan, dimana setiap algoritma dipecah menjadi suatu urutan sederhana, langkah dasar, adalah konstruksi logis yang kemudian disebut mesin Turing."

Mesin Turing adalah perpanjangan dari model mesin keadaan terbatas, sebuah ekstensi yang mencakup memori yang berpotensi tak terbatas dengan kemampuan untuk berpindah (pindah) dari sel yang sedang dilihat ke tetangga kiri atau kanannya.

Secara formal mesin Turing dapat digambarkan sebagai berikut. Biarkan yang berikut ini diberikan:

sekumpulan keadaan berhingga – Q, yang dapat menampung mesin Turing;

himpunan terbatas simbol pita – Г;

fungsi δ (fungsi atau program transisi), yang ditentukan dengan memetakan pasangan dari hasil kali Cartesian Q x Г (mesin dalam keadaan qi dan melihat simbol gi) menjadi tripel dari hasil kali Cartesian Q x Г x (L ,R) (mesin masuk ke keadaan qi, mengganti simbol gi dengan simbol gj dan menggerakkan satu simbol pita ke kiri atau ke kanan) – Q x Г-->Q x Г x (L,R)

satu karakter dari Г-->е (kosong);

subset Σ є Г - -> didefinisikan sebagai subset dari simbol masukan pita, dan е є (Г - Σ);

salah satu keadaan – q0 є Q adalah keadaan awal mesin.

Masalah yang harus diselesaikan ditentukan dengan merekam sejumlah simbol yang terbatas dari himpunan Σ є Г – Si є Σ ke pita:

eS1S2S3S4... ... ...Sne

setelah itu mesin dipindahkan ke keadaan awal dan head dipasang pada simbol tak kosong paling kiri (q0,w) –, setelah itu sesuai dengan fungsi transisi yang ditentukan (qi,Si) - ->(qj, Sk, L atau R), mesin mulai mengganti simbol yang dilihat, menggerakkan kepala ke kanan atau kiri dan berpindah ke keadaan lain yang ditentukan oleh fungsi transisi.

Mesin berhenti jika fungsi transisi untuk pasangan (qi,Si) tidak ditentukan.

Alan Turing mengusulkan bahwa algoritma apa pun dalam arti intuitif dapat diwakili oleh mesin Turing yang setara. Asumsi ini dikenal sebagai tesis Church-Turing. Setiap komputer dapat mensimulasikan mesin Turing (operasi menulis ulang sel, membandingkan dan berpindah ke sel tetangga lainnya, dengan mempertimbangkan perubahan keadaan mesin). Oleh karena itu, ia dapat memodelkan algoritma dalam formalisme apa pun, dan dari tesis ini dapat disimpulkan bahwa semua komputer (terlepas dari kekuatan, arsitektur, dll.) setara dalam hal kemampuan dasar untuk memecahkan masalah algoritmik.

1.1 Properti mesin Turing sebagai suatu algoritma

Dengan menggunakan mesin Turing sebagai contoh, sifat-sifat algoritma dapat terlihat dengan jelas. Mintalah siswa untuk menunjukkan bahwa mesin Turing memiliki semua sifat algoritma.

Kebijaksanaan. Mesin Turing dapat berpindah ke langkah ke (k + 1) hanya setelah menyelesaikan setiap langkah, karena setiap langkah itulah yang menentukan langkah ke (k + 1) yang akan diambil.

Kejelasan. Pada setiap langkah, simbol alfabet ditulis ke dalam sel, robot membuat satu gerakan (L, P, N), dan mesin Turing memasuki salah satu keadaan yang dijelaskan.

Determinisme. Setiap sel tabel mesin Turing hanya berisi satu opsi untuk suatu tindakan. Pada setiap langkah, hasilnya ditentukan secara unik, oleh karena itu urutan langkah penyelesaian masalah ditentukan secara unik, yaitu. Jika mesin Turing diberikan kata masukan yang sama, maka kata keluarannya akan selalu sama.

Produktifitas. Dalam hal konten, hasil dari setiap langkah dan seluruh urutan langkah ditentukan secara unik; oleh karena itu, mesin Turing yang ditulis dengan benar akan menuju ke keadaan q0 dalam sejumlah langkah yang terbatas, yaitu. dalam beberapa langkah yang terbatas jawaban atas pertanyaan masalah akan diperoleh.

Karakter massa. Setiap mesin Turing didefinisikan untuk semua kata yang dapat diterima dari alfabet, ini adalah properti karakter massal. Setiap mesin Turing dirancang untuk memecahkan satu kelas masalah, yaitu. Untuk setiap soal, mesin Turingnya sendiri (baru) ditulis.

2. Kompleksitas algoritma

Kompleksitas suatu algoritma ditentukan oleh daya komputasi yang dibutuhkan untuk menjalankannya. Kompleksitas komputasi suatu algoritma sering diukur dengan dua parameter: T (kompleksitas waktu) dan S (kompleksitas ruang, atau kebutuhan memori). T dan S biasanya direpresentasikan sebagai fungsi n, dimana n adalah ukuran data masukan. (Ada cara lain untuk mengukur kompleksitas: jumlah bit acak, lebar saluran komunikasi, jumlah data, dll.)

Biasanya, kompleksitas komputasi suatu algoritma dinyatakan dengan menggunakan notasi “O Besar”, yaitu digambarkan berdasarkan urutan besarnya kompleksitas komputasi. Ini hanyalah suku dalam perluasan fungsi kompleksitas yang tumbuh paling cepat seiring bertambahnya n, semua suku tingkat rendah diabaikan. Misalnya, jika kompleksitas waktu suatu algoritma tertentu adalah 4n2+7n+12, maka kompleksitas komputasinya berada pada orde n2, ditulis sebagai O(n2).

Kompleksitas waktu yang diukur dengan cara ini tidak bergantung pada implementasi. Anda tidak perlu mengetahui waktu eksekusi pasti dari berbagai instruksi, atau jumlah bit yang digunakan untuk mewakili berbagai variabel, atau bahkan kecepatan prosesor. Satu komputer mungkin 50 persen lebih cepat dibandingkan komputer lain, dan komputer ketiga mungkin memiliki bus data dua kali lebih lebar, namun kompleksitas algoritme, yang diukur berdasarkan urutan besarnya, tidak akan berubah. Hal ini tidak curang; ketika bekerja dengan algoritma yang rumit seperti yang dijelaskan dalam buku ini, segala sesuatu yang lain dapat diabaikan (hingga faktor konstan) dibandingkan dengan urutan besarnya kompleksitas.

Notasi ini memungkinkan Anda melihat bagaimana ukuran data masukan mempengaruhi kebutuhan waktu dan memori. Misalnya, jika T = O(n), maka menggandakan data masukan akan menggandakan waktu eksekusi algoritma. Jika T=O(2n), maka menambahkan satu bit ke data masukan akan menggandakan waktu eksekusi algoritma.

Biasanya, algoritma diklasifikasikan berdasarkan kompleksitas waktu atau ruangnya. Suatu algoritma disebut konstan jika kompleksitasnya tidak bergantung pada n: 0(1). Suatu algoritma dikatakan linier jika kompleksitas waktunya adalah O(n). Algoritma dapat berbentuk kuadrat, kubik, dll. Semua algoritma ini bersifat polinomial, kompleksitasnya adalah O(m), dimana m adalah sebuah konstanta. Algoritma dengan kompleksitas waktu polinomial disebut algoritma waktu polinomial

Algoritma yang kompleksitasnya sama dengan O(tf(n)), dengan t adalah konstanta yang lebih besar dari 1, dan f(n) adalah suatu fungsi polinomial dari n, disebut eksponensial. Subset algoritma eksponensial yang kompleksitasnya adalah O(cf(n)), dengan c adalah konstanta dan f(n) meningkat lebih cepat dari konstanta tetapi lebih lambat dari fungsi linier, disebut superpolinomial.

Idealnya, seorang kriptografer ingin mengklaim bahwa algoritma terbaik untuk memecahkan algoritma enkripsi yang dirancang memiliki kompleksitas waktu yang eksponensial. Dalam praktiknya, pernyataan terkuat yang dapat dibuat mengingat keadaan teori kompleksitas komputasi saat ini adalah dalam bentuk “semua algoritma serangan yang diketahui untuk sistem kriptografi tertentu memiliki kompleksitas waktu superpolinomial.” Artinya, algoritma serangan yang kita kenal memiliki kompleksitas waktu superpolinomial, namun belum dapat dibuktikan bahwa algoritma serangan dengan kompleksitas waktu polinomial tidak dapat ditemukan. Perkembangan teori kompleksitas komputasi suatu saat nanti memungkinkan terciptanya algoritma yang keberadaan algoritma dengan waktu pembukaan polinomial dapat dikecualikan dengan akurasi matematis.

Mesin Turing adalah salah satu penemuan intelektual paling menarik dan mengasyikkan di abad ke-20. Ini adalah model komputasi abstrak yang sederhana dan berguna (komputer dan digital) yang cukup umum untuk mengimplementasikan tugas komputasi apa pun. Berkat deskripsi sederhana dan analisis matematisnya, ini menjadi dasar ilmu komputer teoretis. Penelitian ini menghasilkan pemahaman yang lebih baik tentang komputasi digital dan kalkulus, termasuk pemahaman bahwa ada beberapa masalah komputasi yang tidak dapat diselesaikan pada komputer mainframe.

Alan Turing berusaha mendeskripsikan model paling primitif dari perangkat mekanis yang memiliki kemampuan dasar yang sama dengan komputer. Turing pertama kali mendeskripsikan mesin tersebut pada tahun 1936 dalam sebuah makalah "Tentang bilangan yang dapat dihitung dengan aplikasi pada masalah solvabilitas", yang muncul dalam Proceedings of the London Mathematical Society.

Mesin Turing adalah perangkat komputasi yang terdiri dari kepala baca/tulis (atau "pemindai") dengan pita kertas yang melewatinya. Rekaman itu dibagi menjadi beberapa kotak, yang masing-masing membawa satu simbol - "0" atau "1". Tujuan dari mekanisme ini adalah bahwa ia bertindak baik sebagai sarana input dan output, dan sebagai memori kerja untuk menyimpan hasil perhitungan tahap peralihan. Terdiri dari apa alat tersebut?Setiap mesin terdiri dari dua komponen: Pita tak terbatas. Itu tidak terbatas di kedua arah dan dibagi menjadi beberapa sel. Program yang dikontrol secara otomatis, kepala pemindai untuk membaca dan menulis data. Itu bisa berada di salah satu dari banyak negara bagian pada saat tertentu.

Setiap mesin menghubungkan dua rangkaian data berhingga: alfabet simbol masuk A = (a0, a1, ..., am) dan alfabet status Q = (q0, q1, ..., qp). Keadaan q0 disebut pasif. Dipercayai bahwa perangkat tersebut berhenti bekerja ketika terkena. Keadaan q1 disebut awal - mesin memulai penghitungannya saat berada di awal. Kata masukan terletak pada pita, satu huruf berturut-turut di setiap posisi. Di kedua sisinya hanya ada sel kosong.

Bagaimana mekanisme kerjanya

Mesin Turing memiliki perbedaan mendasar dari perangkat komputasi - perangkat penyimpanannya memiliki pita yang tidak ada habisnya, sedangkan pada perangkat digital perangkat tersebut memiliki strip dengan panjang tertentu. Setiap kelas tugas diselesaikan hanya dengan satu mesin Turing yang dibuat. Masalah dari jenis yang berbeda memerlukan penulisan algoritma baru. Perangkat kontrol, dalam keadaan yang sama, dapat bergerak ke segala arah di sepanjang sabuk. Ia menulis dan membaca dari sel karakter alfabet terbatas. Selama perpindahan, elemen kosong dialokasikan dan mengisi posisi yang tidak berisi data masukan. Algoritma mesin Turing menentukan aturan transisi untuk perangkat kontrol. Mereka mengatur parameter berikut ke kepala baca-tulis: menulis karakter baru ke sel, beralih ke keadaan baru, bergerak ke kiri atau kanan sepanjang pita.

Properti mekanisme

Mesin Turing, seperti sistem komputasi lainnya, memiliki fitur yang melekat, dan sifat-sifatnya mirip dengan algoritma: Kebijaksanaan. Mesin digital berpindah ke langkah berikutnya n+1 hanya setelah langkah sebelumnya selesai. Setiap langkah yang dijalankan menentukan n+1 yang akan dihasilkan. Kejelasan. Perangkat hanya melakukan satu tindakan untuk satu sel. Ia memasukkan karakter dari alfabet dan membuat satu gerakan: kiri atau kanan. Determinisme. Setiap posisi dalam mekanisme sesuai dengan satu opsi untuk melaksanakan skema tertentu, dan pada setiap tahap tindakan dan urutan pelaksanaannya tidak ambigu. Produktifitas. Hasil pasti untuk setiap tahapan ditentukan oleh mesin Turing. Program mengeksekusi algoritme dan dalam sejumlah langkah terbatas menuju status q0. Karakter massal. Setiap perangkat ditentukan berdasarkan kata-kata valid yang termasuk dalam alfabet. Algoritma penyelesaian Fungsi Mesin Turing sering kali memerlukan implementasi suatu fungsi. Bergantung pada kemungkinan penulisan rantai untuk perhitungan, suatu fungsi disebut dapat dipecahkan secara algoritmik atau tidak dapat diputuskan. Sebagai himpunan bilangan asli atau rasional, kata-kata dalam alfabet berhingga N untuk mesin, barisan himpunan B dianggap - kata-kata dalam kode biner alfabet B = (0,1). Selain itu, hasil penghitungan memperhitungkan nilai “tidak terdefinisi” yang terjadi saat algoritme terhenti. Untuk mengimplementasikan fungsi tersebut, penting untuk memiliki bahasa formal dalam alfabet akhir dan untuk memecahkan masalah dalam mengenali deskripsi yang benar.-

Program perangkat

Program untuk mekanisme Turing diformat dalam tabel di mana baris dan kolom pertama berisi simbol alfabet eksternal dan nilai kemungkinan status internal robot - alfabet internal. Data tabular adalah perintah yang diterima mesin Turing. Pemecahan masalah terjadi dengan cara ini: huruf dibaca oleh kepala di sel di mana ia berada saat ini, dan keadaan internal kepala mesin menentukan perintah mana yang perlu dijalankan. Perintah khusus ini terletak di persimpangan simbol alfabet eksternal dan internal yang terletak di tabel.

Komponen untuk perhitungan

Untuk membuat mesin Turing guna memecahkan satu masalah tertentu, Anda perlu menentukan parameter berikut untuk masalah tersebut. Alfabet eksternal. Ini adalah himpunan simbol berhingga tertentu, dilambangkan dengan tanda A, yang unsur-unsur penyusunnya disebut huruf. Salah satunya - a0 - harus kosong. Misalnya, alfabet perangkat Turing yang bekerja dengan bilangan biner terlihat seperti ini: A = (0, 1, a0). Rangkaian huruf dan simbol yang terekam dalam pita disebut kata. Perangkat otomatis adalah perangkat yang beroperasi tanpa campur tangan manusia. Dalam mesin Turing, ia memiliki beberapa keadaan berbeda untuk memecahkan masalah dan, dalam kondisi tertentu yang muncul, berpindah dari satu posisi ke posisi lain. Himpunan status pengangkutan tersebut adalah alfabet internal. Ia memiliki sebutan huruf dalam bentuk Q=(q1, q2...). Salah satu posisi ini - q1 - harus menjadi posisi awal, yaitu posisi yang memulai program. Elemen penting lainnya adalah status q0, yang merupakan status akhir, yaitu status yang mengakhiri program dan membawa perangkat ke posisi berhenti.

tabel transisi.

Komponen ini adalah algoritma untuk perilaku pengangkutan perangkat tergantung pada keadaan mesin saat ini dan nilai simbol baca.-

Algoritma untuk mesin

Selama pengoperasian, pengangkutan perangkat Turing dikendalikan oleh sebuah program yang, selama setiap langkah, melakukan serangkaian tindakan berikut: Menulis simbol alfabet eksternal ke suatu posisi, termasuk yang kosong, mengganti elemen yang ada di itu, termasuk yang kosong. Pindahkan satu langkah sel ke kiri atau kanan. Mengubah keadaan internal Anda. Jadi, saat menulis program untuk setiap pasangan karakter atau posisi, tiga parameter perlu dijelaskan secara akurat: ai - elemen dari alfabet A yang dipilih, arah pergeseran kereta ("←" ke kiri, "→" ke kanan, "titik" - tidak ada gerakan) dan qk - keadaan baru perangkat. Misalnya, perintah 1 “←” q2 memiliki arti “ganti karakter dengan 1, pindahkan kepala kereta ke kiri satu sel langkah dan melakukan transisi ke keadaan q2”.