Masalah Pasca Korespondensi

The Post Correspondence Problem (PCP), yang diperkenalkan oleh Emil Post pada tahun 1946, adalah masalah keputusan yang tidak dapat diputuskan. Soal PCP atas alfabet ∑ dinyatakan sebagai berikut -

Diberikan dua daftar berikut, M dan N dari string tidak kosong di atas ∑ -

M = (x ₁ , x ₂ , x ₃ , ………, x _n )

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

Solusi Pasca Korespondensi dapat dikatakan ada, jika untuk beberapa i ₁ , i ₂ , ………… i _k , dimana 1 ≤ i _j ≤ n, kondisi x _i1 …… .x _ik = y _i1 ……. y _ik memuaskan.

Contoh 1

Temukan apakah daftar

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

punya Solusi Pasca Korespondensi?

Larutan

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

Sini,

x₂x₁x₃ = ‘aaabbaaa’

dan y₂y₁y₃ = ‘aaabbaaa’

Kita bisa lihat itu

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

Oleh karena itu, solusinya adalah i = 2, j = 1, and k = 3.

Contoh 2

Temukan apakah daftar M = (ab, bab, bbaaa) dan N = (a, ba, bab) punya Solusi Pasca Korespondensi?

Larutan

	x 1	x 2	x 3
M	ab	bab	bbaaa
N	Sebuah	ba	bab

Dalam kasus ini, tidak ada solusi karena -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Panjangnya tidak sama)

Oleh karena itu dapat dikatakan bahwa Masalah Pasca Korespondensi ini adalah undecidable.