Problema di posta elettronica

Il Post Correspondence Problem (PCP), introdotto da Emil Post nel 1946, è un problema decisionale indecidibile. Il problema PCP su un alfabeto ∑ è indicato come segue:

Dati i due elenchi seguenti, M e N di stringhe non vuote su ∑ -

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

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

Possiamo dire che esiste una Soluzione Post Corrispondenza, se per alcuni i ₁ , i ₂ , ………… i _k , dove 1 ≤ i _j ≤ n, la condizione x _i1 …… .x _ik = y _i1 ……. y _ik soddisfa.

Esempio 1

Trova se gli elenchi

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

hai una soluzione per la corrispondenza postale?

Soluzione

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

Qui,

x₂x₁x₃ = ‘aaabbaaa’

e y₂y₁y₃ = ‘aaabbaaa’

Possiamo vederlo

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

Quindi, la soluzione è i = 2, j = 1, and k = 3.

Esempio 2

Trova se gli elenchi M = (ab, bab, bbaaa) e N = (a, ba, bab) hai una soluzione per la corrispondenza postale?

Soluzione

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

In questo caso, non c'è soluzione perché:

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Le lunghezze non sono le stesse)

Quindi, si può dire che questo problema di corrispondenza postale è undecidable.