9. Теоремы об итерации

Мы докажем, что произвольная рекурсивная нумерация рекурсивно перечислимых множеств может быть в определенном смысле сведена к универсальной нумерации.

Пусть рекурсивно перечислимое отношение между натуральными числами и словами в данном алфавите. Тогда можно найти общерекурсивную функцию такую, что равно композиции и универсального отношения

Эту теорему мы назовем теоремой об итерации для рекурсивно перечислимых множеств.

Доказательство. Рассмотрим алфавит и запишем схемы данного отношения, отмеченные знаком кроме того, схемы

Пусть -гёделевский номер этого рекурсивно перечислимого множества. Тогда общерекурсивная функция, удовлетворяющая условиям теоремы.

Действительно, если то тогда и только тогда, когда что как раз и означает, что равно композиции

Теорема об итерации для частично рекурсивных функций столь же проста.

Если дана частично рекурсивная функция то мы можем найти общерекурсивную функцию такую, что где универсальная функция.

По аналогии с доказательством предыдущей теоремы мы полагаем равным гёделевскому номеру сечения в точке