Изменения

Для доказательства теоремы рассмотрим некоторую вычислимую функциюБудем доказывать теорему от противного: предположим, от которой никакая что существует всюду определенная вычислимая функция не может отличаться всюду. Такой будет, например <tex>f(x) = U(x, x)h</tex> (действительно, если предположитьтакая, что существует вычислимая функция <tex>U_n \neq U_{h(n)}</tex>, всюду отличная от для любого <tex>f(n) = U(n</tex>. В терминах введенного нами отношения, это значит, n)что <tex>h</tex> не имеет <tex>\equiv</tex>, то нарушается определение универсальной функции{{---}} неподвижных точек.)

Рассмотрим некоторую вычислимую функцию, от которой никакая вычислимая функция не может отличаться всюду. Такой будет, например <tex>f(x) = U(x, x)</tex> (действительно, если предположить, что существует вычислимая функция <tex>g(n)</tex>, всюду отличная от <tex>f(n) = U(n, n)</tex>, то нарушается определение универсальной функции.) Согласно доказанной нами лемме, существует вычислимая и всюду определенная функция <tex>g(x)</tex>, являющаяся <tex>\equiv</tex> {{---}} продолжением функции <tex>f(x)</tex>. Давайте зададим функцию <tex>t(x)</tex> следующим образом: <tex>t(x) = hp(g(x))</tex>, где <tex>hp(x)</tex> - всюду определенная, вычислимая функция, не имеющая <tex>\equiv</tex> {{---}} неподвижных точек. Тогда <tex>t(x)</tex> всюду отличается от <tex>f(x)</tex> (в силу того, что <tex>p(x)</tex> не имеет неподвижных точек.) Получили противоречие.