Kâhinli Turing makinesi

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

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.