Problem nach der Korrespondenz

Das 1946 von Emil Post eingeführte Post Correspondence Problem (PCP) ist ein unentscheidbares Entscheidungsproblem. Das PCP-Problem über ein Alphabet ∑ wird wie folgt angegeben:

Angesichts der folgenden zwei Listen M und N von nicht leeren Strings über ∑ -

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

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

Wir können sagen, dass es eine Post-Korrespondenzlösung gibt, wenn für einige i ₁ , i ₂ , ………… i _k , wobei 1 ≤ i _j ≤ n, die Bedingung x _i1 …… .x _ik = y _i1 ……. y _ik befriedigt.

Beispiel 1

Finden Sie heraus, ob die Listen

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

Haben Sie eine Post-Korrespondenz-Lösung?

Lösung

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

Hier,

x₂x₁x₃ = ‘aaabbaaa’

und y₂y₁y₃ = ‘aaabbaaa’

Wir können das sehen

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

Daher ist die Lösung i = 2, j = 1, and k = 3.

Beispiel 2

Finden Sie heraus, ob die Listen M = (ab, bab, bbaaa) und N = (a, ba, bab) Haben Sie eine Post-Korrespondenz-Lösung?

Lösung

	x 1	x 2	x 3
M.	ab	bab	bbaaa
N.	ein	ba	bab

In diesem Fall gibt es keine Lösung, weil -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Längen sind nicht gleich)

Daher kann gesagt werden, dass dieses Problem nach der Korrespondenz besteht undecidable.