Примеры неразрешимых задач: проблема соответствий Поста — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 47 промежуточных версий 9 участников)
Строка 1: Строка 1:
 +
'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.
 
{{Определение
 
{{Определение
 
|definition=
 
|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>A = (a_1, \dots, a_n)</tex> и <tex>B = (b_1 ,\dots ,b_n)</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>(i_1 , \dots, i_k)</tex>, удовлетворяющей условию <tex>a_{i_1} \dots a_{i_k} = b_{i_1} \dots b_{i_k}</tex>, где <tex>1 \leqslant i_j \leqslant n</tex> для всех <tex>j</tex>, называется '''проблемой соответствий Поста (ПСП)'''. Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.
 
}}
 
}}
 +
 +
== Примеры решений проблем соответствия Поста ==
 +
 +
=== Пример 1 ===
 +
{|class="wikitable" style="text-align: center"
 +
|-
 +
!Номер элемента
 +
!<tex>1</tex>
 +
!<tex>2</tex>
 +
!<tex>3</tex>
 +
|-
 +
!<tex>A</tex>
 +
|<tex>01</tex>
 +
|<tex>1</tex>
 +
|<tex>011</tex>
 +
|-
 +
!<tex>B</tex>
 +
|<tex>101</tex>
 +
|<tex>11</tex>
 +
|<tex>01</tex>
 +
|}
 +
Решение этой проблемы соответствий Поста будет являться последовательность индексов <tex>(3, 1, 3, 2)</tex>.
 +
Проверим это.
 +
 +
<tex>sA = 011, 01, 011, 1</tex>
 +
 +
<tex>sB = 01, 101, 01, 11</tex>
 +
 +
Получаем то, что строки <tex>sA</tex> и <tex>sB</tex> равны, а значит последовательность индексов <tex>(3, 1, 3, 2)</tex> является решением этой проблемы соотвествий Поста.
 +
 +
=== Пример 2 ===
 +
Иногда возникает ситуация, когда решений конкретной проблемы соответствия Поста нет.
 +
{|class="wikitable" style="text-align: center"
 +
|-
 +
!Номер элемента
 +
!<tex>1</tex>
 +
!<tex>2</tex>
 +
!<tex>3</tex>
 +
|-
 +
!<tex>A</tex>
 +
|<tex>01</tex>
 +
|<tex>101</tex>
 +
|<tex>011</tex>
 +
|-
 +
!<tex>B</tex>
 +
|<tex>0</tex>
 +
|<tex>10</tex>
 +
|<tex>111</tex>
 +
|}
 +
 +
Заметим, что если бы решение существовало оно должно было начинаться с индекса <tex>1</tex> или <tex>2</tex>.
 +
Но тогда строки получаемые из <tex>A</tex> всегда будут строго больше по длине, чем строки полученные из <tex>B</tex>, так как <tex> \mathrm{length}(A[i]) \geqslant \mathrm{length}(B[i])</tex> для всех <tex>i</tex>.
 +
 +
Решения не существует.
 +
 +
== Перечислимость языка ПСП ==
 +
 +
{{Теорема
 +
|statement=
 +
Язык пар последовательностей, для которых существует решение ПСП, [[Перечислимые языки | перечислим]].
 +
|proof=
 +
Для списков <tex>A</tex> и <tex>B</tex> размера <tex>n</tex> из условия ПСП построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
 +
  '''for''' <tex>m = 1 \dots \infty</tex>
 +
    '''foreach''' <tex>(i_1, i_2, \dots, i_m): 1 \leqslant i_j \leqslant n</tex>
 +
      '''if''' <tex>a_{i_1} \dots a_{i_m} = b_{i_1} \dots b_{i_m}</tex>
 +
        '''return''' ''true''
 +
 +
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
 +
}}
 +
 +
== Неразрешимость языка ПСП ==
  
 
{{Определение
 
{{Определение
Строка 9: Строка 81:
 
}}
 
}}
  
