Теорема Поста (Mykjybg Hkvmg)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

[править | править код]

Необходимость. Можно считать, что . Значит существует и . Так как разрешимо, то его характеристическая функция вычислима. Рассмотрим функцию :

Тогда  — является множеством значений , значит рекурсивно перечислимо. Аналогично, рассмотрим функцию :

Тогда  — является множеством значений , значит рекурсивно перечислимо.

Достаточность. Пусть и рекурсивно перечислимы. Это означает, что существуют рекурсивные функции множества значений которых есть соответственно. Рассмотрим следующий алгоритм. Будем вычислять последовательно . Поскольку любое натуральное , либо , то в процессе вычисления на каком-то шаге в первом случае обнаружится такое , что , а во втором случае — . В первом случае , а во втором — . Значит вычислима, значит разрешимо.

Если рекурсивно перечислимое, но не разрешимое множество,  — не рекурсивно перечислимое множество.

Литература

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