Изменения

Дана упорядоченная пара Даны два конечных последовательностей списка <tex>(A = (a_1, \ldotsdots, 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 , \ldotsdots, 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>, называется '''проблемой соответствий Поста (ПСП)'''. Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.

== Примеры решений проблем соответствия Поста == === Пример 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>. Решения не существует. == Перечислимость языка ПСП ==

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

Пусть даны последовательности Для списков <tex>aA</tex> и <tex>bB</tex> размера <tex>n</tex> из условия ПСП. Построим построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения: '''for ''' <tex>m = 1 .. \dots \infty</tex> for all '''foreach''' <tex>(i_1, i_2, \ldotsdots, i_m): 1 \leq leqslant i_j \leq leqslant n</tex> '''if ''' <tex>a_{i_1} \ldots dots a_{i_m} = b_{i_1} \ldots dots b_{i_m}</tex> '''return ''' ''true'' 

{{ТеоремаОпределение|definition=Проблема соответствий Поста, для которой фиксирован элемент последовательности индексов <tex>i_1 = 1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.}} Докажем [[Разрешимые (рекурсивные) языки|неразрешимость]] языка ПСП следующим образом. Докажем, что универсальный язык [[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-

МПСП неразрешимадля пары списков <tex>(A, B)</tex> сводится к ПСП для пары списков <tex>(C, D)</tex>.

Выполним Из определения [[M-сводимость|m-сведениесведения]] множества пар из машины Тьюринга (МТ) <tex>M</tex> следует, что мы должны доказать равносильность наличия решения для построенных экземпляров МПСП и строки ПСП. <tex>w\Rightarrow</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 i_2, \ldots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справаdots, <tex>pi_k)</tex> — текущее состояние автомата МТ, головка расположена справа от решение МПСП из условия леммы. То есть <tex>\#_pw_A = w_B</tex>. Построим последовательности таким образом, чтобы решение МПСП образовывало строкугде

<tex>\$' snap_1 \$ snap_2 \$ \ldots \$ snap_n \$ snap_{n_{-1}} \$ snap_w_A = a_1 a_{n_{-2}i_2} \$ \ldots \$ \#_dots a_{yesi_k} \$ \$'</tex>,

где <tex>snap_i</tex> — снимки последовательных состояний МТ от стартового до конечного, <tex>snap_w_B = b_1 b_{n_i_2} \dots b_{-ti_k}}</tex> — последний снимок с <tex>t</tex> удалёнными символами. Оговоримся, что состояния <tex>no</tex> в автомате МТ не существует (его роль может выполнять сток), допуск происходит при попадании в состояние <tex>yes</tex>.

Сформируем последовательности Рассмотрев цепочки <tex>aw_C</tex> и <tex>bw_D</tex> по МТ c аналогичными индексами, заметим, что мы имеем почти равные цепочки с той лишь разницей, что первой не хватает символа <tex>M</tex> и строке <tex>w\#</tex>в начале, а второй — в конце.Конкретно,

<tex>a_1 = \$' \#_c_1 c_{starti_2} w \$ </tex>, <tex>b_1 dots c_{i_k} = d_1 d_{i_2} \dots d_{i_k} \$'# </tex>;.

для всех символов Изменив первый индекс с <tex>c1</tex> алфавита ленты:на <tex>0</tex>, решим проблему с символом <tex>\#</tex> в начале. Добавив индекс <tex>n+1</tex> к набору, решим проблему с символом <tex>\#</tex> в конце.

<tex>a_i c_0 c_{i_2} \dots c_{i_k} c_{n+1} = cd_0 d_{i_2} \dots d_{i_k} d_{n+1} </tex>, <tex>b_i = c</tex>,.

<tex>a_i = \$Leftarrow</tex>, <tex>b_i = \$</tex>;

В любом существующем решении ПСП для всех правил списков <tex>MC, D</tex> вида должны выполняться условия: * <tex>i_1 = 0</tex>, так как только в паре <tex>\delta (pc_1, cd_1) = \langle q</tex> первые символы совпадают, d, \leftarrow \rangle* последний индекс равен <tex>n+1</tex> и для всех символов алфавита , так как только в паре <tex>e(c_{n+1}, d_{n+1})</tex>:строки заканчиваются одинаковыми символами.

Пусть последовательность <tex>a_i = (0, i_2, i_3, \#_q e ddots, i_k, n + 1)</tex>является решением ПСП. Иными словами, <tex>b_i = e \#_p c</tex>;

для всех правил <tex>M</tex> вида <tex>c_0 c_{i_2} \delta (p, c) dots c_{i_k} c_{n+1} = d_0 d_{i_2} \langle q, d, \rightarrow \rangledots d_{i_k} d_{n+1}</tex>:.

Если <tex>a_i = d 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} \#_qdots, i_f)</tex>— также решение ПСП, причём первый индекс равен <tex>0</tex>b_i и <tex>i_f = n + 1</tex>. Остальные индексы не превосходят <tex>n</tex>, но и не равны <tex>0</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\#_p c</tex>;подряд, а в правой её не может быть. Учитывая эти ограничения, перепишем получившееся равенство:

для всех правил <tex>M\# c_1 c_{i_2} \dots c_{i_{f-1}}\$</tex> вида <tex>\delta (p, c) = </tex> <tex>d_1 d_{i_2} \langle q, d, dots d_{i_{f-1}} \downarrow #\rangle$</tex>:.

Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>a_i = \#_q d$</tex>, <tex>b_i = \#_p c</tex>.получим

Заметим, что все элементы <tex>aa_1 a_{i_2} \dots a_{i_{f-1}} = b_1 b_{i_2} \dots b_{i_{f-1}}</tex> и <tex>b</tex>, кроме первых, имеют одинаковую длину. Значит, строка, составленная из элементов <tex>a</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>. Будем добавлять пары цепочек в эти списки по следующим правилам: :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 \$ \ldots dots \$ snap_n \$</tex>,

<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_{n-1} \$</tex>,

<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n+1} \$</tex>

<tex>\$' snap_1 \$ snap_2 \$ \ldots 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>a_i = \#_{yes}</tex>недостижимо, в первой строке никогда не будет символа <tex>b_i = \#_{yes} c</tex>,и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину.

Если же допускающее состояние встретится, то "съедая" по одному символу с помощью элементов правил <tex>a_i = \#_{yes}7</tex>, и <tex>8</tex> и копируя все остальные с помощью элементов из правил <tex>2</tex> и <tex>b_i = c \#_{yes}3</tex>,можно будет привести строки к виду

<tex>a_i = \$'</tex>, <tex>b_i = \#_{yes} \$ \$'</tex>. Если состояние <tex>yes</tex> недостижимо, в первой строке никогда не будет символа <tex>\#_{yes}</tex>, и ни одним из новых элементов воспользоваться не удастся. Значит, строки всегда будут иметь различную длину. Если же допускающее состояние встретится, с помощью новых элементов можно будет привести обе строки к виду

<tex>\$' snap_1 \$ snap_2 \$ \ldots dots \$ snap_n \$ snap_{n_{-1}} \$ snap_{n_{-2}} \$ \ldots dots \$ \#_{yes} \$ \$'</tex>.

Другими словамиИ наконец, «сравнять» строки возможно тогда и только тогда, когда автомат, принадлежащий <tex>M</tex>, допускает <tex>w</tex>. Таким образом, выполнено успешное m-сведение множества пар с помощью элементов из машины Тьюринга (МТ) правила <tex>M9</tex> и сравняем строки <tex>w</tex>, где <tex>M(w)</tex> не зависает, к множеству решений МПСП. }}

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

