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

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

править

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

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

править

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

 

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

 

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

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

Следствие

править

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

Литература

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

См. также

править