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

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

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

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

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

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

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

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

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

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

Следствие

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

Литература

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

См. также

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