{{Утверждение
+
Докажем [[Разрешимые (рекурсивные) языки|неразрешимость]] языка ПСП следующим образом. Докажем, что универсальный язык [[M-сводимость|сводится]] к языку МПСП, который в свою очередь сводится к языку ПСП. При этом отметим, что для унарного алфавита ПСП разрешима.
 +
 
 +
=== Cведение МПСП к ПСП ===
 +
 
 +
Пусть даны списки <tex>A</tex> и <tex>B</tex> из условия МПСП. Построим два новых списка <tex>C</tex> и <tex>D</tex> и рассмотрим ПСП для них. Для этого введем два новых символа, которые не используются в словах из цепочек <tex>A</tex> и <tex>B</tex>. Пусть для определенности это будут символы <tex>\#</tex> и <tex>\$</tex>.
 +
 
 +
Тогда сформируем два новых списка <tex>C, D</tex> по следующим правилам:
 +
* для всех <tex>i = 1 \dots n</tex> возьмем <tex>c_i</tex> равное слову <tex>a_i</tex> с символом <tex>\#</tex> после каждого его символа. Например, для <tex>a_i = 10zx</tex> положим <tex>c_i = 1\#0\#z\#x\#</tex>,
 +
* для всех <tex>i = 1 \dots n</tex> возьмем <tex>d_i</tex> равное слову <tex>b_i</tex> с символом <tex>\#</tex> перед каждым его символом. Например, для <tex>b_i = 10zx</tex> положим <tex>d_i = \#1\#0\#z\#x</tex>,
 +
* <tex>c_0 = \#c_1</tex>,
 +
* <tex>d_0 = d_1</tex>,
 +
* <tex>c_{n+1} = \$</tex>,
 +
* <tex>d_{n+1} = \#\$</tex>.
 +
 
 +
 
 +
{{Лемма
 +
|id=lemma-
 
|statement=
 
|statement=
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
+
МПСП для пары списков <tex>(A, B)</tex> сводится к ПСП для пары списков <tex>(C, D)</tex>.
 
|proof=
 
|proof=
Пусть даны последовательности <tex>a</tex> и <tex>b</tex> размера <tex>n</tex> из условия ПСП. Построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
+
Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП.
  for <tex>m = 1 .. \infty</tex>
+
 
    for all <tex>(i_1, i_2, \ldots, i_m): 1 \leq i_j \leq n</tex>
+
<tex>\Rightarrow</tex>
      if <tex>a_{i_1} \ldots a_{i_m} = b_{i_1} \ldots b_{i_m}</tex>
+
 
        return true
+
Пусть набор индексов <tex>(1, i_2, \dots, i_k)</tex> — решение МПСП из условия леммы. То есть <tex>w_A = w_B</tex>, где
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
+
 
}}
+
<tex>w_A = a_1 a_{i_2} \dots a_{i_k}</tex>,
 +
 
 +
<tex>w_B = b_1 b_{i_2} \dots b_{i_k}</tex>.
 +
 
 +
Рассмотрев цепочки <tex>w_C</tex> и <tex>w_D</tex> c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа <tex>\#</tex> в начале, а второй — в конце. Конкретно,
 +
 
 +
<tex>\# c_1 c_{i_2} \dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \# </tex>.
 +
 
 +
Изменив первый индекс с <tex>1</tex> на <tex>0</tex>, решим проблему с символом <tex>\#</tex> в начале. Добавив индекс <tex>n+1</tex> к набору, решим проблему с символом <tex>\#</tex> в конце.
 +
 
 +
<tex> c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1} </tex>.
 +
 
 +
Итого, если <tex>(1, i_2, \dots, i_k)</tex> — решение исходной МПСП, то <tex>(0, i_2, \dots, i_k, n+1)</tex> — решение построенной по правилам выше ПСП.
 +
 
 +
<tex>\Leftarrow</tex>
 +
 
 +
В любом существующем решении ПСП для списков <tex>C, D</tex> должны выполняться условия:  
 +
* <tex>i_1 = 0</tex>, так как только в паре <tex>(c_1, d_1)</tex> первые символы совпадают,
 +
* последний индекс равен <tex>n+1</tex>, так как только в паре <tex>(c_{n+1}, d_{n+1})</tex> строки заканчиваются одинаковыми символами.
 +
 
 +
Пусть последовательность <tex>(0, i_2, i_3, \dots, i_k, n + 1)</tex> является решением ПСП. Иными словами,
 +
 
 +
<tex>c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1}</tex>.
 +
 
 +
Если <tex>i_f</tex> — наименьший индекс, равный <tex>n+1</tex>, то <tex>c_0 c_{i_2} \dots c_{i_f}</tex>, <tex>d_0 d_{i_2} \dots d_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\$</tex>, следовательно, равны между собой. Последовательность <tex>(0, i_{2} \dots, i_f)</tex> — также решение ПСП, причём первый индекс равен <tex>0</tex> и <tex>i_f = n + 1</tex>. Остальные индексы не превосходят <tex>n</tex>, но и не равны <tex>0</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\#</tex> подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:
  
Для МПСП доказательство перечислимости имеющих решение пар аналогично, но перебор индексов ведётся с <tex>i_2</tex>.
+
<tex>\# c_1 c_{i_2} \dots c_{i_{f-1}}\$</tex> <tex>=</tex> <tex>d_1 d_{i_2} \dots d_{i_{f-1}} \#\$</tex>.
  
{{Теорема
+
Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>\$</tex>, получим
|statement=
 
МПСП неразрешима.
 
|proof=
 
Выполним [[M-сводимость|m-сведение]] множества пар из машины Тьюринга (МТ) <tex>M</tex> и строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП.
 
  
Назовём '''снимком''' состояния МТ строку вида <tex>c_1 c_2 \ldots c_k \#_p c_{k+1} \ldots c_t</tex>, где <tex>c_1 c_2 \ldots c_t</tex> — строка на ленте без учёта пробелов, <tex>p</tex> — текущее состояние автомата МТ, <tex>\#_p</tex> соответствует положению головки. Построим последовательности таким образом, чтобы решение МПСП образовывало строку
+
<tex>a_1 a_{i_2} \dots a_{i_{f-1}} = b_1 b_{i_2} \dots b_{i_{f-1}}</tex>.
  
<tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$</tex>,
+
Итого, если <tex>(0, i_2, \dots, i_k, n+1)</tex> — решение ПСП, то <tex>(1, i_2, \dots, i_k)</tex> — решение исходной МПСП.
 +
}}
  
