Примеры неразрешимых задач: проблема соответствий Поста

Определение:

Постовской системой соответствия над алфавитом [math]\Sigma[/math] называется упорядоченная пара конечных последовательностей [math](( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))[/math], где [math]x_i \in \Sigma ^*[/math] и [math]x_i \in \Sigma ^*[/math] для всех i.

Определение:

Решением постовской системы соответствия [math](( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))[/math] называется непустая последовательность индексов [math]( i_1 , \ldots , i_k )[/math], удовлетворяющая условию [math] x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}[/math], где [math] 1 \leq i_j \leq n[/math] для каждого j.

Пример

Пусть [math]\Sigma = \{ a , b , c \}[/math]. Рассмотрим постовскую систему соответствия [math]((aab, a, caa),(a, aa, bc))[/math]. Последовательность [math](2,1,3,2,2)[/math] является решением этой системы, так как [math]a \cdot aab \cdot caa \cdot a \cdot a = aa \cdot a \cdot bc \cdot aa \cdot aa[/math].

Определение:

Проблемой соответствий Поста (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.

Теорема:

Пусть [math]| \Sigma | \geq 2[/math]. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом [math]\Sigma[/math] узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.