153
правки
Изменения
Нет описания правки
|definition=
Дана упорядоченная пара конечных последовательностей <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>, т.е. для '''МПСП'''. {{Определение|definition='''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <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>\forall i</tex>.}}Считаем, что '''Машина Тьюринга''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex> - недопуск. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = Y</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.
<tex>a_1 = \$ \#_s \omega \$</tex>, <tex>b_1 = \$</tex>.
