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 ₁ , x ₂ , x ₃ , ………, x _n )

N = (y ₁ , y ₂ , y ₃ , ………, y _n )

Bazı i ₁ , i ₂ , ………… 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,

x₂x₁x₃ = ‘aaabbaaa’

ve y₂y₁y₃ = ‘aaabbaaa’

Bunu görebiliriz

x₂x₁x₃ = y₂y₁y₃

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

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Uzunluklar aynı değil)

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