142
правки
Изменения
Нет описания правки
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.
|proof=
Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> - [[Диагональный метод.|универсальная функция]]. Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>.Это значит, что <tex>\forall n: g(n) \neq \bot </tex> и <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex>
}}
