1632
правки
Изменения
м
Существует упорядоченная пара конечных последовательностей Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов <tex>i_1 = 1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.}} Докажем [[Разрешимые ( a_1 рекурсивные) языки|неразрешимость]] языка ПСП следующим образом. Докажем, \ldots что универсальный язык [[M-сводимость|сводится]] к языку МПСП, a_n ) который в свою очередь сводится к языку ПСП. При этом отметим, ( b_1 что для унарного алфавита ПСП разрешима. === Cведение МПСП к ПСП === Пусть даны списки <tex>A</tex> и <tex>B</tex> из условия МПСП. Построим два новых списка <tex>C</tex> и <tex>D</tex> и рассмотрим ПСП для них. Для этого введем два новых символа, которые не используются в словах из цепочек <tex>A</tex> и <tex>B</tex>. Пусть для определенности это будут символы <tex>\ldots #</tex> и <tex>\$</tex>. Тогда сформируем два новых списка <tex>C, b_n ))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\in #0\Sigma ^#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 = \in #c_1</tex>,* <tex>d_0 = d_1</tex>,* <tex>c_{n+1} = \Sigma ^$</tex>,*<tex>d_{n+1} = \#\$</tex>. {{Лемма|id=lemma-|statement=МПСП для пары списков <tex>(A, B)</tex> сводится к ПСП для всех пары списков <tex>i(C, D)</tex>. Вопрос существования непустой последовательности |proof=Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и ПСП. <tex>\Rightarrow</tex> Пусть набор индексов <tex>( i_1 1, i_2, \ldots dots, i_k )</tex> — решение МПСП из условия леммы. То есть <tex>w_A = w_B</tex>, удовлетворяющей условию где <tex>w_A = a_1 a_{i_1i_2} \ldots dots a_{i_k} </tex>, <tex>w_B = b_1 b_{i_1i_2} \ldots 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, \leq i_j dots, i_k)</tex> — решение исходной МПСП, то <tex>(0, i_2, \leq dots, i_k, n+1)</tex> — решение построенной по правилам выше ПСП. <tex>\Leftarrow</tex> В любом существующем решении ПСП для каждого jсписков <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>\# 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>, получим <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> — решение исходной МПСП.
Язык имеющих решение проблем соответствий поста перечислим, но не разрешимУниверсальный язык сводится к МПСП.(Не существует примера неразрешимого языка, который является языком программ)
Докажем неразрешимость:Из определения [[M-сводимость|m-сведения]] следует, что мы должны доказать, что машина Тьюринга <tex>M</tex> допускает <tex>w</tex> тогда и только тогда, когда построенный экземпляр МПСП имеет решение.
Сначала докажем для случая, когда <tex>i_1 = 1</tex>. Считаем, что '''Машина Тьюринка''' (<tex>MT</tex>) никогда не приходит в <tex>N</tex>. <tex>MT: (m, \omega)</tex>. Задача <tex>m(\omega) = yRightarrow</tex> не разрешима. Предположим, что мы умеем решать '''МПСП'''.
Если <tex>MT\Leftarrow</tex> остановится, добъёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c)Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, (a_i = \$ b = \$)</tex>. Соответственнои, получаем <tex>a_i = d \#_p</tex>как было сказано выше, если в первой строке никогда не будет символа <tex>b_i = \#_q c_{yes}</tex> и <tex>\delta(q, c) = <pто "сравнять" строки по длине не удастся. Значит, dесли МПСП имеет решение, \rightarrow>то символ </tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e_{yes}</tex> рано или поздно появится. А значит и машина Тьюринга допустит <tex>\delta (a, c) = <p, d, \leftarrow>w</tex>.Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.
Теперь остаётся избавиться от требования фиксированного == См. также ==* [[Неразрешимость исчисления предикатов первого индексапорядка]]* [[Примеры неразрешимых задач:задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]'''Верно'''* [[Примеры неразрешимых задач:задача о замощении|Задача о замощении]]* умеем '''1ПСП''' <tex>\Rightarrow</tex> умеем '''ПСП'''[[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* не умеем '''1ПСП''' <tex>\Leftarrow</tex>не умеем '''ПСП''''''Необходимо''':[[Неразрешимость задачи об эквивалентности КС-грамматик]]* не умеем '''1ПСП''' <tex>\Rightarrow</tex> не умеем '''ПСП'''[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
Возьмём экземпляр задачи 1ПСП: <tex>(( a_1 == Источники информации ==* Хопкрофт Д., \ldots Мотвани Р., a_n ) Ульман Д. Введение в теорию автоматов, ( b_1 языков и вычислений, \ldots 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», b_n ))</tex>2008. — С. 528. Вставим между каждой парой символов во всех строках символ <tex>— ISBN 5-8459-1347-0*<[http:/tex>/en.wikipedia.org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem]
<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 = 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>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.* <tex>a_{n+1} = \$</tex>* <tex>b_{n+1} = *\$</tex>Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.== Литература ==* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.[[Категория: Примеры неразрешимых задач]]
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> |}Решение этой проблемы соответствий Поста будет являться последовательность индексов <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'' Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.}} == Неразрешимость языка ПСП ==
{{Определение
|definition=
}}
=== Сведение универсального языка к МПСП ===
{{Определение
|definition=
Назовём '''Модифицированной проблемой соответствий Поста (МПСП)снимком состояния [[Машина Тьюринга|МТ]]''' называется вопрос существования последовательности индексов строку вида <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>no</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>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>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>start</tex> и <tex>yes</tex>, алфавит ленты содержит символы <tex>a</tex> и <tex>b</tex>. Переходы автомата устроены следующим образом: <tex>\delta (start, a) = \langle start, b, \rightarrow \rangle</tex>; <tex>\delta (start, b) = \langle yes, b, \downarrow \rangle</tex>; из <tex>yes</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 \#_{start}</tex> |<tex>\#_{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 |<tex>\#_{yes}</tex> |<tex>\#_{yes} a</tex> |- |10 |<tex>\#_{yes}</tex> |<tex>\#_{yes} b</tex> |- |11 |<tex>\$'</tex> |<tex>\#_{yes} \$ \$'</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 \$ \#_{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 \$ \#_{yes} b</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex> |- |align="center" | 10 |align="center" | 4 |<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex> |<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex> |- |align="center" | 11 |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</tex> |- |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 \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex> |} {{Лемма
|statement=
|proof=
Если <tex>a_1 = \$ \#_s \omega \$w</tex> допускается <tex>M</tex>, то можно проимитировать работу <tex>b_1 = \$M</tex>.Получаем со входом <tex>\$ A_0 \$ \ldots \$ A_k \$w</tex>и, как показано в примере выше, получить равные строки из элементов списков <tex>\$ A_i \ldotsA</tex>и <tex>B</tex>. То есть найти решение МПСП.
}}
{{Теорема
|statement=
ПСП не разрешима.
|proof=
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.
}}
