Изменения

Дана упорядоченная пара конечных последовательностей <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, называется '''проблемой соответствий Поста (ПСП)'''.

{{ТеоремаОпределение|definition=Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов <tex>i_1 = 1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.}} {{Утверждение

Язык имеющих пар последовательностей, для которых решение проблем соответствий поста ПСП положительно, перечислим, но не разрешим.

Полуразрешимость: возможно взять по возрастанию все возможные наборы Пусть даны последовательности <tex>a_n, b_n</tex> из условия ПСП. Количество последовательностей индексов, применить конкатенацию и сравнить полученные строкикаждый из которых находится в пределах от 1 до <tex>n</tex>, длины <tex>m</tex> равно <tex>n^m</tex>. Программа-полуразрешитель <tex>p</tex> устроена следующим образом: for <tex>m = 1 . При совпадении задача будет решена. \infty</tex> for all <tex>(i_1, иначе - программа зависнетi_2, \ldots, i_m): 1 \leq i_j \leq n</tex> if <tex>a_{i_1} \ldots a_{i_m} = b_{i_1} \ldots b_{i_m}</tex> return 1Таким образом, язык пар указанных последовательностей полуразрешим, а значит, перечислим.}}

Докажем неразрешимость: Сначала приведём доказательства для случаяДля МПСП доказательство перечислимости имеющих положительное решение пар аналогично, когда но перебор индексов ведётся с <tex>i_1 = 1i_2</tex>, т.е. для '''МПСП'''.