Teori Bahasa dan Otomata 12 - Turing Machine

sacasca

1. MESIN TURING

2. Mesin Turing: Sejarah Diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana dari sebuah mesin komputasi. Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer general-purpose. Diungkapkan pertama kali dalam sebuah artikel ilmiah berjudul " On Computable Numbers, with an Application to the Entscheidungsproblem ", sebagai jawaban atas ‘masalah keputusan ( decision problem aka entscheidungsproblem )’ .

3. Mesin Turing: Sejarah Entscheidungsproblem "Apakah matematika dapat diputuskan ( decidable )?" . Alan Turing menyimpulkan bahwa tidak ada algoritma umum yang dapat memecahkan Entscheidungsproblem untuk semua pernyataan matematika. Melalui konsep mesin abstraknya, Turing menunjukkan bahwa ada masalah-masalah tertentu yang tidak dapat diputuskan secara algoritmis, termasuk menentukan apakah suatu mesin Turing akan berhenti ( halting problem ).

4. Mesin Turing: Sejarah Sama seperti Finite State Automata dan Push Down Automata yang dapat mengenali bahasa formal, maka mesin Turing juga dapat berperan sebagai mesin pengenal bahasa formal. Bahasa yang dikenali oleh Mesin Turing adalah bahasa tanpa-batasan ( un restricted language ), yang disebut juga himpunan terenumerasi rekursif ( recursively enumerable set ).

5. Mesin Turing, FSA dan PDA Perbedaan mesin Turing dengan FSA dan PDA FSA PDA TM Masukan ( input ) hanya dapat dibaca hanya dapat dibaca dapat dibaca dan ditulis Pengakses ( head ) hanya dapat digerakkan ke kanan hanya dapat digerakkan ke kanan dapat digerakkan ke kiri maupun ke kanan Penyimpan ( memory ) hanya pada state dibantu stack Pita masukan juga berfungsi sebagai tempat penyimpanan yang tidak dibatasi pengaksesannya

6. Mesin Turing: Cara Kerja Sebuah mesin Turing terdiri dari komponen-komponen: 1. Pengendali berhingga ( finite state control ) 2. Pita masukan dengan sifat: - panjangnya tak berhingga (ujung kiri dan ujung kanan tidak terbatas), - dapat dibaca maupun ditulis, - pada keadaan awal, n sel pertama dari pita masukan berisi rangkaian simbol yang harus dikenali (dinyatakan sebagai a 1 , a 2 , …, a n ), - sel yang tidak berisi simbol masukan akan berisi simbol kosong ( blank = B). - s el yang berisi rangkaian simbol B berada di sebelah kanan d an kiri .

7. Mesin Turing: Cara Kerja Perilaku mesin Turing bergantung pada simbol masukan yang berada pada posisi head (baca/tulis) dan state dari Finite Control . Setelah membaca simbol masukan, mesin Turing melakukan aksi berikut: Berpindah state . Menuliskan simbol pada pita. Menggerakkan head ke kiri atau ke kanan. Ada 3 kemungkinan yang terjadi setelah proses komputasi: Berh enti dan diterima . Berhenti dan ditolak . Tidak akan berhenti ( infinite loop ) .

8. Mesin Turing: Konfigurasi Sebuah Mesin Turing secara formal dinyatakan dalam 7 tupel, M={Q, ∑, Γ, δ, S, F, b }, di mana: Q = himpunan state ∑ = himpunan simbol masukan Γ = himpunan simbol pita yang ditulis atau dibaca ke dalam pita δ = fungsi transisi S = state awal F = himpunan state akhir b = simbol kosong ( blank ) bagian dari pada pita yang belum ditulisi dianggap berisi simbol b .

9. Mesin Turing: Contoh 1 Terdapat mesin Turing: Q = {q1, q2} ∑ = {a, b} Γ = {a, B} S = q1 F = {q2}   Fungsi transisinya: δ(q1, a) = (q1, a, R) δ(q1, b) = (q1, a, R) δ(q1, B) = (q2, B, L)  

