Turing Makinesi Örnek
 

Örnek

Örneğimizdeki Turing makinesi sembol havuzu (yani alfabe) olarak {'B', '1'} kullanmaktadır. Bu makineni amacı, verilen girdinin en sağına 1 ekleyip girdinin en soluna geri dönmektir.

Bu amaca ulaşabilmek için, {'d0', 'd1', 'd2'} şeklinde üç durum kullanacağız. Bu durumların geçiş tablosu ise şu şekilde olacak:


Güncel Okunan İşlem Yeni

Durum Sembol Durum

- - - - - - - - - - - - - - - - - - - - - - - -

d0 1 Sağa git d0

d0 B 1 yaz d1

d1 1 Sola git d1

d1 B Sağa git d2


Makine, ilk başta d0 durumunda olacak. Bu tabloya bakarak görebiliriz ki, d2 son durum olacak ve makinenin kafası şu işlemi yapacak:


1 sembolünü gördükçe sağa doğru gidecek.

B sembolünü gördüğü an (yani girdinin en sağına ulaştığında) o sembol yerine 1 yazacak.

Yazma işlemi bitince 1 sembolü gördükçe sola gidecek.

B sembolünü gördüğü an (yani girdinin en soluna ulaştığında) bir adım sağa gidecek ki girdinin ilk harfine doğru bakıyor olsun.


Birkaç denemeyle bu makinenin istediğimiz işlemi yaptığını görebiliriz.


Kaynak : Wikipedia