Теорема Поста

Шаблон:Значения Теорема По́ста — теорема теории вычислимости о рекурсивно перечислимых множествах.

Формулировка теоремы

Если множество $M$ и его дополнение $\bar{M}$ в множестве натуральных чисел ℕ рекурсивно перечислимы, то множества $M$ и $\bar{M}$ разрешимы.

Доказательство

Необходимость. Можно считать, что $M\ne \varnothing$. Значит существует $a\in M$ и $b\in ̸M$. Так как $M$ разрешимо, то его характеристическая функция ${\chi }_M(x)$ вычислима. Рассмотрим функцию $f(x)$:

$f(x)=\{\begin{array}{c}x,\text{ if }{\chi }_M(x)=1\\ a,\text{ if }{\chi }_M(x)=0\end{array}$

Тогда $M=\{f(0),f(1),....\}$ — является множеством значений $f(x)$, значит $M$ рекурсивно перечислимо. Аналогично, рассмотрим функцию $g(x)$:

$g(x)=\{\begin{array}{c}x,\text{ if }{\chi }_M(x)=0\\ b,\text{ if }{\chi }_M(x)=1\end{array}$

Тогда $\bar{M}=\{g(0),g(1),....\}$ — является множеством значений $g(x)$, значит $\bar{M}$ рекурсивно перечислимо.

Достаточность. Пусть $M$ и $\bar{M}$ рекурсивно перечислимы. Это означает, что существуют рекурсивные функции $f(x),g(x)$ множества значений которых есть $M,\bar{M}$ соответственно. Рассмотрим следующий алгоритм. Будем вычислять последовательно $f(0),g(0),f(1),g(1),....$. Поскольку любое натуральное $x\in M$, либо $x\in ̸M$, то в процессе вычисления на каком-то шаге в первом случае обнаружится такое $k$, что $f(k)=x$, а во втором случае — $g(k)=x$. В первом случае ${\chi }_M(x)=1$, а во втором — ${\chi }_M(x)=0$. Значит ${\chi }_M(x)$ вычислима, значит $M$ разрешимо.

Следствие

Если $M$ рекурсивно перечислимое, но не разрешимое множество, $\bar{M}$ — не рекурсивно перечислимое множество.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

См. также

• Перечислимое множество
• Разрешимое множество
• Характеристическая функция множества