Katakanlah sudah lama sekali... Namun nyatanya, sebelum terciptanya mesin Turing, mesin diciptakan untuk melakukan berbagai tindakan. Misalnya, Anda perlu mengambil logaritma, nuka, tetapi mari kita rivet mesin yang akan membaca nomor dan mengambil logaritma. Atau Anda perlu, katakanlah, dua angka untuk ditambahkan - inilah mesin untuk menambahkan dua angka. Dan bahkan sekarang ada mesin seperti itu, misalnya, kalkulator. Apa yang bisa mereka lakukan? Tambah, kurangi, kalikan, dan rekayasa - bahkan ambil kosinus atau sinus. Ternyata mesin bodoh ini, kecuali tindakan yang direkam di dalamnya, dapat dan tidak dapat melakukan apa pun.

Jadi akan sangat menarik untuk membuat mesin seperti itu yang tidak akan membaca angka dan bukan simbol, tetapi sebuah algoritme, dan akan menjalankannya, yaitu, membuat mesin yang dapat diprogram. Inilah yang dilakukan Turing (saya akan mengatakan bahwa ada banyak abstraksi seperti itu selain Turing). Dan dia datang dengan model mobil seperti itu. Ternyata untuk menjalankan algoritme yang kompleks, yang Anda butuhkan hanyalah kereta, pita tanpa akhir, dan kemampuan untuk mengubah nilai yang direkam pada pita dan bergerak di sepanjang itu. Ternyata abstraksi ini benar-benar dapat diubah menjadi mesin nyata, satu-satunya, dengan batasan bahwa kami tidak dapat menyediakan mesin dengan pita yang tidak ada habisnya, tetapi kami dapat membuat pita yang sangat panjang;)

Mundur. Sebenarnya, tidak perlu menceritakan cara kerja mesin Turing, seperti yang saya katakan, itu dapat ditemukan dengan sangat mudah. Oleh karena itu, kami akan berasumsi bahwa Anda sudah tahu cara kerjanya.

Nah, mesin Turing melakukan beberapa algoritma sederhana, ini tidak terbantahkan. Tapi bagaimana dengan yang rumit? Dan, misalnya, bagaimana mengatur siklus menggunakan MT? Atau bagaimana cara mengetahui percabangan? Ternyata ada teorema yang membuktikan bahwa MT dapat melakukan perulangan dan percabangan, yang menyatakan bahwa dengan mekanisme yang sangat sederhana dimungkinkan untuk menyusun program dari blok sederhana seperti percabangan dan perulangan, yang artinya segala sesuatu yang dapat diprogram dapat diprogram. Dan di sini, secara teori, harus ada penjelasan bahwa ada fungsi yang tidak dapat dihitung, dan oleh karena itu, masalah yang tidak dapat dipecahkan, dan masalah ini tidak dapat diselesaikan dengan bantuan MT. Begini caranya.

Tetapi tidak ada yang datang dengan sesuatu yang lebih keren dari mesin Turing, jadi semua bahasa pemrograman yang kita gunakan sekarang tidak dapat memprogram lebih dari mesin Turing. Dari sinilah muncul konsep kelengkapan Turing, yang berarti bahwa suatu bahasa (atau sesuatu yang lain) adalah Turing lengkap jika dapat digunakan untuk menulis semua algoritma yang dijalankan pada mesin Turing. Dan Anda dapat membuktikan bahwa suatu bahasa Turing lengkap dengan menulis emulator mesin Turing di dalamnya. Ini adalah pai.

Dari sudut pandang matematika, posting adalah omong kosong, tetapi jelas, untuk apa kami membutuhkan mesin Turing. Sebenarnya menulis algoritma untuk mesin ini adalah teka-teki yang menarik. Saya percaya mereka yang mengatakan bahwa setelah memprogram exp (x) pada mesin Turing, dia benar-benar mengerti apa itu algoritma. Belum mencobanya, tapi ini tantangan yang menarik.

Mesin Turing adalah kumpulan dari objek-objek berikut:

• 1) alfabet eksternal A = (a 0, a 1,…, a n);
• 2) abjad dalam Q = (q 1, q 2,…, q m) adalah himpunan keadaan;
• 3) satu set karakter kontrol (P, L, S)
• 4) pita tak terbatas di kedua arah, dibagi menjadi sel-sel, di mana masing-masing pada setiap saat waktu hanya satu karakter dari alfabet A yang dapat ditulis;
• 5) perangkat kontrol yang mampu berada di salah satu dari banyak keadaan

Simbol untuk sel kosong adalah huruf alfabet luar a 0.

Di antara keadaan, q 1 awal, di mana mesin mulai bekerja, dan akhir (atau keadaan berhenti) q 0, di mana mesin berhenti, dibedakan.

Perangkat kontrol dapat bergerak ke kiri dan kanan sepanjang pita, membaca dan menulis karakter alfabet A ke dalam sel pita. Perangkat kontrol bekerja sesuai dengan perintah yang terlihat seperti ini

q i a j> a p X q k

Entri berarti sebagai berikut: jika perangkat kontrol dalam keadaan qi, dan huruf aj ditulis dalam sel yang diamati, maka (1) alih-alih aj, ap ditulis dalam sel, (2) mesin beralih ke tampilan sel kanan berikutnya dari sel yang baru saja dilihat, jika X = P, atau untuk melihat sel kiri berikutnya, jika X = L, atau terus mengamati sel yang sama dari pita, jika X = C, (3) perangkat kontrol masuk ke keadaan q k.

Karena pengoperasian mesin, dengan kondisi, sepenuhnya ditentukan oleh keadaannya q, pada saat tertentu dan isi sel yang dipantau pada saat itu, maka untuk setiap konfigurasi yang mungkin q i a j ada tepat satu aturan. Tidak ada aturan hanya untuk keadaan akhir, di mana mobil berhenti. Oleh karena itu, program mesin Turing dengan abjad eksternal A = (a0, a1,…, an) dan internal Q = (q1, q2,…, qm) berisi paling banyak m (n + 1) instruksi.

