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

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

Постовской системой соответствия над алфавитом [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]A = ( x_1 , \ldots , x_k )[/math] и [math]B = ( y_k , \ldots , y_k )[/math], и решением является последовательность из О или нескольких целых чисел [math]i_1, \ldots, i_m[/math] при которой [math]x_1 x_{i_1} \ldots x_{i_k} = y_1 y_{i_1} \ldots y_{i_m}[/math]

Теорема:

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

Литература

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