69
правок
Изменения
Нет описания правки
|statement= Пусть <tex>V(n, x)</tex> - вычислимая функция.Тогда найдется такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>
|proof=
Так как <tex>U</tex> - универсальная, то найдется вычислимая всюду определенная <tex>h</tex> такая что <tex>\forall n, x</tex> <tex>V(n, x) = U(h(n), x)</tex>. По доказанному найдется такое <tex>n_0</tex> что <tex>U_{n0} = U_{h(n0)}</tex>. Тогда <tex>V(n0, x) = U(h(n0), x) = U(n0, x)</tex>. Взяв <tex>p=U_{n0}</tex> получаем требуемое утверждение.
}}
==Источники==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