! Последовательность a<tex>A</tex> ! Последовательность b<tex>B</tex>

|<tex>\$' \#_{start} ab \$</tex> |<tex>\$'</tex>

|<tex>\$' \#_{start} ab \$</tex> |<tex>\$'</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start}</tex> |<tex>\$' \#_{start} a</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b</tex> |<tex>\$' \#_{start} ab</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$</tex> |<tex>\$' \#_{start} ab \$</tex>

|<tex>\$' \#_{start} ab \$ b \#_{start} b\$ b</tex> |<tex>\$' \#_{start} ab \$ 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\$ b \#_{yes} b \$</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$</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} b \$ \#_{yes} b</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ 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 \$ \#_{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 \$ \#_{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 \$ \#_{yes} \$ \$'</tex> |<tex>\$' \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$'</tex>

 {{ТеоремаЛемма

ПСП неразрешимаУниверсальный язык сводится к МПСП.

Выполним Из определения [[M-сводимость|m-сведениесведения]] множества решений МПСП к множеству решений ПСП. Пусть даны последовательности <tex>aследует, b</tex> из условия МПСП. Обозначим как <tex>left(wчто мы должны доказать, c)что машина Тьюринга </tex> и <tex>right(w, c)M</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> — символы, не встречающиеся в словах исходных последовательностейкогда построенный экземпляр МПСП имеет решение.

Пусть Если <tex>w_a = a_1 a_{i_2} \ldots a_{i_k}w</tex>, допускается <tex>w_b = b_1 b_{i_2} \ldots b_{i_k}M</tex>, то можно проимитировать работу <tex>w_a = w_bM</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_aA</tex> и <tex>w_b</tex>, а также <tex>\#</tex> (в конце); на нечётных — <tex>\$B</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>a'Поскольку все решения МПСП должны начинаться с первой пары, то длина соответствующих строк будет различаться, b'</tex> должны выполняться условия: * <tex>i_1 = 1</tex>и, так как только было сказано выше, если в паре первой строке никогда не будет символа <tex>(a'_1, b'_1)\#_{yes}</tex> первые символы совпадают;* последний индекс равен , то "сравнять" строки по длине не удастся. Значит, если МПСП имеет решение, то символ <tex>n+2\#_{yes}</tex>, так как только в паре рано или поздно появится. А значит и машина Тьюринга допустит <tex>(a'_{n+2}, b'_{n+2})w</tex> строки заканчиваются одинаковыми символами.

<tex>a'_1 a'_{i_2} \ldots a'_{i_k} Теорема|statement=ПСП не разрешима.|proof= b'_1 b'_{i_2Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.} \ldots b'_{i_k}</tex>.

Если <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_22-1}, \$) \ldots left(b_{i_{f-1}-1}, \$) \$ \#</tex>е изд. : Пер. Оставив из этих двух строк символы, стоящие на чётных позициях, и удалив с конца <tex>\#</tex>англ. — М.:Издательский дом «Вильямс», получим <tex>a_1 a_{i_22008. — С. 528. — ISBN 5-1} \ldots a_{i_{f8459-1}1347-1} = b_1 b_{i_2-1} \ldots b_{i_{f-1}-1}<0* [http://tex>en.}} По доказанному ранее, МПСП неразрешимаwikipedia. Тогда, вследствие теоремы для m-сведения, ПСП неразрешима.}}org/wiki/Post_correspondence_problem Wikipedia — Post correspondence problem]