Изменения
Нет описания правки
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
{{Определение
|definition = Функция <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''универсальной '''(англ. ''universal function)''' ) для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x)</tex> является вычислимой функцией и для любой вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = U(n, x)</tex>
}}
Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции <tex> U_n </tex> является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди <tex>U_n</tex> (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких <tex> n </tex>, для которых <tex> U(n, n) </tex> определено).
Универсальную функцию удобно представлять как интерпретатор, которому на вход подают функцию и её аргумент, а он исполняет функцию на данном аргументе и возвращает результат.
==Существование универсальной функции==
{{Теорема
|statement=Существует универсальная функция для класса вычислимых функций одного аргумента
{{Определение
|definition=Нумерация, заданная двуместной универсальной функцией <tex>U(n,x)</tex> называется '''главной (Гёделевой) ''' (''англ.''Godel numbering)''', если для любой двуместной вычислимой функции <tex>V(n,x)</tex> существует вычислимая, всюду определенная функция <tex>S:\mathbb{N}\rightarrow\mathbb{N}</tex> такая, что <tex>V(n,x)=U(S(n),x)</tex>.
}}
{{Теорема
