Belirlenimsiz Turing makinesi

Vikipedi, özgür ansiklopedi

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:

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).