Изменения

|proof=Рассмотрим универсальную функцию, построенную ранее, и нумерацию, соответствующую ей. Обозначим программу, вычисляющую функцию <tex>V(n,x)</tex> как <tex>v(n,x)</tex>. Построим программу (назовем ее <tex>s</tex>) с одним параметром - <tex>m</tex>, которая генерирует код программы <tex>v(n,x)</tex>, но с фиксированным <tex>n = m</tex>, и возвращает ее номер в заданной нумерации. Построенная программа вычисляет искомую функцию для универсальной двуместной функции <tex>U</tex> и двуместной функции <tex>V</tex>, то есть <tex>V(n,x)=U(S(n),x)</tex>, где <tex>S</tex> - функция, вычисляемая программой <tex>s</tex>. Из вычислимости <tex>v</tex> следует существование <tex>V</tex>, и за конечное время мы можем вернуть номер любой программы в выбранной нумерации. Таким образом <tex>S</tex> - вычислимая, всюду определенная.

}}

== Литература ==