Изменения

'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') - один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.

Даны два конечных списка <tex>A = (a_1, \ldots, a_n)</tex> и <tex>B = (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, называется '''проблемой соответствий Поста (ПСП)''' (англ. ''Post correspondence problem''). Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.