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

Теорема 7.2.1. Пусть U – главная вычислимая универсальная функция для класса вычислимых функций одного аргумента, h(x) – произвольная всюду определенная вычислимая функция одного аргумента. Тогда существует такое число n, U_n=U_h(n), то есть n и h(n) – номера одной функции.

Приведенная теорема называется теоремой Клини о неподвижной точке или теоремой о рекурсии.

Классическим следствием теоремы о рекурсии выступает утверждение о том, что существует программа, печатающая на любом входе свой собственный текст. Это следствие формулируется в виде следующей теоремы.

Теорема 7.2.2. Пусть U(n, x) – главнаявычислимаяуниверсальная функция для класса всех вычислимых функций одного аргумента. Тогда существует такое число p, что U(p, x)=p для любого x.

Теорема 7.2.3. Если W – главное универсальное перечислимое множество, то всякая вычислимая всюду определенная функция h имеет неподвижную точку n, для которой W_n=W_h(n).

Определение 7.2.1. Два множества U₁ и U₂ вычислимо изоморфны, если существует биекция (вычислимая перестановка) f: N®N такая, что (x, y)Î U₁Û (f(x), f(y))Î U₂.

Теорема 7.2.4. Любые два главных универсальных множества для класса перечислимых подмножеств натурального ряда вычислимо изоморфны.