Sebuah kata dalam abjad A atau dalam abjad Q, atau dalam abjad A Q adalah setiap urutan huruf dari abjad yang sesuai. Dengan konfigurasi ke-k yang kami maksud adalah gambar pita mesin dengan informasi yang terbentuk di atasnya pada awal langkah ke-k (atau sebuah kata dalam alfabet A tertulis pada pita di awal k- th step), menunjukkan sel mana yang sedang dilihat pada langkah ini dan dalam kondisi apa mobil itu. Hanya konfigurasi akhir yang masuk akal, mis. mereka di mana semua sel pita, dengan kemungkinan pengecualian dari jumlah terbatas, kosong. Konfigurasi disebut final jika keadaan mesin adalah final.

Jika kita memilih konfigurasi non-final mesin Turing sebagai konfigurasi awal, maka pekerjaan mesin adalah mengubah konfigurasi awal secara berurutan (langkah demi langkah) sesuai dengan program mesin hingga konfigurasi akhir tercapai. Setelah itu, pekerjaan mesin Turing dianggap selesai, dan hasil pekerjaan tersebut adalah konfigurasi akhir yang telah dicapai.

Kami akan mengatakan bahwa kata b yang tidak kosong dalam alfabet A (a 0) = (a 1, ..., an) dirasakan oleh mesin dalam posisi standar, jika ditulis dalam sel pita yang berurutan, semua sel lain kosong, dan mesin melihat sel paling kiri atau paling kanan dari sel tempat kata b ditulis. Posisi standar disebut posisi awal (akhir) jika mesin, yang menangkap kata dalam posisi standar, berada dalam keadaan awal q 1 (masing-masing, dalam keadaan berhenti q 0).

Jika pemrosesan kata b mentransfer mesin Turing ke keadaan akhir, maka dikatakan berlaku untuk b, jika tidak, tidak berlaku untuk b (mesin berjalan tanpa batas)

Mari kita pertimbangkan sebuah contoh:

Diberikan mesin Turing dengan alfabet eksternal A = (0, 1) (di sini 0 adalah simbol sel kosong), alfabet keadaan internal Q = (q 0, q 1, q 2) dan dengan diagram fungsional berikut (program):

q 1 0> 1 L q 2;

q 1 1 > 0 C q 2;

q 2 0 > 0 P q 0;

q 2 1 > 1 C q 1;

Program ini dapat ditulis menggunakan tabel

Pada langkah pertama, perintah berikut beroperasi: q 1 0> 1 q 2 (perangkat kontrol dalam keadaan q1, dan huruf 0 ditulis dalam sel yang diamati, 1 ditulis dalam sel, bukan 0, kepala digeser ke kiri, perangkat kontrol masuk ke status q2), di Akibatnya, konfigurasi berikut dibuat pada mesin:

Akhirnya, setelah menjalankan perintah q 2 0> 0 P q 0, konfigurasi dibuat

Konfigurasi ini bersifat final, karena mesin dalam keadaan berhenti q 0.

Dengan demikian, kata asli 110 diproses oleh mesin menjadi kata 101.

Urutan konfigurasi yang dihasilkan dapat ditulis dengan cara yang lebih pendek (isi dari sel yang diamati ditulis di sebelah kanan status tempat mesin saat ini berada):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Mesin Turing tidak lebih dari aturan (algoritma) untuk mengubah kata-kata dari alfabet A Q, yaitu. konfigurasi. Jadi, untuk mendefinisikan mesin Turing, Anda perlu menentukan abjad eksternal dan internalnya, sebuah program dan menunjukkan simbol mana yang menunjukkan sel kosong dan status akhir.

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 komputer apa pun. Berkat deskripsi sederhana dan analisis matematisnya, ini membentuk dasar ilmu komputer teoretis. Penelitian ini menghasilkan pemahaman yang lebih dalam tentang komputer digital dan kalkulus, termasuk kesadaran bahwa ada beberapa masalah komputasi yang tidak dapat diselesaikan pada komputer pengguna umum.

Alan Turing berusaha untuk menggambarkan model paling primitif dari perangkat mekanik yang akan memiliki kemampuan dasar yang sama seperti komputer. Turing pertama kali menjelaskan mesin pada tahun 1936 dalam sebuah artikel "Pada angka yang dapat dihitung dengan aplikasi untuk masalah solvabilitas", yang muncul di Prosiding London Mathematical Society.

Mesin Turing adalah perangkat komputasi yang terdiri dari kepala baca / tulis (atau "pemindai") dengan pita kertas yang melewatinya. Pita dibagi menjadi kotak, yang masing-masing memiliki satu karakter - "0" atau "1". Tujuan dari mekanisme ini adalah bahwa ia bertindak baik sebagai sarana untuk masuk dan keluar, dan sebagai memori kerja untuk menyimpan hasil-hasil dari tahap-tahap perhitungan menengah. Apa perangkat terdiri dari Setiap mesin tersebut terdiri dari dua komponen: Pita tak terbatas. Itu tak terbatas di kedua arah dan dibagi menjadi sel. Mesin otomatis - program yang dikendalikan, pemindai kepala untuk membaca dan menulis data. Itu bisa kapan saja di salah satu dari banyak negara bagian.

Setiap mesin menghubungkan dua baris data berhingga: alfabet simbol yang masuk A = (a0, a1, ..., am) dan alfabet status Q = (q0, q1, ..., qp). Keadaan q0 disebut pasif. Diyakini bahwa perangkat tersebut akan berhenti bekerja ketika mengenainya. Keadaan q1 disebut keadaan awal - mesin memulai perhitungannya, berada di awal di dalamnya. Kata input terletak di pita, satu huruf berturut-turut di setiap posisi. Hanya sel kosong yang terletak di kedua sisinya.

Bagaimana mekanismenya?

