1632
правки
Изменения
м
== Основные определения ==
Для МПСП доказательство перечислимости имеющих решение пар аналогично, но перебор индексов ведётся с <tex>i_2</tex>.== Неразрешимость языка ПСП ==
Для начала покажем как свести === Cведение МПСП к ПСП.===
Теперь покажем как свести универсальный язык === Сведение универсального языка к МПСП.===
rollbackEdits.php mass rollback
'''Проблема соответствий Поста''' (англ. ''Post correspondence problem'') — один из основных примеров неразрешимой задачи, использующийся для доказательства неразрешимости многих других задач.
{{Определение
|definition=
Даны два конечных списка <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> |definition=}Проблема Решение этой проблемы соответствий Постабудет являться последовательность индексов <tex>(3, для которой фиксирован элемент последовательности индексов 1, 3, 2)</tex>.Проверим это. <tex>i_1 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>. Решения не существует.
== Перечислимость языка ПСП ==
|proof=
Для списков <tex>A</tex> и <tex>B</tex> размера <tex>n</tex> из условия ПСП построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
'''for ''' <tex>m = 1 .. \dots \infty</tex> for all '''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''
Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.
}}
{{Определение|definition=Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов <tex>i_1 = Неразрешимость языка ПСП ==1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.}}
Докажем [[Разрешимые (рекурсивные) языки|неразрешимость ]] языка ПСП следующим образом. Докажем, что универсальный язык [[M-сводимость|сводится]] к языку МПСП, который в свою очередь сводится к языку ПСП. При этом отметим, что для унарного алфавита ПСП разрешима.
Пусть даны списки <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>.
В любом существующем решении ПСП для списков <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>a_1 a_{i_2} \dots a_{i_{f-1}} = b_1 b_{i_2} \dots b_{i_{f-1}}</tex>.
Итого, если <tex>(0, i_2, \dots, i_k, n+1)</tex> - — решение ПСП, то <tex>(1, i_2, \dots, i_k)</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>\$ 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>no</tex> в автомате МТ не существует, а допуск происходит при попадании в состояние <tex>yes</tex>.
Сформируем списки <tex>A</tex> и <tex>B</tex> по МТ <tex>M</tex> и входной строке <tex>w</tex>. Будем добавлять пары цепочек в эти списки по следующим правилам:
|-
! Номер элемента
! Список <tex>A</tex> ! Список <tex>B</tex>
|-
|1
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.
}}
== См. также ==
* [[Неразрешимость исчисления предикатов первого порядка]]
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]
* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
* [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
== Источники информации ==
* Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2008. — С. 528. — ISBN 5-8459-1347-0
* [http://en.wikipedia.org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem - Wikipedia] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]
