```Belirlenimsiz Turing makinesi```, klasik Turing makinesi ile ayný temelleri kullanarak çalýþýr:
...
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:
bkz. Turing makinesi
...Detaylý bilgi için linke týklayýnýz.
Melek-vari belirlenimsizlik: bu tip bir belirlenimsizlikte, makine birkaç seçim arasýndan her zaman "doðru" olaný seçer.
Jaakko Hintikka tarafýndan 1972 yýlýnda ``Language games and information`` (``Dil oyunlarý ve bilgi``) isimli kitapta yayýnlanan bir fikir olan melek-vari belirlenimsizlik birkaç seçeneði olunca her zaman kendisini sonuca doðru götürecek olan seçimi yapan bir belirlenimsizlik çeþididir. Buna bazý çevrelerce ``þanslý seçim`` de denir.
...Detaylý bilgi için linke týklayýnýz.
Þeytani belirlenimsizlik: bu tip belirlenimsizlikte ise makine birkaç seçim arasýndan her zaman "yanlýþ" olaný seçer.
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, Jaakko Hintikka tarafýndan 1972 yýlýnda ``Language games and information`` (``Dil oyunlarý ve bilgi``) isimli kitapta yayýnlanan bir fikir olan þeytani belirlenimsizlik birkaç seçeneði olunca her zaman kendisini sonuçsuzluða doðru götürecek olan seçimi yapan bir belirlenimsizlik çeþididir. Buna bazý çevrelerce ``þanssýz seçim`` de denir.
...Detaylý bilgi için linke týklayýnýz.
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).
Seyyar satýcý problemi en önemli algoritma problemlerinden biridir. NP-Tam olan problem þu þekildedir:
...Detaylý bilgi için linke týklayýnýz.
Lütfen dikkat: Bu sayfada kýrmýzý ile linklenen ve iki çizgi ile altý çizilen linkler reklamdýr. Bu linklere týklanýldýðýnda baþka bir siteye yönlenirsiniz.
