Türkçe Bilgi logo TürkçeBilgi

Kâhinli Turing Makinesi

Kısaca: Kâhinli Turing makinesi, klasik Turing makinesi ile aynı temelleri kullanarak çalışır: ...devamı ☟

Kahinli 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, kahinli Turing makinesi özel bir duruma sahiptir: kahine soru durumu. Başka bir deyişle, geçiş tablosunda şu şekilde bir giriş bulunur: 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.

Bu konuda henüz görüş yok.
Görüş/mesaj gerekli.
Markdown kullanılabilir.