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

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

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

M = (x 1 , x 2 , x 3 , ………, x n )

N = (y 1 , y 2 , y 3 , ………, y n )

Мы можем сказать, что существует Пост-Корреспондентское Решение, если для некоторых i 1 , i 2 , ………… 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 ааа аа

Вот,

x2x1x3 = ‘aaabbaaa’

и y2y1y3 = ‘aaabbaaa’

Мы видим, что

x2x1x3 = y2y1y3

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

Пример 2

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

Решение

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

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

| x2x1x3 | ≠ | y2y1y3 | (Длина не одинакова)

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