11. Теорема Клини о неподвижной точке

Для доказательства рекурсивности некоторых операций в теории конструктивных ординалов Клини [1] доказал важную теорему, которую обычно называют теоремой о рекурсии или теоремой Клини о неподвижной точке.

Рассмотрим два алфавита, и пусть универсальна для частично рекурсивных функций, переводящих слова из первого алфавита в слова из второго, т. е. если функция с гёделевским номером будучи применена к аргументу а, дает значение 6.

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

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

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

и есть искомая неподвижная точка, так как

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

Соответствующая теорема для рекурсивно перечислимых множеств известна как теорема Майхилла о неподвижной точке.

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

Доказательство во всех деталях аналогично только что приведенному.

Пример. Чтобы найти натуральное число которое является гёделевским номером рекурсивно перечислимого множества с единственным элементом достаточно применить теорему Майхилла о неподвижной точке к отношению равенства между натуральными числами. Заметим, что уже в этом простом случае не ясно, как найти без обращения к теореме о неподвижной точке.