Изменения

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

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

Полуразрешимость: возможно взять по возрастанию все возможные наборы индексовТаким образом, применить конкатенацию и сравнить полученные строки. При совпадении задача будет решенаязык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, иначе - программа зависнетперечислим.}}

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

Назовём '''Модифицированной проблемой соответствий Поста (МПСП)снимком состояния [[Машина Тьюринга|МТ]]''' называется вопрос существования последовательности индексов строку вида <tex>( 1 , i_1, c_1 c_2 \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} dots c_k \ldots a_#_p c_{i_k} = b_1 b_{i_1} \ldots b_{i_kk+1}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))dots c_t</tex>, где <tex>a_i c_1 c_2 \in \Sigma ^*dots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>b_i \in \Sigma ^*p</tex> — текущее состояние автомата МТ, головка расположена справа от <tex>\forall i#_p</tex>.

СчитаемПостроим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$ \$</tex>, где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами, а <tex>\$</tex> — символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что '''Машина Тьюринга''' (отвергающего состояния <tex>MTno</tex>) никогда в автомате МТ не приходит существует, а допуск происходит при попадании в состояние <tex>yes</tex>. Сформируем списки <tex>A</tex> и <tex>B</tex> по МТ <tex>M</tex> и входной строке <tex>w</tex>. Будем добавлять пары цепочек в эти списки по следующим правилам: :1. <tex>a_1 = \$ \#_{start} w \$ </tex>, <tex>b_1 = \$</tex>. По определению МПСП эта пара всегда будет первой в любом решении.:2. <tex>Na_i = c</tex> - недопуск, <tex>b_i = c</tex> для всех символов <tex>c</tex> алфавита ленты.:3. <tex>MTa_i = \$</tex>, <tex>b_i = \$</tex>.: 4. <tex>a_i = \#_q e d</tex>, <tex>b_i = e \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (mp, c) = \langle q, d, \leftarrow \rangle</tex> и для всех символов алфавита <tex>e</tex>.:5. <tex>a_i = d \#_q</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\omegadelta (p, c)= \langle q, d, \rightarrow \rangle</tex>. Задача :6. <tex>ma_i = \#_q d</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (\omegap, c) = Y\langle q, d, \downarrow \rangle</tex>. Заметим, что все элементы <tex>A</tex> и <tex>B</tex>, кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов <tex>A</tex>, всегда оказывается длиннее. Если представить процесс формирования решения МПСП как динамический, то строка из элементов <tex>B</tex> вынуждена постоянно "догонять" первую. Более того, можно заметить, что вторая строка всегда будет отставать ровно на один снимок. Действительно, первая пара из списков <tex>A</tex> не разрешимаи <tex>B</tex> задает это отставание. Затем при помощи элементов из правил <tex>4</tex>, <tex>5</tex> и <tex>6</tex> мы имитируем переход машины Тьюринга, добавляя во вторую строку то состояние и положение головки, которые были до перехода, а в первую строку - то состояние, положение головки и новый ленточный символ, которые стали после перехода. ПредположимНетрудно заметить, что тем самым строка составленная из элементов списка <tex>B</tex> будет соответствовать строке из элементов списка <tex>A</tex>, но с отставанием на один переход. Далее с помощью элементов из правил <tex>2</tex> и <tex>3</tex> мы умеем решать '''МПСП'допишем в обе строки одинаковые суффиксы текущего снимка, разделитель <tex>\$</tex> и префикс нового снимка до следующего перехода машины Тьюринга. Таким образом если первая строка равна  <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$</tex>, то вторая будет равна <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$</tex>, а через несколько шагов они изменятся на <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n+1} \$</tex> и <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$ snap_n \$</tex>, соответственно. Теперь стоит новая задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности элементы по следующим правилам: :7. <tex>a_i = \#_{yes}</tex>, <tex>b_i = \#_{yes} c</tex>, для всех символов <tex>c</tex> алфавита ленты.:8. <tex>a_i = \#_{yes}</tex>, <tex>b_i = c \#_{yes}</tex>, для всех символов <tex>c</tex> алфавита ленты.:9. <tex>a_i = \$'</tex>, <tex>b_i = \#_{yes} \$ \$'</tex>.  Если состояние <tex>yes</tex> недостижимо, в первой строке никогда не будет символа <tex>\#_{yes}</tex>, и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину. Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил <tex>7</tex> и <tex>8</tex> и копируя все остальные с помощью элементов из правил <tex>2</tex> и <tex>3</tex> можно будет привести строки к виду  <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$</tex> и <tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ </tex>. И наконец, с помощью элементов из правила <tex>9</tex> сравняем строки. === Пример ===

Пусть автомат МТ состоит из двух состояний <tex>a_1 = \$ \#_s \omega \$start</tex>, и <tex>b_1 = \$yes</tex>.Таким образом выводятся следующие последовательности: , алфавит ленты содержит символы <tex>\$ A_0 \$ \ldots \$ A_k \$a</tex> и <tex>\$ A_i \ldotsb</tex> - мгновенное описание.Переходы автомата устроены следующим образом:

Если <tex>MT\delta (start, a) = \langle start, b, \rightarrow \rangle</tex> остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.;

<tex>\forall c \in \Pi</tex> построим следующую пару <tex>delta (a_i=cstart, b_i = cb), (a_i = \$langle yes, b = , \downarrow \$)</tex>.<tex>b</tex> должно сойтись с соответствующей <tex>arangle</tex> в предыдущем мгновенном описании.;

