Turing Makinesi Değişik Turing Makineleri

Değişik Turing makineleri

Anlatılan Turing makinesi, yapılabilecek en basit makinedir Bunu şu şekilde geliştirebiliriz:


Beş girdili geçiş tablolu Turing makinesi: bu makine, bir sembol okuyup gerekli işlemi yaptıktan sonra hem yeni bir sembol yazıp hem de aynı anda kafasının yerini değiştirebilir

Birkaç şerit okuyuculu Turing makinesi: bu makine, birkaç şeride aynı anda okuyup yazabildiği için paralel işlem yapabilir


Buna ek olarak, anlatılan Turing makinesi belirlenimci (determinist) bir makinedir, başka bir deyişle aynı girdi için her zaman aynı çıktıyı üretir:


Belirlenimsiz Turing makinesi (İngilizce Non Deterministic Turing machine), çalışmaya başlamadan önce şeride rastgele bir sembol dizisi yazar, bu aşamaya tahmin etme aşaması (İngilizce guessing stage) denir NP problem grubunun tanımı bu makine ile yapılabilir

Kahinli Turing makinesi (İngilizce Oracle Turing machine), anlatılan donanımlara ek olarak bir kahin içerir Turing makinesi, bu kahine bir soru sorabilir, kahin de bu soruyu cevaplayacaktır NP complete problem indirgemesi bu makine ile yapılabilir


Kaynak : Wikipedia