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