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