Yazışma Sonrası Sorunu

1946'da Emil Post tarafından ortaya atılan Yazışma Sonrası Sorunu (PCP), karar verilemez bir karar sorunudur. Bir alfabe ∑ üzerindeki PCP problemi aşağıdaki gibi ifade edilir -

Aşağıdaki iki liste göz önüne alındığında, M ve N ∑ üzerinde boş olmayan dizelerin sayısı -

M = (x 1 , x 2 , x 3 , ………, x n )

N = (y 1 , y 2 , y 3 , ………, y n )

Bazı i 1 , i 2 , ………… i k , burada 1 ≤ i j ≤ n, x i1 …… .x ik = y i1 …… ise bir Yazışma Sonrası Çözüm var diyebiliriz . y ik tatmin ediyor.

örnek 1

Listelerin

M = (abb, aa, aaa) ve N = (bba, aaa, aa)

Bir Yazışma Sonrası Çözümünüz var mı?

Çözüm

x 1 x 2 x 3
M Abb aa aaa
N Bba aaa aa

Buraya,

x2x1x3 = ‘aaabbaaa’

ve y2y1y3 = ‘aaabbaaa’

Bunu görebiliriz

x2x1x3 = y2y1y3

Dolayısıyla çözüm şudur: i = 2, j = 1, and k = 3.

Örnek 2

Listelerin M = (ab, bab, bbaaa) ve N = (a, ba, bab) Bir Yazışma Sonrası Çözümünüz var mı?

Çözüm

x 1 x 2 x 3
M ab bebek Bbaaa
N a ba bebek

Bu durumda çözüm yok çünkü -

| x2x1x3 | ≠ | y2y1y3 | (Uzunluklar aynı değil)

Dolayısıyla, bu Yazışma Sonrası Probleminin undecidable.