MESIN TURING (Cara Kerja Mesin Turing)

* Mesin Turing

•Pada PDA (Push Down Otomata) digunakan stack untuk menyimpan dan mengakses data inputan. Tetapi hal ini menyebabkan kemampuan kerja PDA yang terbatas karena pada prinsip stack,hanya data teratas yang bisa diakses. Ini menyebabkan keterbatasan PDA.

•Mesin turing menggunakan pita (tape) sebagai memori yang berbentuk array . Hal ini menyebabkan data pada pita dapat diakses dari mana saja.

*Spesifikasi Mesin Turing

1.Mesin turing memiliki pita berupa array sebagai memori yang dapat menyimpan sebuah simbol tunggal

2.Mesin turing memiliki head sebagai penunjuk posisi yang sedang diakses pada pita

3.Head dapat bergerak kekanan/kekiri pada pita sesuai fungsi transisi yang ditetapkan untuk membaca inputan

4.Head juga  dapat melakukan penulisan/ mengubah isi pita

*Sebuah mesin turing secara formal dinyatakan dalam 7 tupel,

M = (Q, S, G, d, S, F, b)

Dimana:

Q =  himpunan state

 S = himpunan simbol input

 G = simbol pada pita,termasuk blank

 d = fungsi transisi

 S = state awal (S anggota elemen Q)

 F = himpunan state akhir

 b = simbol kosong (menandakan bagian yang tidak terisi)

*Pembacaan fungsi transisi pada mesin turing

Misal :

 d (q1,a) = (q1,b,R) dibaca :

Pada state q1 yang menunjukkan karakter a pada pita, maka karakter pada state tersebut berubah menjadi b dan head bergerak ke kanan dengan menunjuk array sebagai  state q1

*Prinsip Kerja mesin Turing

1.Lihat state semula dan simbol yang ditunjuk head

2.Berdasarkan fungsi transisinya,tentukan:

-state berikutnya

-Lakukan penulisan ke pita

-Gerakkan head ke kanan dan ke kiri

3.Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti

4.Bila mesin turing berhenti di dalam state final (F) , berarti input diterima. Sebaliknya jika mesin berhenti tidak pada state akhir,maka berarti inputan tersebut ditolak.