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

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

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

Если множество $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.

См. также