1632
правки
Изменения
м
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
rollbackEdits.php mass rollback
{{Определение
|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>\forall</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> определено).
Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.
{{Теорема
|proof = От противного. Пусть <tex>U(n, x)</tex> — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента <tex>d(x) = U(x, x) + 1</tex>. <tex>\exists n \in N : d(x) = U(n, x)</tex> в силу того, что <tex>U(n, x)</tex> — универсальная для соответствующего класса функций. Так как <tex>d(x)</tex> всюду определена, то она не зависает на аргументе <tex>n</tex>. Значит <tex>d(n) = U(n, n)</tex>, но в то же время <tex>d(n) = U(n, n) + 1</tex>. Противоречие.
}}
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
== Литература ==
[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин, А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]
''В. А. Успенский'' '''Лекции о вычислимых функциях''' — М.: ГИФМЛ, 1960, с. 203
