Belirlenimsiz Turing makinesi

Vikipedi, özgür ansiklopedi

Belirlenimsiz Turing makinesi, bulunduğu durumdan sonraki durum için birden fazla seçenek Turing makinasıdır. Makina aşağıdaki bileşenlerden oluşur:

• 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

Belirlenimli Turing makinasından farklı olarak, 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. Melek-vari belirlenimsiz bir Turing makinasıyla polinomsal zamanda çözülebilen problemler NP kümesini oluşturur. Belirlenimsiz makina, belirlenimli bir Turing makinası ile simüle edilebileceği için belirlenimsiz makinanın çözebildiği problemler kümesi , belirlenimli makinanın çözebildiği problemler kümesine eşittir.