:::: MENU ::::

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


1 Yorum

  • Cevapla mustafa |

    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.

Görüşlerinizi önemsiyorum...