Mesin Turing memiliki perbedaan mendasar dari perangkat komputasi - perangkat memorinya memiliki pita tak berujung, sedangkan pada perangkat digital perangkat semacam itu memiliki strip dengan panjang tertentu. Setiap kelas tugas diselesaikan hanya dengan satu mesin Turing bawaan. Masalah dari jenis yang berbeda melibatkan penulisan algoritma baru. Perangkat kontrol, dalam satu keadaan, dapat bergerak ke segala arah di sepanjang sabuk. Ia menulis dan membaca dari sel karakter alfabet terakhir. Selama pergerakan, elemen kosong dipilih, yang mengisi posisi yang tidak berisi data input. Algoritma mesin Turing mendefinisikan aturan transisi untuk perangkat kontrol. Mereka mengatur parameter berikut ke kepala baca-tulis: menulis karakter baru ke sel, beralih ke status baru, bergerak ke kiri atau kanan di sepanjang pita.

Sifat mekanisme

Mesin Turing, seperti sistem komputasi lainnya, memiliki fitur yang melekat, dan mereka mirip dengan sifat-sifat algoritma: Diskresi. Mesin digital melanjutkan ke langkah berikutnya n + 1 hanya setelah yang sebelumnya selesai. Setiap tahap yang diselesaikan menunjuk apa yang akan menjadi n + 1. Dapat dipahami. Perangkat hanya melakukan satu tindakan untuk sel yang sama. Ini menuliskan karakter dari alfabet dan membuat satu gerakan: kiri atau kanan. Determinisme. Setiap posisi dalam mekanisme sesuai dengan satu opsi untuk melakukan skema yang diberikan, dan pada setiap tahap, tindakan dan urutan implementasinya tidak ambigu. Efektivitas. Hasil yang tepat untuk setiap tahap ditentukan oleh mesin Turing. Program mengeksekusi algoritme dan dalam sejumlah langkah yang terbatas lolos ke keadaan q0. Karakter massa. Setiap perangkat didefinisikan melalui kata-kata abjad yang valid. Fungsi Mesin Turing Algoritme penyelesaian seringkali membutuhkan implementasi suatu fungsi. Bergantung pada kemungkinan penulisan rantai untuk komputasi, fungsi ini disebut dapat ditentukan secara algoritmik atau tidak dapat diputuskan. Sebagai satu set bilangan alami atau rasional, kata-kata dalam alfabet hingga N untuk mesin, kami mempertimbangkan urutan set B - kata-kata dalam kerangka alfabet kode biner B = (0,1). Juga, hasil perhitungan memperhitungkan nilai "tidak terdefinisi" yang terjadi ketika algoritme "hang". Untuk mengimplementasikan fungsi tersebut, penting bahwa bahasa formal ada dalam alfabet yang terbatas dan bahwa masalah mengenali deskripsi yang benar dapat dipecahkan.

Program perangkat

Program untuk mekanisme Turing diformat dengan tabel di mana baris dan kolom pertama berisi simbol alfabet eksternal dan nilai kemungkinan status internal mesin - alfabet internal. Data tabular adalah perintah yang diterima oleh mesin Turing. Solusi dari masalah adalah sebagai berikut: surat yang dibaca oleh kepala di sel di mana ia berada saat ini, dan keadaan internal kepala mesin menentukan perintah mana yang harus dijalankan. Secara khusus, perintah semacam itu terletak di persimpangan simbol alfabet eksternal dan internal, yang ada di tabel.

Komponen komputasi

Untuk membangun mesin Turing untuk memecahkan satu masalah tertentu, perlu untuk menentukan parameter berikut untuk itu. Alfabet eksternal. Ini adalah beberapa set simbol yang terbatas, dilambangkan dengan tanda A, elemen-elemen penyusunnya dinamai dengan huruf. Salah satunya - a0 - harus kosong. Misalnya, alfabet perangkat Turing yang bekerja dengan bilangan biner terlihat seperti ini: A = (0, 1, a0). Rangkaian simbol huruf yang tidak terputus yang direkam pada pita disebut kata. Automaton adalah perangkat yang bekerja tanpa campur tangan manusia. Dalam mesin Turing, ia memiliki beberapa keadaan berbeda untuk memecahkan masalah dan, dalam kondisi tertentu yang timbul, bergerak dari satu posisi ke posisi lain. Kumpulan status carriage tersebut adalah alfabet internal. Ini memiliki notasi huruf dalam bentuk Q = (q1, q2 ...). Salah satu dari posisi ini - q1 - harus menjadi posisi awal, yaitu posisi yang memulai program. Elemen penting lainnya adalah keadaan q0, yang final, yaitu yang mengakhiri program dan membawa perangkat ke posisi berhenti.

Meja lompat.

Komponen ini merupakan algoritme untuk perilaku carriage perangkat, tergantung pada status mesin saat ini dan nilai karakter yang sedang dibaca.

Algoritma untuk otomat

Selama operasi, pembawa perangkat Turing dikendalikan oleh program yang, selama setiap langkah, melakukan urutan berikut: Menulis simbol alfabet eksternal ke suatu posisi, termasuk yang kosong, mengganti elemen di dalamnya, termasuk yang kosong. Pindahkan satu langkah sel ke kiri atau kanan. Mengubah keadaan batin Anda. Jadi, ketika menulis program untuk setiap pasangan karakter atau posisi, tiga parameter harus dijelaskan secara akurat: ai - elemen dari alfabet A yang dipilih, arah pergeseran carriage ("←" ke kiri, "→" ke kanan, "titik" - tidak ada gerakan) dan qk - status perangkat baru Misalnya, perintah 1 "←" q2 memiliki nilai "ganti karakter dengan 1, pindahkan kepala kereta ke kiri satu langkah sel dan buat transisi ke keadaan q2".

