Etiket Arşivleri: 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 a ve b sembollerinden oluşmuş 2 listemiz olsun. Bu iki listenin elemanlarının bazı kombinasyonlarında aynı>>>

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>>>