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ı ifadeyi üretmek mümkünken, bazılarında bu mümkün değildir.
M = (x1,x2,x3)=(abb, aa, aaa) dersek.
N = (y1,y2,y3)=(bba, aaa, aa) dersek.
x2x1x3 = ‘aaabbaaa’ ve y2y1y3 = ‘aaabbaaa’ olduğunu görürüz böylece x2x1x3 = y2y1y3 olur. Fakat
M = (ab, bab, bbaaa) ve N = (a, ba, bab) listeleri için aynı şekilde bir ifade oluşturmaya çalıştığımızda:
| x2x1x3 | ≠ | y2y1y3 | ifadelerin uzunluklarının dahi tutmadığı görülmektedir. İşte bu durumdan dolayı Post Correspondence Problemi karar verilemez (undecidable) bir problemdir.
Daha biçimsel anlatımı, farklı bir örneği ve ispatı için tıklayınız
Videolu anlatım:
Bit match var mı sorusuna makine evet ya da hayır cevabı verebilir mi?
Varsa verecektir peki yoksa?
Kümelerinin tekrarlanabildiğini de unutmamak gerekir.