где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами строки. Оговоримся, что состояния <tex>no</tex> в автомате МТ не существует (его роль может выполнять сток), допуск происходит при попадании в состояние <tex>yes</tex>.
 
  
Сформируем последовательности <tex>a</tex> и <tex>b</tex> по МТ <tex>M</tex> и строке <tex>w</tex>.
 
  
<tex>a_1 = \$ \#_{start} w \$ </tex>, <tex>b_1 = \$</tex>;
+
=== Сведение универсального языка к МПСП ===
 +
{{Определение
 +
|definition=
 +
Назовём '''снимком состояния [[Машина Тьюринга|МТ]]''' строку вида <tex>c_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t</tex>, где <tex>c_1 c_2 \dots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>p</tex> — текущее состояние автомата МТ, головка расположена справа от <tex>\#_p</tex>.
 +
}}
 +
Построим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку
  
для всех символов <tex>c</tex> алфавита ленты (за исключением пробела):
+
<tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$ \$</tex>,
  
<tex>a_i = c</tex>, <tex>b_i = c</tex>,
+
где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_{n_{-t}}</tex> — последний снимок с <tex>t</tex> удалёнными символами, а <tex>\$</tex> — символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния <tex>no</tex> в автомате МТ не существует, а допуск происходит при попадании в состояние <tex>yes</tex>.
  
а также
+
Сформируем списки <tex>A</tex> и <tex>B</tex> по МТ <tex>M</tex> и входной строке <tex>w</tex>. Будем добавлять пары цепочек в эти списки по следующим правилам:
  
<tex>a_i = \$</tex>, <tex>b_i = \$</tex>;
+
:1. <tex>a_1 = \$ \#_{start} w \$ </tex>, <tex>b_1 = \$</tex>. По определению МПСП эта пара всегда будет первой в любом решении.
 +
:2. <tex>a_i = c</tex>, <tex>b_i = c</tex> для всех символов <tex>c</tex> алфавита ленты.
 +
:3. <tex>a_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 (p, 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>\delta (p, c) = \langle q, d, \rightarrow \rangle</tex>.
 +
:6. <tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex> для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \downarrow \rangle</tex>.
  
для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \leftarrow \rangle</tex> и для всех символов алфавита <tex>e</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>a_i = \#_q e d</tex>, <tex>b_i = e \#_p c</tex>;
+
<tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$</tex>,
  
для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \rightarrow \rangle</tex>:
+
то вторая будет равна
  
<tex>a_i = d \#_q</tex>, <tex>b_i = \#_p c</tex>;
+
<tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$</tex>,
  
для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \downarrow \rangle</tex>:
+
а через несколько шагов они изменятся на
  
<tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex>.
+
<tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n+1} \$</tex>
  
Такие последовательности позволяют сформировать строки <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex> (из <tex>a</tex>) и <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex> (из <tex>b</tex>) и только их, но решения МПСП быть не может, так как все члены последовательностей, кроме первого, имеют равную длину, и строка, составленная из элементов <tex>a</tex>, всегда оказывается длиннее.
+
и
  
Задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности следующие элементы:
+
<tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$ snap_n \$</tex>,
  
для всех символов <tex>c</tex> алфавита ленты (за исключением пробела):
+
соответственно.
  
<tex>a_i = \#_{yes}</tex>, <tex>b_i = \#_{yes} c</tex>,
+
Теперь стоит новая задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности элементы по следующим правилам:
  
<tex>a_i = \#_{yes}</tex>, <tex>b_i = c \#_{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>a_i = \$</tex>, <tex>b_i = \#_{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 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots \$ \#_{yes} \$ \$</tex>,
+
и
  
но только тогда, когда в <tex>snap_n</tex> содержится <tex>\#_{yes}</tex>; другими словами, только тогда, когда автомат, принадлежащий <tex>M</tex>, допускает <tex>w</tex>. Таким образом, выполнено успешное m-сведение множества пар из машины Тьюринга (МТ) <tex>M</tex> и строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП.
+
<tex>\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ </tex>.
  
}}
+
И наконец, с помощью элементов из правила <tex>9</tex> сравняем строки.
  
 
=== Пример ===
 
=== Пример ===
Строка 91: Строка 210:
 
из <tex>yes</tex> переходов нет.
 
из <tex>yes</tex> переходов нет.
  
Последовательности при строке <tex>ab</tex> будут сформированы следующим образом:
+
Списки <tex>A</tex> и <tex>B</tex> для строки <tex>ab</tex> будут сформированы следующим образом:
  