Kita sering memecahkan masalah dengan kompleksitas yang berbeda-beda: sehari-hari, matematika, dll. Ada yang mudah diselesaikan, ada yang harus banyak dipikirkan, ada juga yang tidak pernah kita temukan solusinya.

Dalam kasus umum, cara untuk memecahkan masalah (jika ada) dapat dijelaskan dengan menggunakan sejumlah tindakan dasar yang terbatas.

Misalnya, menyelesaikan persamaan kuadrat:

1. Bawa persamaan ke bentuk kanonik \ (a x ^ 2 + b x + c = 0 \)
2. Jika \ (a = 0 \), maka ini adalah persamaan linier dengan solusi \ (x = \ frac (-c) (b) \). Masalahnya sudah diatasi. Jika tidak, lanjutkan ke langkah 3.
3. Hitung diskriminan \ (D = b ^ 2-4 a c \)
4. Hitung solusi persamaan \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Masalahnya sudah diatasi.

Anda dapat memperkenalkan konsep algoritma intuitif berikut:

Algoritma adalah seperangkat instruksi yang menggambarkan urutan tindakan pelaksana untuk mencapai hasil pemecahan masalah dalam jumlah tindakan yang terbatas, untuk setiap set data awal.

Ini, tentu saja, bukan definisi yang ketat, tetapi menggambarkan esensi dari konsep suatu algoritma.

Algoritma dikompilasi berdasarkan spesifik penampil, dan, karenanya, harus disusun dalam bahasa yang dapat dipahami oleh pelaku.

Pelaksana algoritme dapat berupa seseorang, atau dapat berupa komputer, atau mesin lain, misalnya, alat tenun.

Properti algoritme berikut disorot:

Keterpisahan dari algoritme harus berupa urutan tertentu dari langkah-langkah (tindakan) yang terpisah dan terdefinisi dengan jelas. Masing-masing tindakan ini harus terbatas waktunya. Determinisme pada setiap langkah algoritma, langkah selanjutnya secara unik ditentukan oleh keadaan sistem saat ini. Akibatnya, pada data awal yang sama, algoritme mengembalikan hasil yang sama setiap kali, tidak peduli berapa kali dieksekusi. Comprehensibility Algoritme harus dirumuskan dalam bahasa yang dapat dimengerti oleh performer. Ketika datang ke komputer, algoritme harus menggunakan hanya instruksi yang diketahui komputer dan hasilnya ditentukan secara ketat. Keterbatasan algoritma harus diselesaikan dalam jumlah langkah yang terbatas. Besarnya algoritma harus dapat diterapkan pada kumpulan data input yang berbeda. Dengan kata lain, algoritme harus cocok untuk penyelesaian kelas tugas. Kembali ke contoh kuadrat, algoritme cocok untuk diselesaikan dari semua persamaan kuadrat, bukan hanya satu atau lebih. Efektivitas algoritma harus diakhiri dengan hasil tertentu. Katakanlah, dengan memecahkan masalah, atau dengan menemukan bahwa tidak ada solusi. Jika algoritme tidak mengarah pada hasil, tidak jelas mengapa itu diperlukan sama sekali.

Tidak setiap cara untuk memecahkan masalah adalah algoritma. Katakanlah algoritma menyiratkan tidak ada pilihan. Misalnya, sebagian besar resep bukanlah algoritme karena mereka menggunakan frasa seperti "garam secukupnya". Akibatnya, persyaratan determinisme dilanggar.

Tidak untuk setiap masalah yang ada solusinya, ada juga algoritma solusi. Misalnya, masalah pengenalan gambar sebagian besar masih belum terselesaikan, dan tentu saja tidak menggunakan algoritma yang ketat. Namun, penggunaan jaringan saraf memberikan hasil yang cukup baik.

Biasanya, ada set untuk algoritme diizinkan memasukan data. Akan aneh untuk mencoba menerapkan algoritma penyelesaian persamaan untuk memasak makan malam, atau sebaliknya.

Selain itu, rangkaian kemungkinan tindakan pelaku juga terbatas, karena jika ada tindakan yang diizinkan, maka di antara mereka harus ada juga "tidak dapat diterima".

Definisi Algoritma Ketat

Definisi algoritma di atas tidak ketat. Ini menciptakan beberapa kesulitan. Secara khusus, dengan definisi seperti itu, tidak mungkin untuk membuktikan secara ketat apakah kelas masalah tertentu dapat dipecahkan oleh suatu algoritma.

Ternyata ada kelasnya masalah yang tidak dapat dipecahkan secara algoritmik- masalah yang tidak mungkin untuk menyusun algoritma solusi. Tetapi untuk membuktikan secara ketat ketidakjelasan algoritme, Anda harus terlebih dahulu memiliki definisi algoritme yang ketat.

Pada 20-30-an abad XX, berbagai ahli matematika mengerjakan masalah definisi algoritma yang ketat, khususnya Alan Turing, Emil Leon Post, Andrei Andreevich Markov, Andrei Nikolaevich Kolmogorov, Gereja Alonzo, dan lainnya. Pekerjaan mereka akhirnya mengarah pada munculnya dan pengembangan teori algoritma, teori kalkulus dan berbagai pendekatan untuk kalkulus, dan, omong-omong, pemrograman secara umum. Salah satu hasil kerja mereka adalah munculnya beberapa definisi ketat dari algoritma, diperkenalkan dengan cara yang berbeda, tetapi setara satu sama lain.

Kami akan membahas secara rinci definisi Turing, dan secara dangkal menganalisis definisi yang setara dari Post, Church, dan Markov.

mesin turing

Untuk memperkenalkan definisi formal dari suatu algoritma, Turing datang dengan dan menggambarkan mesin komputasi abstrak yang disebut mesin komputasi Turing, atau hanya mesin Turing.

Alan Turing (1912-1954)

Matematikawan Inggris, ahli logika, kriptografer, mungkin "peretas" pertama di dunia, adalah asal mula ilmu komputer dan teori kecerdasan buatan. Dia memberikan kontribusi yang signifikan bagi kemenangan pasukan Sekutu dalam Perang Dunia Kedua.

