AlmorA

 

Belirlenimsiz Turing makinesi, klasik Turing makinesi ile aynı temelleri kullanarak çalışır:

Bir veya birkaç şerit
Şerit(ler)i okumak için kafa(lar)
Geçiş tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık
Öte yandan, belirlenimsiz Turing makinesi aynı durum için birkaç adım arasından seçim yapabilir. Başka bir deyişle, geçiş tablosunda aşağıdaki gibi girdiler olabilir:

Güncel Okunan İşlem Yeni
Durum Sembol Durum
- - - - - - - - - - - - - - - - - - - - - - - -
d0 1 Sağa git d2
d0 1 Sola git d1
Bu durumda, ilgili Turing makinesi d0 durumundayken ve 1 sembolünü görürken ister sağa ister sola gidebilir.

İki çeşit belirlenimsizlik vardır:

Melek-vari belirlenimsizlik: bu tip bir belirlenimsizlikte, makine birkaç seçim arasından her zaman "doğru" olanı seçer.
Şeytani belirlenimsizlik: bu tip belirlenimsizlikte ise makine birkaç seçim arasından her zaman "yanlış" olanı seçer.
Belirlenimsiz Turing makinesi, melek-vari bir belirlenimsizlik kullanır ve dolayısıyla her zaman kendini sonuca yaklaştıran seçimi yapacaktır.

Böyle bir makineyi, örneğin, seyyar satıcı problemini çözmek için kullanabiliriz: yanına belirlenimsiz bir Turing makinesi almış olan satıcı, gezmesi gereken şehirlerin en kısa listesine makineyi bir kez çalıştırarak gezilecek şehir sayısı kadar bir zamanda ulaşacaktır (zira makine her şehre geldiğinde bir sonraki şehrin hangisi olduğunu hemen bulabilecek, dolayısıyla şehir sayısı kadar adımda sonuca ulaşacaktır).

_____________________