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

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

Формулировка теоремы[править]

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

Доказательство[править]

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

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

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

g (x) = {\begin{cases} x, if χ_{M} (x) = 0 \\ b, if χ_{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 \in̸ M$ , то в процессе вычисления на каком-то шаге в первом случае обнаружится такое $k$ , что $f (k) = x$ , а во втором случае — $g (k) = x$ . В первом случае $χ_{M} (x) = 1$ , а во втором — $χ_{M} (x) = 0$ . Значит $χ_{M} (x)$ вычислима, значит $M$ разрешимо.

Следствие[править]

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

Литература[править]

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

См. также[править]