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:

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.

Hesaplama modelleri
Turing makinesi