Соответственно из <tex>a_i = d \#_pyes</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.Аналогично следует поступить и с переходом на месте, или считаем, что такого не бываетпереходов нет.

Как может быть устроен префикс решения '''МПСП'''Списки <tex>A</tex> и <tex>B</tex> для строки <tex>ab</tex> будут сформированы следующим образом:

{|class="wikitable" style="text-align: center" |- ! Номер элемента ! <tex>A</tex> ! <tex>B</tex> |- |1 |<tex>\$ \#_{start} ab \$</tex> |<tex>\$</tex> |- |2 |<tex>a</tex> |<tex>a</tex>: |- |3 |<tex>b</tex> |<tex>b</tex> |- |4 |<tex>\$</tex> | <tex>\$ </tex> |- |5 | <tex>b \#_s _{start}</tex> |<tex>\omega_1 #_{start} a</tex> |- |6 |<tex>\$ #_{yes} b</tex> |<tex>\#_{start} b</tex> |- |7 |<tex>\#_{yes}</tex> |<tex>a \#_{yes}</tex> |- |8 |<tex>\#_{yes}</tex> |<tex>b \#_{yes}</tex> |- |9 | d <tex>\#_p _{yes}</tex> | w_2 <tex>\ldots #_{yes} a</tex> |- |10 | <tex>\#_{yes}</tex> |<tex>\#_{yes} b</tex> |- |11 |<tex>\$ '</tex> | <tex>\#_y _{yes} \$ | \$ |'</tex> |}

<tex>b</tex>Решение МПСП будет иметь следующий вид: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex>

Требуется добиться остановки. Для этого добавляется далее:{|class="wikitable" |- ! Шаг ! Индекс элемента ! Первая строка ! Вторая строка |- |align="center" | 1 |align="center" | 1 |<tex>\$ \#_{start} ab \$</tex> |<tex>\$</tex> |- |align="center" | 2 |align="center" | 5 |<tex>\$ \#_{start} ab \$ b \#_{start}</tex>* |<tex>\$ \#_{start} a </tex> |- |align="center" | 3 |align="center" | 3 |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex> |<tex>\$ \#_{start} ab</tex> |- |align="center" | 4 |align="center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$</tex> |<tex>\$ \#_{start} ab \$</tex> |- |align="center" | 5 |align="center" | 3 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b</tex> |<tex>\$ \#_{start} ab \$ b</tex> |- |align="center" | 6 |align="center" | 6 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex> |- |align="center" | 7 |align="center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b \$</tex> |- |align= "center" | 8 |align="center" | 8 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_y_{yes}</tex>, |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex> |- |align= "center" | 9 |align="center" | 3 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_y c_{yes} b</tex>* или |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>a |- |align="center" | 10 |align= "center" | 4 |<tex>\$ \#_{start} ab \$ b \#_y_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex>, |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex> |- |align= c "center" | 11 |align="center" | 10 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_y_{yes} b \$ \#_{yes} b \$ \#_{yes}</tex>* или |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b</tex>a |- |align="center" | 12 |align= "center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$</tex>, |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex> |- |align= "center" | 13 |align="center" | 11 |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex> |<tex>\$ \#_{start} ab \$ b \#_y _{start} b \$ b \#_{yes} b \$\#_{yes} b \$ \#_{yes} \$ \$'</tex> |}

Теперь остаётся избавиться от требования фиксированного первого индекса{{Лемма|statement=Универсальный язык сводится к МПСП.|proof=Из определения [[M-сводимость|m-сведения]] следует, т.ечто мы должны доказать, что машина Тьюринга <tex>M</tex> допускает <tex>w</tex> тогда и только тогда, когда построенный экземпляр МПСП имеет решение. перейти от '''МПСП''' к '''ПСП''':

'''Известно''':* Существует решение '''МПСП''' <tex>\Rightarrow</tex> существует решение '''ПСП'''* Не существует решения '''МПСП''' <tex>\Leftarrow</tex>не существует решения '''ПСП''''''Необходимо''':* Не существует решения '''МПСП''' <tex>\Rightarrow</tex> не существует решения '''ПСП'''

Возьмём экземпляр задачи МПСП: Если <tex>w</tex> допускается <tex>M</tex>(( a_1 , \ldots то можно проимитировать работу <tex>M</tex> со входом <tex>w</tex> и, a_n ) как показано в примере выше, ( b_1 , \ldots , b_n ))получить равные строки из элементов списков <tex>A</tex>. Вставим между каждой парой символов во всех строках символ и <tex>*B</tex>. То есть найти решение МПСП.

<tex>i = 1</tex>* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex>* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex><tex>i = 2 \ldots n </tex>:* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex>* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex><tex>i = n + 1</tex>* <tex>a_{n+1} = \$</tex>* <tex>b_{n+1} = *\$Leftarrow</tex>

Теперь необходимо начать Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, и, как было сказано выше, если в первой строке никогда не будет символа <tex>(a_1, b_1)\#_{yes}</tex>, тто "сравнять" строки по длине не удастся.кЗначит, если МПСП имеет решение, то символ <tex>\#_{yes}</tex> рано или поздно появится. все остальные пары начинаются с различных символовА значит и машина Тьюринга допустит <tex>w</tex>.

{{Теорема|statement=ПСП не разрешима.|proof=Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.}} == См. также ==* [[Неразрешимость исчисления предикатов первого порядка]]* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* [[Неразрешимость задачи об эквивалентности КС-грамматик]]* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]] == Литература Источники информации ==* Джон ХопкрофтД., Раджив МотваниР., Джеффри УльманД. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0* [http://en.wikipedia.org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]