Data input untuk mesin Turing adalah: kata-kata dikompilasi dengan bantuan tertentu alfabet, yaitu himpunan karakter.

Hasil kerja mesin Turing juga berupa kata-kata.

Kata yang menerapkan algoritma disebut memasukkan... Kata yang berasal dari pekerjaan akhir pekan.

Himpunan kata yang menerapkan algoritma disebut ruang lingkup algoritma.

Sebenarnya, tidak mungkin untuk membuktikan bahwa objek apa pun dapat direpresentasikan dalam bentuk kata-kata yang disusun dalam beberapa alfabet - untuk ini kita memerlukan definisi objek yang ketat. Namun, Anda dapat memeriksa apakah algoritme acak apa pun yang bekerja pada objek dapat diubah sehingga ia bekerja pada kata-kata tanpa mengubah esensi algoritme.

Deskripsi mesin Turing

Mesin Turing termasuk pita yang tidak terbatas di kedua arah, dibagi menjadi sel, dan perangkat kontrol (juga disebut kepala baca-tulis, atau sederhananya mesin), mampu berada di salah satu dari banyak negara. Jumlah kemungkinan status perangkat kontrol terbatas dan ditentukan dengan tepat.

Perangkat kontrol dapat bergerak ke kiri dan ke kanan di sepanjang pita, membaca dan menulis karakter dari beberapa alfabet terbatas ke dalam sel. Karakter kosong khusus, dilambangkan \ (a_0 \) atau \ (\ Lambda \), dialokasikan, yang mengisi semua sel pita, kecuali sel (jumlah terbatas) tempat data input ditulis.

Kontroler beroperasi sesuai dengan aturan transisi, yang mewakili algoritma yang diterapkan oleh mesin Turing tertentu. Setiap aturan transisi menginstruksikan mesin, tergantung pada keadaan saat ini dan simbol yang diamati di sel saat ini, untuk menulis simbol baru di sel ini, beralih ke keadaan baru, dan memindahkan satu sel ke kiri atau ke kanan. Beberapa status mesin Turing dapat ditandai sebagai terminal, dan transisi ke salah satu dari mereka berarti akhir pekerjaan, penghentian algoritma.

Meskipun mesin Turing adalah konsep abstrak, cukup membayangkan mesin seperti itu (walaupun dengan pita terbatas), dan bahkan ada mesin demo seperti ini:

Lebih mudah untuk mewakili algoritma untuk mesin Turing dalam bentuk tabel: kolom tabel sesuai dengan simbol saat ini (diamati) pada pita, baris sesuai dengan kondisi mesin saat ini, dan sel berisi perintah yang akan dijalankan oleh mesin.

Perintah, pada gilirannya, dapat memiliki struktur berikut:

\ [a_k \ kiri \ lbrace \ begin (matriks) L \\ N \\ R \ end (matriks) \ kanan \ rbrace q_m \]

Pertama muncul simbol alfabet, yang harus ditulis di sel saat ini \ (a_k \), kemudian pergerakan mesin ke kiri (L), ke kanan (P) atau tidak ke mana-mana (tetap di tempat, H) ditunjukkan . Pada akhirnya, status baru ditunjukkan, ke mana otomat \ (q_m \) harus pergi.

Sel tabel didefinisikan dengan jelas oleh simbol saat ini \ (a_i \) dan status mesin saat ini \ (q_j \).

Mari kita sepakat bahwa pada awal pekerjaan, mesin Turing masuk keadaan awal, dilambangkan dengan \ (q_1 \), dan pada transisi ke keadaan berhenti\ (q_0 \) algoritma selesai dan mesin berhenti.

Contoh

Mari kita buat algoritma untuk mesin Turing yang menambahkan 1 ke kata input, yang merupakan angka desimal.

Kemudian secara deskriptif algoritma tersebut dapat dirumuskan sebagai berikut:

1. Pindah ke kanan, temukan awal kata input
2. Pindah ke kanan, temukan akhir kata input
3. Tambahkan satu ke bit kata input saat ini. Jika ada angka dari 0 hingga 8, keluar. Jika tidak, tulis 0, pindah ke kiri, dan kembali ke langkah 3.

Mari kita tulis algoritma ini dalam bentuk tabel. Alfabet terdiri dari angka 0 sampai 9 dan karakter kosong \ (\ Lambda \). Kami juga membutuhkan 4 status otomat, menghitung status berhenti, sesuai dengan langkah-langkah dalam deskripsi algoritme.

Mari kita sepakat bahwa keadaan awal \ (1 \) adalah pencarian awal kata input, \ (2 \) adalah pencarian akhir kata input, \ (3 \) adalah penambahan 1.

\ (_ (q_j) \ garis miring terbalik ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Mari kita telusuri operasi algoritma ini dengan sebuah contoh. Baris pertama sesuai dengan pita, yang kedua menunjukkan posisi mesin dan kondisinya saat ini.

	1	9	9
1

Di negara bagian 1, mesin penjual otomatis berada di atas sel kosong. Perintah yang sesuai dari tabel "ΛП1", yaitu, biarkan sel kosong, pindah ke kanan dan tetap dalam status 1:

	1	9	9
	1

Sekarang mesin penjual otomatis memonitor nilai "1". Perintah yang sesuai "1H2", yaitu, tinggalkan "1" di sel, jangan bergerak, dan pergi ke status "2":

	1	9	9
	2

Dalam keadaan "2", mesin mengamati nilai "1". Perintah yang sesuai "1P2", yaitu, tinggalkan "1", pindah ke kanan dan tetap dalam status "2":

Situasi berulang:

Sekarang, di negara bagian 3 dan mengamati simbol "9", mesin menjalankan perintah "0L3":

	1	9	0
		3

Situasi berulang:

Status "0" - status berhenti. Algoritma telah selesai.

Deskripsi resmi

Secara matematis, sebuah mesin Turing dapat digambarkan sebagai berikut:

Mesin Turing (MT)

ini adalah sistem bentuk \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), di mana

