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

Bir cevap yazın

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