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, называется '''проблемой соответствий Поста (ПСП)'''.
}}
{{Теорема
|statement=
Не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)
}}