• \ (A \) - satu set terbatas simbol alfabet MT
• \ (a_0 \ dalam A \) - karakter alfabet kosong
• \ (Q \) adalah himpunan berhingga dari status MT
• \ (q_1 \ di Q \) - status awal MT
• \ (q_0 \ di Q \) - status akhir MT (status berhenti)
• \ (T = \ (A, P, H \) \) adalah himpunan shift MT
• \ (\ tau \) - Program MT, yaitu fungsi yang menentukan pemetaan \ (\ tau: A \ kali Q \ garis miring terbalik \ (q_0 \) \ panah kanan A \ kali T \ kali Q \)

Kunci dalam teori algoritma adalah Tesis Turing.

Secara longgar, tesis Turing dirumuskan sebagai berikut:

Tesis Turing untuk setiap masalah yang dapat dipecahkan secara algoritmik, ada mesin Turing yang memecahkan masalah ini. jika tidak, untuk algoritma apa pun ada mesin Turing yang setara.

Tesis Turing memungkinkan kita untuk berbicara tentang algoritma menggunakan peralatan matematika yang cukup sederhana. Terlebih lagi, mesin Turing itu sendiri adalah aktuator universal, dan kemungkinan untuk menciptakan mesin imajiner seperti itu telah menjadi alasan untuk berbicara tentang penciptaan teknologi komputasi universal.

Definisi Algoritma Alternatif

Selain mesin Turing, ada beberapa definisi independen yang setara dengan definisi Turing.

Secara khusus, definisi melalui mesin Post, melalui kalkulus lambda Gereja, algoritma Markov normal.

Mari kita pertimbangkan metode ini.

Mesin Pos

Setahun setelah Turing, matematikawan Amerika Emile Leon Post secara independen mengusulkan mesin komputasi universal abstrak lainnya, yang agak disederhanakan dibandingkan dengan mesin Turing.

Mesin Post beroperasi dengan alfabet dua digit, dan status internal mesin diganti dengan baris program.

Kalau tidak, mesin Post mirip dengan mesin Turing: ada otomat, dan ada selotip tanpa ujung.

Mesin Pos dapat menjalankan perintah berikut:

1. Tulis 1, pergi ke baris ke-i dari program
2. Tulis 0, pergi ke baris ke-i dari program
3. Geser ke kiri, pergi ke baris ke-i program
4. Geser ke kanan, pergi ke baris ke-i program
5. Lompatan bersyarat: jika ada 0 di sel yang diamati, pergi ke baris ke-i dari program, jika tidak, pergi ke baris ke-j dari program.
6. Berhenti.

Mesin Post juga memiliki beberapa perintah terlarang:

1. Menulis ke sel 1 ketika sudah ada 1.
2. Menulis ke sel 0 ketika sudah ada 0.

Peristiwa seperti itu menyebabkan kecelakaan.

Untuk menulis program untuk mesin pos, Anda dapat menggunakan notasi berikut:

1. i - tulis 1, pergi ke baris ke-i dari program
2. × i - tulis 0, pergi ke baris ke-i dari program
3. i - lakukan shift kiri, pergi ke baris ke-i dari program
4. → i - lakukan pergeseran ke kanan, pergi ke baris ke-i dari program
5. ? Saya; j - lompatan bersyarat: jika ada 0 di sel yang diamati, pergi ke baris ke-i dari program, jika tidak, pergi ke baris ke-j dari program.
6. ! - berhenti.

Contoh program:

1. → 2 2.? 1; 3 3. × 4 4. 5 5.!

Program ini akan menghapus label pertama (1) yang terletak di sebelah kanan posisi awal mesin dan menghentikan mesin di sel di sebelah kirinya.

Pada umumnya, mobil Post adalah pendahulunya imperatif bahasa pemrograman, misalnya C, Fortran, dll.

Mesin Post setara dengan mesin Turing. Dengan kata lain, untuk program apa pun untuk mesin Turing, Anda dapat menulis program yang setara untuk mesin Post, dan sebaliknya.

Salah satu konsekuensi penting dari kesetaraan ini adalah bahwa alfabet apa pun dapat direduksi menjadi kode biner.

Mirip dengan tesis Turing, ada juga tesis Post.

Tesis Post, algoritma apa pun dapat direpresentasikan dalam bentuk mesin Post.

Algoritma Markov Normal

Algoritma Markov normal dirancang untuk diterapkan pada kata-kata dalam alfabet yang berbeda.

Definisi dari setiap algoritma normal terdiri dari dua bagian:

1. Alfabet algoritma
2. Skema algoritma

Algoritma itu sendiri diterapkan pada kata-kata, yaitu, urutan karakter alfabet.

Skema dari algoritma normal disebut himpunan berhingga yang disebut rumus substitusi, yang masing-masing dapat sederhana atau akhir... Ekspresi bentuk \ (L \ ke D \) disebut rumus substitusi sederhana, di mana \ (L \) dan \ (D \) adalah dua kata arbitrer yang disusun dari alfabet algoritma (masing-masing disebut kiri dan kanan). sisi rumus substitusi). Demikian pula, rumus substitusi akhir adalah ekspresi dari bentuk \ (L \ to \ cdot D \), di mana \ (L \) dan \ (D \) adalah dua kata arbitrer yang disusun dari alfabet algoritme.

Diasumsikan bahwa karakter bantu \ (\ to \) dan \ (\ to \ cdot \) tidak termasuk dalam alfabet algoritme.

Proses penerapan algoritma normal ke kata arbitrer \ (V \) adalah urutan tindakan berikut:

