Sejarah
Diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana sebuah komputer. Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer general-purpose. Mesin Turing dapat digunakan untuk menghitung kelas fungsi bilangan bulat yang dikenal sebagai fungsi rekursif sebagian (partial recursive function).
Alan Mathison Turing, (23 Juni 1912 - 7 Juni 1954), adalah seorang ahli matematika, ahli logika, kriptanalis, dan ilmuwan komputer Inggris. Dia sangat berpengaruh dalam pengembangan ilmu komputer, memberikan formalisasi konsep "algoritma" dan "komputasi" dengan mesin Turing, yang memainkan peran penting dalam penciptaan komputer modern. Turing secara luas dianggap sebagai bapak ilmu komputer dan kecerdasan buatan.
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-pembatasan (non-restricted language), yang disebut juga himpunan terenumerasi rekursif (recursively enumerable set).
Mesin Turing (Turing Machine)
Stack (tumpukan) yang terdapat pada PDA memiliki keterbatasan kemampuan akses, yaitu hanya mengakses data yang terdapat pada top / puncak dari stack. Untuk melakukan akses pada bagian yang lebih rendah dari puncak stack, harus memindahkan bagian di atasnya (pop), yang akan menyebabkan bagian tersebut hilang.
Pada mesin Turing, memori berupa pita yang berupa array (deretan) sel-sel penyimpanan. Setiap sel mampu menyimpan sebuah simbol tunggal. Pita tersebut tidak mempunyai sel pertama dan sel terakhir. Pita dapat memuat informasi dalam jumlah tak terbatas, dan dapat diakses bagian manapun dari pita dengan urutan bagaimanapun. Terdapat sebuah head yang menunjukkan posisi yang diakses pada pita. Head dapat bergerak ke kanan atau ke kiri untuk membaca input dari pita dan sekaligus juga bisa melakukan penulisan pada pita/mengubah isi pita.
Mesin Turing bisa dianalogikan seperti komputer sederhana, dengan sejumlah state sebagai memori, pita sebagai secondary storage, fungsi transisi sebagai program. Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel, yaitu :
M = (Q, Σ, F, 6, S, F, b), dimana :
Q = himpunan state
Σ = himpunan simbol input
F = simbol pada pita (meliputi pula blank)
6 = fungsi transisi
S = state awal, S C Q
F = himpunan state akhir, FS Q
b = simbol kosong (blank) (bukan bagian dari Σ, b ØΣ) Bagian pada pita yang belum ditulis dianggap berisi simbol b .
Model Mesin Turing
Sebuah mesin Turing terdiri dari komponen-komponen :
1. Pengendali berhingga (finite control)
2. Pita masukan dengan sifat:
- panjangnya tidak berhingga (ujung kiri terbatas, ujung kanan tidak terbatas)
- dapat dibaca maupun ditulis
- sel yang tidak berisi simbol masukan akan berisi simbol kosong (blank = B)
Pada keadaan awal, n sel pertama dari pita masukan berisi rangkaian simbol yang harus dikenali (dinyatakan sebagai a1, a2, …, an). Sel di sebelah kanan rangkaian simbol berisi B.
Perbedaan mesin Turing dengan FSA dan PDA
Prinsip Kerja Mesin Turing
Lihat pada State Semula dan simbol yang ditunjuk Head
Berdasarkan fungsi transisinya, tentukan :
- State Berikutnya
- Lakukan Penulisan ke pita
- Gerakan Head kekanan dan ke-kiri
Bila pasangan dari state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya, berarti mesin turing berhenti.
Bila mesin turing berhenti pada state final (F), brarti input diterima. Sebaliknya jika mesin turing tidak berhenti pada state akhir/final(F), maka berarti inputan tersebut ditolak.
Apa yang Dilakukan Mesin Turing?
Mesin Turing terdiri dari pita yang diinisialisasi dengan serangkaian simbol. Mesin memiliki kepala yang membaca dan menulis simbol saat bergerak di sepanjang pita.
Ketika pita itu membaca simbol tertentu, ia memutuskan apa yang harus dilakukan (apa yang akan ditulis ke pita pada titik itu dan kemudian ke arah mana untuk bergerak selanjutnya) tergantung pada set fungsi transisi yang terkait dengan mesin. Fungsi transisi pada dasarnya adalah baris instruksi khusus dalam program mesin Turing. Anda dapat menganggap himpunan fungsi transisi sebagai program lengkap yang menentukan apa yang harus dilakukan mesin Turing pada setiap input valid yang diterimanya.
Dalam praktiknya, fungsi transisi mengambil bentuk berikut
Keadaan apa saya sekarang
Simbol apa yang baru saja saya baca
Simbol apa yang harus saya tulis
Keadaan apa yang harus saya ubah selanjutnya
Ke arah mana saya harus pindah selanjutnya
Urutan input ini dapat bervariasi tergantung pada simulator mesin Turing mana yang digunakan untuk menjalankan mesin , tetapi semua informasi ini akan disertakan.
Pada satu waktu, mesin memiliki head yang ditempatkan di atas salah satu kotak pada pita. Dengan head ini, mesin dapat melakukan tiga operasi yang sangat dasar:
Bacalah simbol di kotak di bawah head.
Edit simbol dengan menulis simbol baru atau menghapusnya.
Pindahkan pita ke kiri kanan sebanyak satu kotak sehingga mesin dapat membaca dan mengedit simbol pada kotak di sebelahnya (tetangga).
Demonstrasi sederhana
Sebagai contoh sederhana untuk mendemonstrasikan operasi ini, mari kita coba mencetak simbol "1 1 0" pada pita yang awalnya kosong
Pertama, kita menulis angka 1 di kotak di bawah head:
Selanjutnya, kita memindahkan pita ke kiri satu kotak
Sekarang, tulis angka 1 di kotak baru di bawah head:
Kemudian memindahkan rekaman itu ke kiri satu kotak lagi:
Terakhir, hanya menuliskan 0
Contoh 1 :
Mesin Turing M akan digunakan untuk mengenali bahasa L = {0n1n | n ³ 1}. Contoh string di dalam L misalnya
01, 0011, 000111, 00001111, dst.
Cara kerja mesin Turing untuk mengenali bahasa L dinyatakan dengan algoritma berikut:
1. Ganti simbol ‘0’ paling kiri dengan simbol ‘X’.
2. Gerakkan head ke kanan hingga dijumpai simbol ‘1’.
3. Ganti simbol ‘1’ paling kiri dengan simbol ‘Y’
4. Gerakkan head ke kiri hingga dijumpai simbol ‘X’
5. Geser head ke kanan (akan diperoleh ‘0’ paling kiri).
6. Kembali ke langkah 1.
Jika pada saat bergerak ke kanan untuk mencari ‘1’ , mesin Turing M menjumpai simbol B, maka berarti banyaknya ‘0’ lebih dari banyaknya ‘1’. Kesimpulannya, string masukan tidak dikenali.
Jika pada saat bergerak ke kiri M tidak menjumpai lagi ‘0’, maka M memeriksa apakah masih ada ‘1’. Bila habis maka string diterima (dikenali).
Jika sebuah string diterima (dikenali), maka mesin Turing M berhenti. Untuk string yang tidak dikenali (ditolak) ada kemungkinan M tidak berhenti (looping).
Contoh 2 :
String masukan adalah 000111
Kesimpulan: string ‘000111’ dikenali oleh mesin M.
Dari penjelasan di atas, terlihat ada empat modus kerja yang berbeda dari mesin Turing:
- Dalam setiap modus kerja (status), aksi yang dilakukan mesin Turing mungkin menerima/membaca berbagai simbol pada pita.
- Aksi yang dilakukan dalam setiap modus kerja (status) dapat berbeda-beda.
Definisi Formal Mesin Turing
Sebuah mesin Turing M dilambangkan dengan notasi formal sbb:
M = (Q, å, G, d, q0, B, F)
yang dalam hal ini,
Q : himpungan berhingga status (a, b, c, … atau q0, q1, q2, …)
G : himpunan berhingga simbol-simbol yang muncul di pita
B Î G: melambangkan simbol blank
å : himpunan symbol input, subset dari G
d : fungsi pergerakan yang memetakan Q ´ G ® Q ´ G ´ {L, R}*)
q0 Î Q : status awal
F Í Q : himpunan status akhir atau accepted states
Dengan menggunakan notasi formal tersebut, maka mesin Turing pengenal bahasa L = {0n1n | n ³ 1} dapat ditulis sbb:
M = (Q, å, G, d, q0, B, F)
yang dalam hal ini,
Q = {q0, q1, q2, q3, q4}
G= {0, 1, X, Y, B}
å= {0, 1, B}
q0 = q0
F = {q4}
d(q0, 0) = (q1, X, R); d(q0, Y) = (q3, Y, R);
d(q1, 0) = (q1, 0, R); d(q1, 1) = (q2, Y, L); d(q1, Y) = (q1, Y, R);
d(q2, 0) = (q2, 0, L); d(q2, X) = (q0, X, L); d(q2, Y) = (q2, Y, L);
d(q3, Y) = (q3, Y, R); d(q3, B) = (q4, B, R);
Referensi
Diktat Teori Bahasa dan Otomata oleh Ir. Sudiadi Stmik MDP
Teori Komputasi oleh RInaldi Munir STEI-ITB