72
правки
Изменения
Нет описания правки
===Определение универсальной функции===
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
{{Определение
Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.
===Существование универсальной функции===
{{Теорема
|statement=Существует универсальная функция
===Вычислимость универсальной функции===
{{Теорема
|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
}}
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
===Главная нумерация===
{{Определение
|definition=Нумерация, заданная двуместной универсальной функцией <tex>U(n,x)</tex> называется главной (Гёделевой), если для любой двуместной вычислимой функции <tex>V(n,x)</tex> существует вычислимая, всюду определенная функция <tex>S:\mathbb{N}\rightarrow\mathbb{N}</tex> такая, что <tex>V(n,x)=U(S(n),x)</tex>.
}}
{{Теорема
|statement=Существует главная нумерация.
|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> - вычислимая, всюду определенная.
}}
== Литература ==
[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин, А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]
