Математическая энциклопедия

УНИВЕРСАЛЬНАЯ ФУНКЦИЯ

для данного класса Кфункций типа - функция F(y, х1, . . ., хп)типа такая, что для всякой найдется при к-ром

Здесь - множество натуральных чисел, а равенство (*) означает, что функции f(x1, .. .,хn)и F(i, x1, . . .,хn)определены на одних и тех же наборах аргументов x1, . . .,хnиих значения на этих наборах совпадают. Иногда в определении У. ф. требуется, чтобы для всех функция F(i, x1, . . .,хn)принадлежала классу К(см. [4]). Имеются также др. варианты определения У. ф. (см. [1], [2]).
У. ф. существуют для всякого счетного класса функций. Следующие У. ф. играют важную роль в теории алгоритмов: 1) универсальные частично рекурсивные функции для классов всех n-местныхчастично рекурсивных функций,2) общерекурсивные У. ф. для классов всех n-местныхпримитивно рекурсивных функций.
Если функция универсальна для класса всех одноместных частично рекурсивных функций, то она не продолжается до рекурсивной всюду определенной функции, а множество определена} является примером перечислимого, но не разрешимого множества натуральных чисел.

Лит.:[1] Петер Р., Рекурсивные функции, пер. с нем., М., 1954; [2] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [3]Успенский В. А., Лекции о вычислимых функциях, М., 1960: [4] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965.
С. Н.Артемов.

  1. универсальная функция—universal function...Русско-английский машиностроительный словарь
  2. универсальная функция—universal function...Русско-английский юридический словарь
  3. универсальная функция—унверсальна функця...Русско-украинский политехнический словарь