Kâhinli Turing makinesi
Kâhinli 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, kâhinli Turing makinesi özel bir duruma sahiptir: kâhine soru durumu. Başka bir deyişle, geçiş tablosunda şu şekilde bir giriş bulunur:
| Güncel durum | Okunan simge | Yeni durum 1 | Yeni durum 2 |
|---|---|---|---|
| dk | s | dk1 | dk2 |
Bu durumda, dk durumunda s sembolü okunursa kâhine gidilecektir. Kâhin, makineyi sorunun cevabı evet ise dk1, hayır ise dk2 durumuna geçirecektir. Kâhinin Turing makinesinin tüm şeritlerini okuma ve değiştirme hakkı vardır.
Kâhinli Turing makinesi, NP-complete problem indirgemesi yapılırken kullanılır, zira bir problemin (yani kâhinin) başka bir problemin çözümünde nasıl kullanılabileceğini göstermektedir.