Durma (Halting) problemi nedir?

Durma (Halting) problemi nedir?

Bir programın belli bir zaman sonra durup durmayacağı belirsizdir. D(P,G) şeklinde bir durup durmamayı bilen program yazıldığını düşünelim. Burada P programı G girdisi ile çalıştığı zaman durup durmayacağını D(P,G) programımız söyleyecek olsun. D(P,G)’nin bir sonuç döndüreceğini kabul ettiğimizden eğer programa kendisini girdi olarak verirsek sonuç döndürmesi beklenir, yani D(P,P) durumu. Fakat böyle bir şey mümkün değildir. Durma (Halting) problemi kararı mümkün olmayan (undecidable) bir problemdir.

Halting makinesi girdi olarak aldığı ifadenin sonucunda makinenin durup durmayacağını belirten makinedir.

durma-halting-makinesi

2 Yorum

  1. halting problemini formal olarak göstermen gerekir. Ayrıca D(P,P)’nin neden durmadığını gösteremediğinden bence halting problemini bir tersleyici yardımı ile her zaman yanlış çalışacağını göstermek daha kolay olabilir. Aşağıdaki animasyon bunu ifade ediyor.
    https://www.youtube.com/watch?v=92WHN-pAFCs

Yorum Yapın