29
правок
Изменения
м
== Примеры решений проблем соответсвия Поста ==
<tex>1)</tex>
{|class="wikitable" style="text-align: center"
|-
!Номер элемента
!<tex>1</tex>
!<tex>2</tex>
!<tex>3</tex>
!<tex>4</tex>
|-
!<tex>A</tex>
|<tex>01</tex>
|<tex>1</tex>
|<tex>101</tex>
|<tex>11</tex>
|-
!<tex>B</tex>
|<tex>0</tex>
|<tex>11</tex>
|<tex>10</tex>
|<tex>111</tex>
|}
Решение этой проблемы соответствий Поста будет являться последовательность индексов <tex>(1, 4, 3, 2)</tex>.
Проверим это.
<tex>sA = 01, 11, 101, 1</tex>
<tex>sB = 0, 111, 10, 11</tex>
Получаем то, что строки <tex>sA</tex> и <tex>sB</tex> равны, а значит последовательность индексов <tex>(1, 4, 3, 2)</tex> является решением этой проблемы соотвествий Поста.
<tex>2)</tex>
Иногда возникает ситуация, когда решений конкретной проблемы соотвествия Поста нет.
{|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>i_1 = 1</tex>, называется '''модифицированной проблемой соответствий Поста (МПСП)'''.
}}
== Примеры решений проблем соответсвия Поста ==
<tex>1)</tex>
{|class="wikitable" style="text-align: center"
|-
!Номер элемента
!<tex>1</tex>
!<tex>2</tex>
!<tex>3</tex>
!<tex>4</tex>
|-
!<tex>A</tex>
|<tex>01</tex>
|<tex>1</tex>
|<tex>101</tex>
|<tex>11</tex>
|-
!<tex>B</tex>
|<tex>0</tex>
|<tex>11</tex>
|<tex>10</tex>
|<tex>111</tex>
|}
Решение этой проблемы соответствий Поста будет являться последовательность индексов <tex>(1, 4, 3, 2)</tex>.
Проверим это.
<tex>sA = 01, 11, 101, 1</tex>
<tex>sB = 0, 111, 10, 11</tex>
Получаем то, что строки <tex>sA</tex> и <tex>sB</tex> равны, а значит последовательность индексов <tex>(1, 4, 3, 2)</tex> является решением этой проблемы соотвествий Поста.
<tex>2)</tex>
Иногда возникает ситуация, когда решений конкретной проблемы соотвествия Поста нет.
{|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>.
Решения не существует.
== Перечислимость языка ПСП ==
Скомбинировав обе леммы, мы сведем универсальный язык к языку ПСП, а так как универсальный язык неразрешим, то и ПСП — неразрешима.
}}
== См. также ==
