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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

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

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

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

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