{| border="1"
+
{|class="wikitable" style="text-align: center"
|Номер элемента
 
|width="60"|1
 
|width="60"|2
 
|width="60"|3
 
|width="60"|4
 
|width="60"|5
 
|width="60"|6
 
|width="60"|7
 
|width="60"|8
 
|width="60"|9
 
|width="60"|10
 
|width="60"|11
 
 
  |-
 
  |-
  |Последовательность a
+
! Номер элемента
 +
! <tex>A</tex>
 +
! <tex>B</tex>
 +
  |-
 +
|1
 
  |<tex>\$ \#_{start} ab \$</tex>
 
  |<tex>\$ \#_{start} ab \$</tex>
 +
|<tex>\$</tex>
 +
|-
 +
|2
 +
|<tex>a</tex>
 
  |<tex>a</tex>
 
  |<tex>a</tex>
 +
|-
 +
|3
 
  |<tex>b</tex>
 
  |<tex>b</tex>
 +
|<tex>b</tex>
 +
|-
 +
|4
 
  |<tex>\$</tex>
 
  |<tex>\$</tex>
|<tex>b \#_{start}</tex>
 
|<tex>\#_{yes} b</tex>
 
|<tex>\#_{yes}</tex>
 
|<tex>\#_{yes}</tex>
 
|<tex>\#_{yes}</tex>
 
|<tex>\#_{yes}</tex>
 
 
  |<tex>\$</tex>
 
  |<tex>\$</tex>
 
  |-
 
  |-
  |Последовательность b
+
  |5
|<tex>\$</tex>
+
  |<tex>b \#_{start}</tex>
|<tex>a</tex>
 
  |<tex>b</tex>
 
|<tex>\$</tex>
 
 
  |<tex>\#_{start} a</tex>
 
  |<tex>\#_{start} a</tex>
 +
|-
 +
|6
 +
|<tex>\#_{yes} b</tex>
 
  |<tex>\#_{start} b</tex>
 
  |<tex>\#_{start} b</tex>
 +
|-
 +
|7
 +
|<tex>\#_{yes}</tex>
 
  |<tex>a \#_{yes}</tex>
 
  |<tex>a \#_{yes}</tex>
 +
|-
 +
|8
 +
|<tex>\#_{yes}</tex>
 
  |<tex>b \#_{yes}</tex>
 
  |<tex>b \#_{yes}</tex>
 +
|-
 +
|9
 +
|<tex>\#_{yes}</tex>
 
  |<tex>\#_{yes} a</tex>
 
  |<tex>\#_{yes} a</tex>
 +
|-
 +
|10
 +
|<tex>\#_{yes}</tex>
 
  |<tex>\#_{yes} b</tex>
 
  |<tex>\#_{yes} b</tex>
  |<tex>\#_{yes} \$ \$</tex>
+
|-
 +
|11
 +
|<tex>\$'</tex>
 +
  |<tex>\#_{yes} \$ \$'</tex>
 
  |}
 
  |}
  
 
Решение МПСП будет иметь следующий вид:
 
Решение МПСП будет иметь следующий вид:
  
{| border="1"
+
{|class="wikitable"
  |Шаг
+
  |-
  |Индекс элемента
+
! Шаг
  |Первая строка
+
  ! Индекс элемента
  |Вторая строка
+
  ! Первая строка
 +
  ! Вторая строка
 
  |-
 
  |-
  |1
+
  |align="center" | 1
  |1
+
  |align="center" | 1
 
  |<tex>\$ \#_{start} ab \$</tex>
 
  |<tex>\$ \#_{start} ab \$</tex>
 
  |<tex>\$</tex>
 
  |<tex>\$</tex>
 
  |-
 
  |-
  |2
+
  |align="center" | 2
  |5
+
  |align="center" | 5
 
  |<tex>\$ \#_{start} ab \$ b \#_{start}</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start}</tex>
 
  |<tex>\$ \#_{start} a</tex>
 
  |<tex>\$ \#_{start} a</tex>
 
  |-
 
  |-
  |3
+
  |align="center" | 3
  |3
+
  |align="center" | 3
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
 
  |<tex>\$ \#_{start} ab</tex>
 
  |<tex>\$ \#_{start} ab</tex>
 
  |-
 
  |-
  |4
+
  |align="center" | 4
  |4
+
  |align="center" | 4
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$</tex>
 
  |<tex>\$ \#_{start} ab \$</tex>
 
  |<tex>\$ \#_{start} ab \$</tex>
 
  |-
 
  |-
  |5
+
  |align="center" | 5
  |3
+
  |align="center" | 3
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b</tex>
 
  |<tex>\$ \#_{start} ab \$ b</tex>
 
  |<tex>\$ \#_{start} ab \$ b</tex>
 
  |-
 
  |-
  |6
+
  |align="center" | 6
  |6
+
  |align="center" | 6
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
 
  |-
 
  |-
  |7
+
  |align="center" | 7
  |4
+
  |align="center" | 4
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$</tex>
 
  |-
 
  |-
  |8
+
  |align="center" | 8
  |8
+
  |align="center" | 8
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex>
 
  |-
 
  |-
  |9
+
  |align="center" | 9
  |3
+
  |align="center" | 3
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>
 
  |-
 
  |-
  |10
+
  |align="center" | 10
  |4
+
  |align="center" | 4
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>
 
  |-
 
  |-
  |11
+
  |align="center" | 11
  |10
+
  |align="center" | 10
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}</tex>
 
  |<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>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b</tex>
 
  |-
 
  |-
  |12
+
  |align="center" | 12
  |4
+
  |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 \$ \#_{yes} \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex>
 
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex>
 
  |-
 
  |-
  |13
+
  |align="center" | 13
  |11
+
  |align="center" | 11
  |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$</tex>
+
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$</tex>
+
  |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>
 
  |}
 
  |}
  
 
