Belirlenimsiz Turing makinesi

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:

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
durum
Okunan
simge
İşlem Yeni
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, melekimsi bir belirlenimsizlik kullanır ve dolayısıyla her zaman kendini sonuca yaklaştıran seçimi yapacaktır. Melekimsi 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.

This article is issued from Vikipedi - version of the 7/9/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.