```Kahinli Turing makinesi```, klasik Turing makinesi ile aynı temelleri kullanarak çalışır:
...
Kahinli 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, kahinli Turing makinesi özel bir duruma sahiptir: kahine soru durumu. Başka bir deyişle, geçiş tablosunda şu şekilde bir giriş bulunur:
Güncel Okunan Yeni Yeni
Durum Sembol Durum 1 Durum 2
- - - - - - - - - - - - - - - - - - - - - - - -
dk s dk1 dk2
Bu durumda, dk durumunda s sembolü okunursa kahine gidilecektir. Kahin, makineyi sorunun cevabı evet ise dk1 hayır ise dk2 durumuna geçirecektir. Kahinin Turing makinesinin tüm şeritlerini okuma ve değiştirme hakkı vardır.
Kahinli Turing makinesi, bkz. Turing makinesi
...Detaylı bilgi için linke tıklayınız.
NP-complete problem indirgemesi yapılırken kullanılır, zira bir problemin (yani kahinin) başka bir problemin çözümünde nasıl kullanılabileceğini göstermektedir.
Lütfen dikkat: Bu sayfada kırmızı ile linklenen ve iki çizgi ile altı çizilen linkler reklamdır. Bu linklere tıklanıldığında başka bir siteye yönlenirsiniz.
