Belirlenimsiz Turing Makinesi

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

Belirlenimsiz 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, belirlenimsiz Turing makinesi aynı durum için birkaç adım arasından seçim yapabilir. Başka bir deyişle, geçiş tablosunda aşağıdaki gibi girdiler olabilir:

  Güncel Okunan  İşlem  Yeni
  Durum Sembol      Durum
  - - - - - - - - - - - - - - - - - - - - - - - -
  d0   1   Sağa git  d2
  d0   1   Sola git  d1


Bu durumda, ilgili Turing makinesi d0 durumundayken ve 1 sembolünü görürken ister sağa ister sola gidebilir.

İki çeşit belirlenimsizlik vardır:



Belirlenimsiz Turing makinesi, melek-vari bir belirlenimsizlik kullanır ve dolayısıyla her zaman kendini sonuca yaklaştıran seçimi yapacaktır.

Böyle bir makineyi, örneğin, seyyar satıcı problemini çözmek için kullanabiliriz: yanına belirlenimsiz bir Turing makinesi almış olan satıcı, gezmesi gereken şehirlerin en kısa listesine makineyi bir kez çalıştırarak gezilecek şehir sayısı kadar bir zamanda ulaşacaktır (zira makine her şehre geldiğinde bir sonraki şehrin hangisi olduğunu hemen bulabilecek, dolayısıyla şehir sayısı kadar adımda sonuca ulaşacaktır).

Kaynaklar

Vikipedi

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