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

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

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

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