Проблема с почтовой корреспонденцией

Проблема почтовой корреспонденции (PCP), представленная Эмилем Постом в 1946 году, является неразрешимой проблемой для решения. Задача PCP над алфавитом ∑ формулируется следующим образом:

Учитывая следующие два списка, M и N непустых строк над ∑ -

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

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

Мы можем сказать, что существует Пост-Корреспондентское Решение, если для некоторых i ₁ , i ₂ , ………… i _k , где 1 ≤ i _j ≤ n, выполняется условие x _i1 …… .x _ik = y _i1 ……. y _ik удовлетворяет.

Пример 1

Найдите ли списки

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

есть решение для почтовой переписки?

Решение

	х 1	х 2	х 3
M	Abb	аа	ааа
N	Bba	ааа	аа

Вот,

x₂x₁x₃ = ‘aaabbaaa’

и y₂y₁y₃ = ‘aaabbaaa’

Мы видим, что

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

Следовательно, решение i = 2, j = 1, and k = 3.

Пример 2

Найдите ли списки M = (ab, bab, bbaaa) и N = (a, ba, bab) есть решение для почтовой переписки?

Решение

	х 1	х 2	х 3
M	ab	бабушка	bbaaa
N	а	ба	бабушка

В этом случае решения нет, потому что -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Длина не одинакова)

Следовательно, можно сказать, что эта проблема пост-корреспонденции является undecidable.