Изменения

|proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию <tex>U(n, x) = p_n(x)</tex>, где <tex>p_n</tex> — <tex>n</tex>-ая программа в указанной нумерации. <tex>\forall</tex> вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x) = p_n(x)</tex>, очевидно, является вычислимой функцией. Значит <tex>U(n, x)</tex> — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что <tex>U(n, x)</tex> вычислима. Действительно, для того, чтобы вычислить <tex>U(n, x)</tex> , достаточно вернуть вывод программы <tex>p_n</tex> на входе <tex>x</tex>.