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

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

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

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

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

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

$f(x)={\begin{cases}x,{\text{ if }}\chi _{M}(x)=1\\a,{\text{ if }}\chi _{M}(x)=0\end{cases}}$

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

$g(x)={\begin{cases}x,{\text{ if }}\chi _{M}(x)=0\\b,{\text{ if }}\chi _{M}(x)=1\end{cases}}$

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

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

Следствие

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

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. — МЦНМО, 2002.
• Игошин В. И. Математическая логика и теория алгоритмов. — Academia, 2008.
• Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, Физматлит, 1986.

См. также

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