undecidable

Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz?

Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz? Post Correspondence Problemi, 1946 yılında Emil Post tarafından açıklanmış karar verilemez (undecidable) bir karar problemidir. Örnek: M = (abb, aa, aaa) ve N = (bba, aaa, aa) şeklinde…

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…