Изменения

В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.

{{Определение

Универсальную функцию удобно представлять как интерпретатор, которому на вход подают функцию и её аргумент, а он исполняет функцию на данном аргументе и возвращает результат.

{{Теорема

|statement=Существует универсальная функция для класса вычислимых функций одного аргумента

}}

{{Теорема

|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.

Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).

{{Определение

|definition='''Нумерация (numbering)''' множества <tex>X-</tex> это такое всюду определенное отображение <tex> f : \mathbb{N} \rightarrow X</tex>, область значений которого есть все множество <tex>X</tex>.

Собственно, то, что с помощью главной нумерации мы можем легко получать номер композиции двух программ и является преимуществом главной нумерации относительно других.

{{Теорема