Turing makinesi Örnek

[iGrand]

Türkiye'de ilk Mobil & PC Aynı Anda Metin2 Oyna. Triarchonline kalıcı ve uzun ömürlü yapısı ile 24 Temmuz'da açılıyor. | 1-99 Mobil Metin2 Triarch HEMEN TIKLA!

Ö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 durum	Okunan simge	İşlem	Yeni durum
d0	1	Sağa git	d0
d0	B	1 yaz	d1
d1	1	Sola git	d1
d1	B	Sağa git	d0

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.