10. Mesin Turing: Ilustrasi Contoh 1 Misal pita yang akan dibaca ‘abbaa’, maka: δ(q 1, a)=(q 1, a, R) menyebabkan head bergerak ke kanan δ(q 1, b)=( q 1, a, R) menyebabkan head menulis ‘a’ lalu bergerak ke kanan δ(q 1, b)=( q 1, a, R) menyebabkan head menulis ‘a’ lalu bergerak ke kanan δ(q 1, a)=( q 1, a, R) menyebabkan head bergerak ke kanan δ(q 1, a)=( q 1, a, R) menyebabkan head bergerak ke kanan head menunjuk B, δ(q 1, B)=( q 2, B, L) menyebabkan head bergerak ke kiri Tidak ada transisi lagi dari state q 2, mesin turing akan berhenti ( halt ) karena state q 2 termasuk state akhir berarti input tersebut diterima .

11. Mesin Turing: Contoh 2 (0 n 1 n ) Sebuah Mesin Turing akan digunakan untuk mengenali bahasa L = {0 n 1 n | n ≥ 1}. L = {01, 0011, 000111, 00001111, dst.}

12. Mesin Turing: Solusi 0 n 1 n Untuk mengenali bahasa L , mesin Turing akan bekerja dengan algoritma berikut: 0. Baca simbol paling kiri, jika simbol = ‘0’ maka lakukan langkah 1 1. Ganti simbol ‘0’ paling kiri dengan simbol ‘X’. 2. Gerakkan head ke kanan, jika yang ditemukan - simbol ‘1’ maka lakukan langkah 3, - simbol = ‘B’ maka untai ditolak. 3. Ganti simbol ‘1’ dengan simbol ‘Y’ 4. Gerakkan head ke kiri hingga dijumpai simbol ‘X’ 5. Geser head ke kanan, jika yang ditemukan: - simbol = ‘0’ maka kembali ke langkah 1, - simbol = ‘B’ maka untai diterima. - simbol = ‘1’ maka untai ditolak.

13. Contoh: String masukan adalah 000111 ‹#› X 1 1 1 B B ... Y 1 1 B B ... X X Y 1 1 B B ... X 1 1 B B ... X Y Mesin Turing: Ilustrasi 0 n 1 n

14. ‹#› Y Y 1 B B ... X X Y Y 1 B B ... X X Y Y 1 B B ... X X X Y Y B B ... X X X Y Kesimpulan: string ‘000111’ dikenali oleh mesin M . Y Y B B ... X X X Y Mesin Turing: Ilustrasi 0 n 1 n

15. Konfigurasi mesin Turing: Q = {q , q 1 , q 2 , q 3 , q 4 } ∑ = {0, 1} Γ = {0, 1, X, Y, B} S = q F = {q 4 } δ 1 X Y B q ( q 1, X, R) - - ( q 3, Y, R) - q 1 ( q 1, 0, R) ( q 2, Y, L) - ( q 1, Y, R) - q 2 (q 2, 0, L) - ( q 0, X, R) ( q 2, Y, L) - q 3 - - - ( q 3, Y, R ) ( q 4, B, L) ( q 4 ) - - - - - Mesin Turing: Contoh 2 (0 n 1 n ) Tabel transisi: Diagram transisi:

16. Mesin Turing: Contoh 2 (0 n 1 n ) Diagram transisi:

17. Kita lihat bagaimana mesin Turing tersebut beroperasi (head ditunjukkan oleh ↑): 2. 3. 4. 1. Misalkan pita yang akan di baca : ‘0011 ’ ↑q0 ↑q1 ↑ q1 ↑ q2

18. 5. 6. 7. 8. 9. ↑ q2 ↑ q0 ↑ q1 ↑ q1 ↑ q2

19. 10. 11. 12. 13. 14. Kesimpulan : Tidak ada transisi lagi dari state q 4 , mesin Turing akan berhenti. Karena state q 4 termasuk state akhir, maka input tersebut diterima . ↑ q2 ↑ q0 ↑ q3 ↑ q3 ↑ q4

20. Mesin Turing: Latihan Misal, kita mempunyai mesin Turing M 1 , dengan konfigurasi: Q = {q 1 , q 2 , q 3 , q 4 } Σ = {a} Γ = (a, b ) S = {q 1 } F = {q 4 } Tentukan beberapa string yang diterima dan ditolak oleh mesin M 1 ! dengan fungsi transisi: δ(q 1 , a) = (q 2 , a, R) δ(q 1 , b ) = (q 2 , b , R) δ(q 2 , a) = (q 3 , a, R) δ(q 2 , b ) = (q 3 , b , L ) δ(q 3 , a) = (q 4 , a, R) δ(q 3 , b ) = (q 4 , b , R)