1. Biarkan \ (V "\) menjadi kata yang diperoleh pada langkah algoritma sebelumnya (atau kata asli, jika langkah saat ini adalah yang pertama).
2. Jika tidak ada substitusi di antara formula substitusi, yang sisi kirinya akan dimasukkan dalam \ (V "\), maka pekerjaan algoritma dianggap selesai, dan hasil dari pekerjaan ini adalah kata \ (V" \ ).
3. Jika tidak, di antara formula substitusi, yang sisi kirinya termasuk dalam \ (V "\), yang pertama dipilih.
4. Dari semua kemungkinan representasi kata \ (V "\) dalam bentuk \ (RLS \) (di mana \ (R \) adalah awalan, dan \ (L \) adalah akhiran), satu dipilih sedemikian rupa sehingga \ ( R \) adalah yang terpendek diikuti dengan substitusi \ (V "= RDS \).
5. Jika rumus substitusi berhingga, maka algoritma selesai dengan hasil \ (V "\). Jika tidak, lanjutkan ke langkah 1 (langkah berikutnya).

Setiap algoritma normal setara dengan beberapa mesin Turing, dan sebaliknya - setiap mesin Turing setara dengan beberapa algoritma normal.

Sebuah analog dari tesis Turing untuk algoritma normal biasanya disebut prinsip normalisasi.

Contoh

Algoritma ini mengubah bilangan biner menjadi “satuan” (di mana catatan bilangan bulat non-negatif N adalah string dari N tongkat). Misalnya, bilangan biner 101 diubah menjadi 5 batang: |||||.

Alfabet: (0, 1, |) Aturan:

1. 1 → 0|
2. |0 → 0||
3. 0 -> (string kosong)

Baris asli: 101 Eksekusi:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

Fungsi rekursif

Sistem yang setara dengan mesin Turing dapat dibangun berdasarkan fungsi matematika. Untuk ini, kita perlu memperkenalkan kelas fungsi berikut:

• fungsi rekursif primitif
• fungsi rekursif umum
• fungsi rekursif sebagian

Kelas terakhir akan bertepatan dengan kelas fungsi Turing-computable (yaitu, fungsi untuk perhitungan yang algoritma untuk mesin Turing dapat dibangun).

Definisi algoritma melalui fungsi rekursif sebenarnya adalah inti dari kalkulus lambda, dan atas dasar itu pendekatan dibangun pemrograman fungsional.

Fungsi rekursif primitif

Kelas fungsi rekursif primitif berisi: fungsi dasar dan semua fungsi diturunkan dari yang dasar melalui operator substitusi dan rekursi primitif.

Fungsi dasar meliputi:

• Fungsi null \ (O () = 0 \) adalah fungsi tanpa argumen yang selalu mengembalikan \ (0 \).
• Fungsi suksesi \ (S (x) = x + 1 \) adalah fungsi yang menetapkan ke sembarang bilangan asli \ (x \) bilangan berikut \ (x + 1 \)
• Fungsi \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), di mana \ (0

Untuk membangun sisa fungsi kelas, operator digunakan:

• Pergantian. Untuk fungsi \ (f \) dari \ (m \) variabel dan \ (m \) fungsi \ (g_1, \ ldots, g_m \) dari \ (n \) variabel masing-masing, hasil substitusi \ (g_k \) di \ ( f \) adalah fungsi \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \) dari \ (n \) variabel.
• rekursi primitif. Misalkan \ (f (x_1, \ ldots, x_n) \) adalah fungsi dari \ (n \) variabel, dan \ (g (x_1, \ ldots, x_ (n + 2)) \) fungsi dari \ (n + 2 \) variabel. Maka hasil penerapan operator rekursi primitif pada fungsi \ (f \) dan \ (g \) adalah variabel fungsi \ (h \) dari \ (n + 1 \) berbentuk: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Fungsi rekursif sebagian

Kelas fungsi rekursif parsial mencakup fungsi rekursif primitif, dan, sebagai tambahan, semua fungsi yang diperoleh dari fungsi rekursif primitif menggunakan operator minimisasi argumen:

Operator minimalisasi argumen

Biarkan \ (f \) menjadi fungsi dari \ (n \) variabel \ (x_i \ dalam \ mathbb (N) \). Maka hasil penerapan operator minimisasi argumen ke fungsi \ (f \) adalah fungsi \ (h \) dari argumen \ (n-1 \), didefinisikan sebagai:

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] di mana \ Artinya, \ (h \) mengembalikan nilai minimum dari argumen terakhir ke fungsi \ (f \) di mana \ (f \) adalah nol.

Sementara fungsi rekursif primitif selalu dapat dihitung, fungsi rekursif sebagian mungkin tidak didefinisikan untuk beberapa nilai argumen.

Lebih tepatnya, fungsi rekursif sebagian harus disebut "fungsi rekursif yang ditentukan sebagian", karena mereka didefinisikan hanya pada sebagian kecil dari nilai argumen yang mungkin.

Fungsi rekursif umum

Fungsi rekursif umum adalah subkelas dari semua fungsi rekursif sebagian yang didefinisikan untuk nilai argumen apa pun. Masalah menentukan apakah suatu fungsi rekursif parsial yang diberikan adalah rekursif umum adalah: tidak dapat ditentukan secara algoritmik... Ini membawa kita ke topik teori komputabilitas dan masalah penghentian.

Teori komputabilitas dan masalah penghentian

Imajinasi kita umumnya memungkinkan adanya masalah yang tidak dapat dipecahkan, yaitu masalah yang tidak mungkin untuk menyusun algoritma.

Teori komputabilitas berurusan dengan masalah seperti itu.

Contoh masalah yang tidak dapat dipecahkan secara algoritmik adalah: hentikan masalah dan masalah pengenalan daya tetas... Mari kita pertimbangkan mereka secara lebih rinci.

Masalah penghentian Berdasarkan uraian algoritma A dan data masukan \ (x \), perlu diketahui apakah algoritma \ (A \) berhenti pada data masukan \ (x \).

Masalah penghentian secara algoritmik tidak dapat dipecahkan. Mari kita buktikan.

\ (\ Delta \)

Biarkan ada algoritma universal yang memecahkan masalah penghentian. Pertimbangkan kemudian kelas algoritme yang memproses teks yang menjelaskan algoritme.

Karena adanya algoritma universal untuk menyelesaikan masalah penghentian, ada algoritma yang menentukan apakah suatu algoritma dari kelas tersebut akan berhenti pada teksnya sendiri atau tidak. Mari kita tunjukkan algoritma seperti itu dengan \ (B \).

Mari kita buat algoritme \ (C \), data input yang merupakan teks dari algoritme \ (A \), yang memproses teksnya sendiri:

1. Jalankan algoritma \ (B \) di atas \ (A \).
2. Jika algoritme \ (B \) menentukan bahwa \ (A \) akan berhenti pada teksnya, lanjutkan ke langkah 1. Jika tidak, lanjutkan ke langkah 3.
3. Algoritma akhir \ (C \).

Setelah mencoba menerapkan algoritme \ (C \) ke algoritme \ (C \), kami sampai pada kontradiksi yang jelas: jika \ (C \) berhenti pada teksnya sendiri, maka ia tidak dapat berhenti, dan sebaliknya. Oleh karena itu, tidak ada algoritma \ (B \). \ (\ bukan \ Delta \)

Rumusan yang lebih umum dari masalah penghentian adalah masalah mendefinisikan daya tetas.

Masalah pengenalan daya tetas

Biarkan alfabet tertentu, kata-kata (rumus) alfabet ini, dan sistem transformasi formal atas kata-kata alfabet ini didefinisikan (yaitu, kalkulus logis dibangun)

Apakah ada dua kata \ (R \) dan \ (S \) rantai deduktif yang mengarah dari \ (R \) ke \ (S \) dalam kerangka kalkulus logis ini?

Pada tahun 1936, Gereja Alonzo membuktikan teorema Gereja.

Teorema Gereja Masalah mengenali keteruraian secara algoritme tidak dapat dipecahkan.

Gereja menggunakan formalisme kalkulus lambda untuk membuktikannya. Pada tahun 1937, terlepas dari dia, Turing membuktikan teorema yang sama menggunakan formalisme mesin Turing.

Karena semua definisi algoritma setara satu sama lain, ada sistem konsep yang tidak terkait dengan definisi spesifik suatu algoritma, dan beroperasi dengan konsep tersebut. fungsi yang dapat dihitung.

Computable function Fungsi yang dapat dihitung dengan algoritma.

Ada masalah di mana hubungan antara data input dan output tidak dapat dijelaskan menggunakan algoritma. Fungsi-fungsi tersebut adalah tak terhitung.

Contoh fungsi yang tidak dapat dihitung

Ambil fungsi \ (h (n) \) yang didefinisikan untuk \ (\ forall n \ di \ mathbb (N) \) sebagai berikut:

\ [h (n) = \ begin (cases) 1, & \ text (jika di) \ pi \ text (ada urutan persis) n \ text (9-k) \\ 0, & \ text (sebaliknya ) \ akhir (kasus) \]

Kita bisa mendapatkan nilai \ (1 \) untuk fungsi ini, namun, untuk mendapatkan nilai \ (0 \), kita perlu memeriksa ekspansi desimal tak terbatas dari \ (\ pi \), yang jelas tidak mungkin dalam waktu yang terbatas . Dengan demikian fungsi ini tidak dapat dihitung.

Ekspresi pasca 1920-an Mesin hitung mengacu pada mesin apa pun yang melakukan pekerjaan komputer manusia, terutama yang dikembangkan sesuai dengan metode efektif tesis Church-Turing. Tesis ini dirumuskan sebagai: "Algoritme apa pun dapat ditentukan dalam bentuk mesin Turing yang sesuai atau definisi rekursif sebagian, dan kelas fungsi yang dapat dihitung bertepatan dengan kelas fungsi rekursif sebagian dan dengan kelas fungsi yang dapat dihitung pada mesin Turing ." Dengan kata lain, tesis Church-Turing didefinisikan sebagai hipotesis tentang sifat perangkat komputasi mekanis seperti komputer elektronik. Perhitungan apa pun yang memungkinkan dapat dilakukan di komputer, asalkan tersedia waktu dan ruang penyimpanan yang cukup.

Mekanisme yang bekerja pada komputasi dengan tak terhingga dikenal sebagai tipe analog. Nilai dalam mekanisme tersebut diwakili oleh nilai numerik kontinu, misalnya, sudut rotasi poros atau perbedaan potensial listrik.

Tidak seperti mesin analog, mesin digital memiliki kemampuan untuk mewakili keadaan nilai numerik dan menyimpan setiap digit secara terpisah. Mesin digital menggunakan berbagai prosesor atau relay sebelum penemuan perangkat RAM.

Nama Mesin hitung sejak tahun 1940-an, mulai digantikan oleh konsep komputer... Komputer-komputer itu mampu melakukan perhitungan yang biasa dilakukan pegawai. Sejak nilai tidak lagi bergantung pada karakteristik fisik (seperti pada mesin analog), komputer logis berdasarkan perangkat keras digital mampu melakukan segala sesuatu yang dapat dijelaskan. sistem mekanis murni .

Mesin Turing dirancang untuk secara formal mendefinisikan secara matematis apa yang dapat dihitung mengingat kendala pada daya komputasi. Jika mesin Turing dapat menyelesaikan suatu tugas, maka tugas tersebut dianggap Turing dapat dihitung. Turing berfokus terutama pada perancangan mesin yang dapat menentukan apa yang dapat dihitung. Turing menyimpulkan bahwa selama ada mesin Turing yang dapat menghitung perkiraan angka, nilai itu dapat dihitung. Selain itu, mesin Turing dapat menginterpretasikan operator logika seperti AND, OR, XOR, NOT, dan If-then-Else untuk menentukan apakah