mesin turing

MESIN TURING

• 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 mana akan menyebabkan bagian tersebut hilang.

• Pada mesin Turing, memori berupa suatu pita yang pada dasarnya 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, Σ, Γ, δ, S, F, b) dimana :

Q = himpunan state

Σ = himpunan simbol input

Γ = simbol pada pita (meliputi pula blank)

δ = fungsi transisi

S = state awal, S ∈ Q

F = himpunan state akhir, F⊆ Q

b = simbol kosong (blank) 􀃆 bukan bagian dari Σ, b ∉Σ

Bagian dari pita yang belum ditulisi dianggap berisi simbol b (blank)

• Contoh :

Misal terdapat mesin Turing :

Q = {q1,q2}

Σ = {a,b}

Γ = {a,b, b)

F = {q2}

S = {q1}

Fungsi transisinya : Pergerakan mesin Turing : R = right(kanan), L = left (kiri)

δ (q1,a) = (q1,a,R) 􀃎 pada state q1, head menunjuk karakter ‘a’ pada pita, menjadi state q1, head

bergerak ke kanan

δ (q1,b) = (q1,a,R) 􀃎 pada state q1, head menunjuk karakter ‘b’ pada pita, menjadi state q1, head

menulis karakter ‘a’ lalu bergerak ke kanan

δ (q1, b ) = (q2, b ,L) 􀃎 pada state q1, head menunjuk karakter ‘ b ’ pada pita menjadi state q2,

head bergerak ke kiri

Perhatian : pada mesin Turing

δ (q,x) = (q,y,G)

bila x <> y, maka head akan menulis simbol y (menimpa x) sebelum bergerak sesuai G

(kiri / kanan)

Jadi berdasarkan fungsi transisi diatas, maka mesin Turing beroperasi seperti berikut :

Head ditunjukkan dengan

1. Misal pita yang akan dibaca : ‘abbaa’

a

b

b

a

a

state q1

Fungsi transisi δ (q1,a) = (q1,a,R) menyebabkan head bergerak ke kanan

37

2.

a

b

b

a

a

state q1

Fungsi transisi δ (q1,b) = (q1,a,R) menyebabkan head menulis ‘a’ lalu bergerak ke kanan

3.

a

a

b

a

a

state q1

Fungsi transisi δ (q1,b) = (q1,a,R) menyebabkan head menulis ‘a’ lalu bergerak ke kanan

4.

a

a

a

a

a

state q1

Fungsi transisi δ (q1,a) = (q1,a,R) menyebabkan head bergerak ke kanan

5.

a

a

a

a

a

state q1

Fungsi transisi δ (q1,a) = (q1,a,R) menyebabkan head bergerak ke kanan

6.

a

a

a

a

a

b

state q1

Head menunjuk b, karena bagian pita yang belum ditulisi dianggap berisi b

Fungsi transisi δ (q1, b ) = (q2, b ,L) menyebabkan head bergerak ke kiri

7.

a

a

a

a

a

b

state q2

Tidak ada transisi lagi dari state q2, mesin Turing akan berhenti (halt state)

Karena state q2 termasuk state akhir berarti input tersebut diterima

• Contoh :

Misal konfigurasi mesin Turing :

Q = {q0,q1,q2,q3,q4}

Σ = {0,1}

Γ = {0,1,X,Y, b)

F = {q4}

S = {q0}

Fungsi transisinya dalam bentuk tabel sebagai berikut :

δ

0

1

X

Y

b

q0

(q1,X,R)

-

-

(q3,Y,R)

-

q1

(q1,0,R)

(q2,Y,L)

-

(q1,Y,R)

-

q2

(q2,0,L)

-

(q0,X,R)

(q2,Y,L)

-

q3

-

-

-

(q3,Y,R)

(q4, b ,L)

q4

-

-

-

-

38

1. Misal pita yang akan dibaca : ‘0011’

0

0

1

1

state q0

2.

X

0

1

1

state q1

3.

X

0

1

1

state q1

4.

X

0

Y

1

state q2

5.

X

0

Y

1

state q2

6.

X

0

Y

1

state q0

7.

X

X

Y

1

state q1

8.

X

X

Y

1

state q1

9.

X

X

Y

Y

state q2

10.

X

X

Y

Y

state q2

11.

X

X

Y

Y

state q0

12.

X

X

Y

Y

state q3

39

13.

X

X

Y

Y

state q3

14.

X

X

Y

Y

b

state q4

Tidak ada transisi lagi dari state q4, mesin Turing berhenti dan karena state q4 termasuk state akhir, maka input tersebut diterima.

DESKRIPSI SEKETIKA PADA MESIN TURING

• Tahapan transisi nomor (1) sampai (14) pada contoh diatas dapat dinyatakan dalam notasi yang disebut deskripsi seketika (instantaneous description).

• Deskripsi seketika diperlukan untuk menyatakan secara formal konfigurasi mesin Turing pada suatu saat.

• Perubahan dari suatu kondisi ke berikutnya dipisahkan dengan tanda ‘ | ‘

Untuk simbol head ditulis dengan garis bawah ‘_’

• Jadi tahapan no. 1 sampai 14 dapat dinyatakan sebagai berikut :

(q0,0011) | (q1,X011) (q1,X011) (q2,X0Y1) (q2,X0Y1) (q0,X0Y1) (q1,XXY1) (q1,XXY1) (q2,XXYY) (q2,XXYY) (q0,XXYY) (q3,XXYY) (q3,XXYY b) (q4,XXYY b)

• Misal bila mendapat input 011 :

(q0,011) (q1,X11) (q2,XY1) (q0,XY1) (q3,XY1)

Tidak ada transisi (q3,1) maka mesin berhenti dan karena q3 tidak termasuk state akhir berarti input tersebut ditolak.