MESIN TURING

MESIN TURING

Mesin Turing adalah model komputasi teoretis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak

Mesin turing mempunyai 7 Tuple

            M = (Q, å, G, d, S, F, q)

            Q         = himpunan state

            å         = Himpunan simbol input

            G          = simbol pada pita

            d          = fungsi transisi

            S          = state awal, S Î Q

            F          = himpunan state akhir

            b          = simbol kosong (blank)

           

Contoh :

            Terdapat mesin turing dengan konfigurasi

            Q         = { q₁, q₂ }

             å        = { a, b }

             G         = {  a, b, b  }

             F         = { q₂ }                                     R  = Right

             S         = { q₁ }                                     L  = Left

Fungsi transisi

d          ( q₁, a)            =  (q₁, a, R)

d          ( q₁, b)            =  (q₁, a, R)

d          (q₁, b )            =  (q₂, b ,L)

- d (q₁, a)         = (q₁, a, R)

State q₁, head menunjuk karakter ‘a’ pada pita menjadi state q₁, head bergerak ke kanan.

- d (q₁, b)         = (q₁, a, R)

State q₁,  head menunjuk karakter ‘b’ pada pita menjadi state q₁, head menulis karakter ‘a’ lalu bergerak ke kanan

- d ( q₁, b )       = (q₂, b , L)

Pada State q₁,  head menunjuk karakter ‘ b ’ pada pita menjadi state q₂, head bergerak ke kiri.

Jika mesin turing tersebut menerima input ‘abbaa’, apakah diterima oleh mesin turing atau ditolak