Изменения

Существует Дана упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.

Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема Проблема соответствий Поста неразрешима.)

Полуразрешимость: Возьмём по возрастанию все возможные наборы индексов, применим конкатинацию конкатенацию и сравним. Сошлось - задача решена, иначе - программа зависла.

Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина ТьюринкаТьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.