Изменения

Перейти к: навигация, поиск

Универсальная функция

3 байта добавлено, 15:02, 1 ноября 2016
Нет описания правки
|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>U</tex> при фиксированном <tex>n</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> определено).
Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.
Анонимный участник

Навигация