Меню Главная Случайная статья Настройки Теорема Поста Материал из https://ru.wikipedia.org Теорема Поста — теорема теории вычислимости о рекурсивно перечислимых множествах. Содержание 1 Формулировка теоремы 2 Доказательство 3 Следствие 4 Литература 5 См. также Формулировка теоремы Если множество ${\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. См. также Перечислимое множество Разрешимое множество Характеристическая функция множества