Изменения

Перейти к: навигация, поиск

Теорема о рекурсии

1004 байта добавлено, 10:13, 29 декабря 2011
Нет описания правки
* Найдется такая всюду определенная вычислимая <tex>h</tex> что <tex>\forall n </tex> <tex>h(n) \not\equiv n</tex>
|proof=
ОлолоОт противного. Пусть оба утверждения выполнены. <br>Определим функцию <tex>f</tex> так: <tex>f(x)=U(x,x)</tex>. Заметим что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. Согласно первому утверждению найдется всюду определенное вычислимое <tex>\equiv</tex>-продолжение <tex>g</tex> функции <tex>f</tex>. Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))</tex>, где <tex>h</tex> - функция из второго утверждения. Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(x)</tex>, т.е. <tex>f(x) \ne t(x)</tex>. Если <tex>f(x)= \perp</tex>, то <tex>f(x) \ne t(x)</tex>, т.к. <tex>f</tex> - всюду определена. Значит <tex>f</tex> всюду отлична от <tex>t</tex>, противоречие.
}}
}}
69
правок

Навигация