+
{{Лемма
{{Теорема
 
 
|statement=
 
|statement=
ПСП неразрешима.
+
Универсальный язык сводится к МПСП.
 
|proof=
 
|proof=
Выполним [[M-сводимость|m-сведение]] множества решений МПСП к множеству решений ПСП.
+
Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать, что машина Тьюринга <tex>M</tex> допускает <tex>w</tex> тогда и только тогда, когда построенный экземпляр МПСП имеет решение.
 
 
Пусть даны последовательности <tex>a, b</tex> из условия МПСП. Обозначим как <tex>left(w, c)</tex> и <tex>right(w, c)</tex> строки, состоящие из символов <tex>w</tex>, разделённых <tex>c</tex>: <tex>left(w, c) = c w_1 c w_2 \ldots c w_k</tex>, <tex>right(w, c) = w_1 c w_2 c \dots w_k c</tex>.
 
 
 
Построим две новые последовательности <tex>a', b'</tex>:
 
* <tex>a'_1 = \$ right(a_1, \$)</tex>, <tex>b'_1 = left(b_1, \$)</tex>;
 
* <tex>\forall i = 1 .. n</tex>: <tex>a'_{i+1} = right(a_i, \$)</tex>, <tex>b'_{i+1} = left(b_i, \$)</tex>;
 
* <tex>a'_{n+2} = \#</tex>, <tex>b'_{n+2} = \$ \#</tex>,
 
где <tex>\$</tex>, <tex>\#</tex> — символы, не встречающиеся в словах исходных последовательностей.
 
  
{{Утверждение
 
|statement=
 
Существование решения МПСП для <tex>a, b</tex> эквивалентно существованию решения ПСП для <tex>a', b'</tex>.
 
|proof=
 
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Пусть
+
Если <tex>w</tex> допускается <tex>M</tex>, то можно проимитировать работу <tex>M</tex> со входом <tex>w</tex> и, как показано в примере выше, получить равные строки из элементов списков <tex>A</tex> и <tex>B</tex>. То есть найти решение МПСП.
 
 
<tex>w_a = a_1 a_{i_2} \ldots a_{i_k}</tex>,
 
 
 
<tex>w_b = b_1 b_{i_2} \ldots b_{i_k}</tex>,
 
 
 
<tex>w_a = w_b</tex>. Рассмотрим
 
 
 
<tex>w'_a = a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = \$ right(a_1, \$) right(a_{i_2}, \$) \ldots right(a_{i_k}, \$) \#</tex>,
 
 
 
<tex>w'_b = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2} = left(b_1, \$) left(b_{i_2}, \$) \ldots left(b_{i_k}, \$) \$ \#</tex>.
 
 
 
На чётных позициях в <tex>w'_a</tex> и <tex>w'_b</tex> стоят равные символы из <tex>w_a</tex> и <tex>w_b</tex>, а также <tex>\#</tex> (в конце); на нечётных — <tex>\$</tex>. Следовательно, <tex>w'_a = w'_b</tex>, то есть
 
 
 
<tex>a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2}</tex>.
 
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
В любом существующем решении ПСП для <tex>a', b'</tex> должны выполняться условия:
+
Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, и, как было сказано выше, если в первой строке никогда не будет символа <tex>\#_{yes}</tex>, то "сравнять" строки по длине не удастся. Значит, если МПСП имеет решение, то символ <tex>\#_{yes}</tex> рано или поздно появится. А значит и машина Тьюринга допустит <tex>w</tex>.
* <tex>i_1 = 1</tex>, так как только в паре <tex>(a'_1, b'_1)</tex> первые символы совпадают;
 
* последний индекс равен <tex>n+2</tex>, так как только в паре <tex>(a'_{n+2}, b'_{n+2})</tex> строки заканчиваются одинаковыми символами.
 
  
Пусть
+
}}
  
<tex>a'_1 a'_{i_2} \ldots a'_{i_k} = b'_1 b'_{i_2} \ldots b'_{i_k}</tex>.
+
{{Теорема
 +
|statement=
 +
ПСП не разрешима.
 +
|proof=
 +
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.
 +
}}
  
Если <tex>i_f</tex> — наименьший индекс, равный <tex>n+2</tex>, то <tex>a'_1 a'_{i_2} \ldots a'_{i_f}</tex>, <tex>b'_1 b'_{i_2} \ldots b'_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\#</tex>, следовательно, равны между собой. <tex>i_1, \ldots, i_f</tex> — также решение ПСП, причём <tex>i_1 = 1</tex>, <tex>i_f = n + 2</tex>. Остальные индексы не превосходят <tex>n+1</tex>, но и не равны <tex>1</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\$</tex> подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:
+
== См. также ==
 +
* [[Неразрешимость исчисления предикатов первого порядка]]
 +
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
 +
* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]
 +
* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]
 +
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
 +
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
  
<tex>\$ right(a_1, \$) right(a_{i_2-1}, \$) \ldots right(a_{i_{f-1}-1}, \$) \#</tex> <tex>=</tex> <tex>left(b_1, \$) left(b_{i_2-1}, \$) \ldots left(b_{i_{f-1}-1}, \$) \$ \#</tex>.
+
== Источники информации ==
 
+
* Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0
Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>\#</tex>, получим
+
* [http://en.wikipedia.org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem]
 
 
<tex>a_1 a_{i_2-1} \ldots a_{i_{f-1}-1} = b_1 b_{i_2-1} \ldots b_{i_{f-1}-1}</tex>.
 
}}
 
 
 
