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 thoughts on “Durma (Halting) problemi nedir?

    mustafa

    (9 Haziran 2017 - 01:00)

    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

      Ahmet Cevahir ÇINAR

      (9 Haziran 2017 - 13:14)

      Sayın mustafa, ek bilgi ve video için teşekkürler. Videonun bulunduğu kanalda çok güzel simülasyonlar varmış. İyi ki öğrendim.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir