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

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

Постовской системой соответствия над алфавитом [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.

Литература

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