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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:45, 26 апреля 2016.
TemplateTheoremIcon.svg Теорема Теорема Поста

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

Доказательство
Пусть для множества и примитивно-рекурсивных функций и для произвольного натурального числа справедливы эквивалентности
,
.


Рассмотрим функцию
.


Тогда — рекурсивная функция и
.


Литература