По доказанному ранее, МПСП неразрешима. Тогда, вследствие теоремы для m-сведения, ПСП неразрешима.
 
}}
 
  
== Литература ==
+
[[Категория: Теория формальных языков]]
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
+
[[Категория: Теория вычислимости]]
 +
[[Категория: Примеры неразрешимых задач]]

Текущая версия на 19:41, 4 сентября 2022

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

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


Примеры решений проблем соответствия Поста

Пример 1

Номер элемента [math]1[/math] [math]2[/math] [math]3[/math]
[math]A[/math] [math]01[/math] [math]1[/math] [math]011[/math]
[math]B[/math] [math]101[/math] [math]11[/math] [math]01[/math]

Решение этой проблемы соответствий Поста будет являться последовательность индексов [math](3, 1, 3, 2)[/math]. Проверим это.

[math]sA = 011, 01, 011, 1[/math]

[math]sB = 01, 101, 01, 11[/math]

Получаем то, что строки [math]sA[/math] и [math]sB[/math] равны, а значит последовательность индексов [math](3, 1, 3, 2)[/math] является решением этой проблемы соотвествий Поста.

Пример 2

Иногда возникает ситуация, когда решений конкретной проблемы соответствия Поста нет.

Номер элемента [math]1[/math] [math]2[/math] [math]3[/math]
[math]A[/math] [math]01[/math] [math]101[/math] [math]011[/math]
[math]B[/math] [math]0[/math] [math]10[/math] [math]111[/math]

Заметим, что если бы решение существовало оно должно было начинаться с индекса [math]1[/math] или [math]2[/math]. Но тогда строки получаемые из [math]A[/math] всегда будут строго больше по длине, чем строки полученные из [math]B[/math], так как [math] \mathrm{length}(A[i]) \geqslant \mathrm{length}(B[i])[/math] для всех [math]i[/math].

Решения не существует.

Перечислимость языка ПСП

Теорема:
Язык пар последовательностей, для которых существует решение ПСП, перечислим.
Доказательство:
[math]\triangleright[/math]

Для списков [math]A[/math] и [math]B[/math] размера [math]n[/math] из условия ПСП построим программу-полуразрешитель [math]p[/math], проверяющую все возможные решения:

 for [math]m = 1 \dots \infty[/math]
   foreach [math](i_1, i_2, \dots, i_m): 1 \leqslant i_j \leqslant n[/math]
     if [math]a_{i_1} \dots a_{i_m} = b_{i_1} \dots b_{i_m}[/math]
       return true
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
[math]\triangleleft[/math]

Неразрешимость языка ПСП

Определение:
Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов [math]i_1 = 1[/math], называется модифицированной проблемой соответствий Поста (МПСП).


Докажем неразрешимость языка ПСП следующим образом. Докажем, что универсальный язык сводится к языку МПСП, который в свою очередь сводится к языку ПСП. При этом отметим, что для унарного алфавита ПСП разрешима.

Cведение МПСП к ПСП

Пусть даны списки [math]A[/math] и [math]B[/math] из условия МПСП. Построим два новых списка [math]C[/math] и [math]D[/math] и рассмотрим ПСП для них. Для этого введем два новых символа, которые не используются в словах из цепочек [math]A[/math] и [math]B[/math]. Пусть для определенности это будут символы [math]\#[/math] и [math]\$[/math].

Тогда сформируем два новых списка [math]C, D[/math] по следующим правилам:

  • для всех [math]i = 1 \dots n[/math] возьмем [math]c_i[/math] равное слову [math]a_i[/math] с символом [math]\#[/math] после каждого его символа. Например, для [math]a_i = 10zx[/math] положим [math]c_i = 1\#0\#z\#x\#[/math],
  • для всех [math]i = 1 \dots n[/math] возьмем [math]d_i[/math] равное слову [math]b_i[/math] с символом [math]\#[/math] перед каждым его символом. Например, для [math]b_i = 10zx[/math] положим [math]d_i = \#1\#0\#z\#x[/math],
  • [math]c_0 = \#c_1[/math],
  • [math]d_0 = d_1[/math],
  • [math]c_{n+1} = \$[/math],
  • [math]d_{n+1} = \#\$[/math].


Лемма:
МПСП для пары списков [math](A, B)[/math] сводится к ПСП для пары списков [math](C, D)[/math].
Доказательство:
[math]\triangleright[/math]

Из определения m-сведения следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП.

[math]\Rightarrow[/math]

Пусть набор индексов [math](1, i_2, \dots, i_k)[/math] — решение МПСП из условия леммы. То есть [math]w_A = w_B[/math], где

[math]w_A = a_1 a_{i_2} \dots a_{i_k}[/math],

[math]w_B = b_1 b_{i_2} \dots b_{i_k}[/math].

Рассмотрев цепочки [math]w_C[/math] и [math]w_D[/math] c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа [math]\#[/math] в начале, а второй — в конце. Конкретно,

[math]\# c_1 c_{i_2} \dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \# [/math].

