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 durumOkunan simgeYeni durum 1Yeni durum 2
dksdk1dk2

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.