Изменив первый индекс с [math]1[/math] на [math]0[/math], решим проблему с символом [math]\#[/math] в начале. Добавив индекс [math]n+1[/math] к набору, решим проблему с символом [math]\#[/math] в конце.

[math] c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1} [/math].

Итого, если [math](1, i_2, \dots, i_k)[/math] — решение исходной МПСП, то [math](0, i_2, \dots, i_k, n+1)[/math] — решение построенной по правилам выше ПСП.

[math]\Leftarrow[/math]

В любом существующем решении ПСП для списков [math]C, D[/math] должны выполняться условия:

  • [math]i_1 = 0[/math], так как только в паре [math](c_1, d_1)[/math] первые символы совпадают,
  • последний индекс равен [math]n+1[/math], так как только в паре [math](c_{n+1}, d_{n+1})[/math] строки заканчиваются одинаковыми символами.

Пусть последовательность [math](0, i_2, i_3, \dots, i_k, n + 1)[/math] является решением ПСП. Иными словами,

[math]c_0 c_{i_2} \dots c_{i_k} c_{n+1} = d_0 d_{i_2} \dots d_{i_k} d_{n+1}[/math].

Если [math]i_f[/math] — наименьший индекс, равный [math]n+1[/math], то [math]c_0 c_{i_2} \dots c_{i_f}[/math], [math]d_0 d_{i_2} \dots d_{i_f}[/math] — префиксы исходных конкатенаций до первого символа [math]\$[/math], следовательно, равны между собой. Последовательность [math](0, i_{2} \dots, i_f)[/math] — также решение ПСП, причём первый индекс равен [math]0[/math] и [math]i_f = n + 1[/math]. Остальные индексы не превосходят [math]n[/math], но и не равны [math]0[/math], иначе в левой части равенства образуется подстрока из двух [math]\#[/math] подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:

[math]\# c_1 c_{i_2} \dots c_{i_{f-1}}\$[/math] [math]=[/math] [math]d_1 d_{i_2} \dots d_{i_{f-1}} \#\$[/math].

Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца [math]\$[/math], получим

[math]a_1 a_{i_2} \dots a_{i_{f-1}} = b_1 b_{i_2} \dots b_{i_{f-1}}[/math].

Итого, если [math](0, i_2, \dots, i_k, n+1)[/math] — решение ПСП, то [math](1, i_2, \dots, i_k)[/math] — решение исходной МПСП.
[math]\triangleleft[/math]


Сведение универсального языка к МПСП

Определение:
Назовём снимком состояния МТ строку вида [math]c_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t[/math], где [math]c_1 c_2 \dots c_t[/math] — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, [math]p[/math] — текущее состояние автомата МТ, головка расположена справа от [math]\#_p[/math].

Построим списки [math]A[/math] и [math]B[/math] таким образом, чтобы решение МПСП образовывало строку

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$ \$[/math],

где [math]snap_i[/math] — снимки последовательных состояний МТ от стартового до конечного, [math]snap_{n_{-t}}[/math] — последний снимок с [math]t[/math] удалёнными символами, а [math]\$[/math] — символ, не принадлежащий алфавиту ленты и алфавиту входных слов. Оговоримся, что отвергающего состояния [math]no[/math] в автомате МТ не существует, а допуск происходит при попадании в состояние [math]yes[/math].

Сформируем списки [math]A[/math] и [math]B[/math] по МТ [math]M[/math] и входной строке [math]w[/math]. Будем добавлять пары цепочек в эти списки по следующим правилам:

1. [math]a_1 = \$ \#_{start} w \$ [/math], [math]b_1 = \$[/math]. По определению МПСП эта пара всегда будет первой в любом решении.
2. [math]a_i = c[/math], [math]b_i = c[/math] для всех символов [math]c[/math] алфавита ленты.
3. [math]a_i = \$[/math], [math]b_i = \$[/math].
4. [math]a_i = \#_q e d[/math], [math]b_i = e \#_p c[/math] для всех правил [math]M[/math] вида [math]\delta (p, c) = \langle q, d, \leftarrow \rangle[/math] и для всех символов алфавита [math]e[/math].
5. [math]a_i = d \#_q[/math], [math]b_i = \#_p c[/math] для всех правил [math]M[/math] вида [math]\delta (p, c) = \langle q, d, \rightarrow \rangle[/math].
6. [math]a_i = \#_q d[/math], [math]b_i = \#_p c[/math] для всех правил [math]M[/math] вида [math]\delta (p, c) = \langle q, d, \downarrow \rangle[/math].

Заметим, что все элементы [math]A[/math] и [math]B[/math], кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов [math]A[/math], всегда оказывается длиннее. Если представить процесс формирования решения МПСП как динамический, то строка из элементов [math]B[/math] вынуждена постоянно "догонять" первую. Более того, можно заметить, что вторая строка всегда будет отставать ровно на один снимок. Действительно, первая пара из списков [math]A[/math] и [math]B[/math] задает это отставание. Затем при помощи элементов из правил [math]4[/math], [math]5[/math] и [math]6[/math] мы имитируем переход машины Тьюринга, добавляя во вторую строку то состояние и положение головки, которые были до перехода, а в первую строку - то состояние, положение головки и новый ленточный символ, которые стали после перехода. Нетрудно заметить, что тем самым строка составленная из элементов списка [math]B[/math] будет соответствовать строке из элементов списка [math]A[/math], но с отставанием на один переход. Далее с помощью элементов из правил [math]2[/math] и [math]3[/math] мы допишем в обе строки одинаковые суффиксы текущего снимка, разделитель [math]\$[/math] и префикс нового снимка до следующего перехода машины Тьюринга. Таким образом если первая строка равна

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$[/math],

то вторая будет равна

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$[/math],

а через несколько шагов они изменятся на

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n+1} \$[/math]

и

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_{n-1} \$ snap_n \$[/math],

соответственно.

Теперь стоит новая задача — получить равные строки, если состояние [math]\#_{yes}[/math] достижимо. Для этого добавим в уже имеющиеся последовательности элементы по следующим правилам:

7. [math]a_i = \#_{yes}[/math], [math]b_i = \#_{yes} c[/math], для всех символов [math]c[/math] алфавита ленты.
8. [math]a_i = \#_{yes}[/math], [math]b_i = c \#_{yes}[/math], для всех символов [math]c[/math] алфавита ленты.
9. [math]a_i = \$'[/math], [math]b_i = \#_{yes} \$ \$'[/math].

Если состояние [math]yes[/math] недостижимо, в первой строке никогда не будет символа [math]\#_{yes}[/math], и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину.

Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил [math]7[/math] и [math]8[/math] и копируя все остальные с помощью элементов из правил [math]2[/math] и [math]3[/math] можно будет привести строки к виду

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ \#_{yes} \$[/math]

и

[math]\$ snap_1 \$ snap_2 \$ \dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \dots \$ [/math].

И наконец, с помощью элементов из правила [math]9[/math] сравняем строки.

Пример

Пусть автомат МТ состоит из двух состояний [math]start[/math] и [math]yes[/math], алфавит ленты содержит символы [math]a[/math] и [math]b[/math]. Переходы автомата устроены следующим образом:

[math]\delta (start, a) = \langle start, b, \rightarrow \rangle[/math];

[math]\delta (start, b) = \langle yes, b, \downarrow \rangle[/math];

из [math]yes[/math] переходов нет.

Списки [math]A[/math] и [math]B[/math] для строки [math]ab[/math] будут сформированы следующим образом:

Номер элемента [math]A[/math] [math]B[/math]
1 [math]\$ \#_{start} ab \$[/math] [math]\$[/math]
2 [math]a[/math] [math]a[/math]
3 [math]b[/math] [math]b[/math]
4 [math]\$[/math] [math]\$[/math]
5 [math]b \#_{start}[/math] [math]\#_{start} a[/math]
6 [math]\#_{yes} b[/math] [math]\#_{start} b[/math]
7 [math]\#_{yes}[/math] [math]a \#_{yes}[/math]
8 [math]\#_{yes}[/math] [math]b \#_{yes}[/math]
9 [math]\#_{yes}[/math] [math]\#_{yes} a[/math]
10 [math]\#_{yes}[/math] [math]\#_{yes} b[/math]
11 [math]\$'[/math] [math]\#_{yes} \$ \$'[/math]

Решение МПСП будет иметь следующий вид:

Шаг Индекс элемента Первая строка Вторая строка
1 1 [math]\$ \#_{start} ab \$[/math] [math]\$[/math]
2 5 [math]\$ \#_{start} ab \$ b \#_{start}[/math] [math]\$ \#_{start} a[/math]
3 3 [math]\$ \#_{start} ab \$ b \#_{start} b[/math] [math]\$ \#_{start} ab[/math]
4 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$[/math] [math]\$ \#_{start} ab \$[/math]
5 3 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b[/math] [math]\$ \#_{start} ab \$ b[/math]
6 6 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b[/math] [math]\$ \#_{start} ab \$ b \#_{start} b[/math]
7 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$[/math]
8 8 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}[/math]
9 3 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b[/math]
10 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$[/math]
11 10 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b[/math]
12 4 [math]\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$[/math]
13 11 [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'[/math] [math]\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'[/math]
Лемма:
Универсальный язык сводится к МПСП.
Доказательство:
[math]\triangleright[/math]

Из определения m-сведения следует, что мы должны доказать, что машина Тьюринга [math]M[/math] допускает [math]w[/math] тогда и только тогда, когда построенный экземпляр МПСП имеет решение.

[math]\Rightarrow[/math]

Если [math]w[/math] допускается [math]M[/math], то можно проимитировать работу [math]M[/math] со входом [math]w[/math] и, как показано в примере выше, получить равные строки из элементов списков [math]A[/math] и [math]B[/math]. То есть найти решение МПСП.

[math]\Leftarrow[/math]

Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, и, как было сказано выше, если в первой строке никогда не будет символа [math]\#_{yes}[/math], то "сравнять" строки по длине не удастся. Значит, если МПСП имеет решение, то символ [math]\#_{yes}[/math] рано или поздно появится. А значит и машина Тьюринга допустит [math]w[/math].
[math]\triangleleft[/math]
Теорема:
ПСП не разрешима.
Доказательство:
[math]\triangleright[/math]
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.
[math]\triangleleft[/math]

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0
  • Wikipedia — Post correspondence problem