Математическая энциклопедия - универсальная функция
Связанные словари
Универсальная функция
для данного класса Кфункций типа функция 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.
С. Н. Артемов.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 552 | |
2 | 479 | |
3 | 475 | |
4 | 469 | |
5 | 451 | |
6 | 435 | |
7 | 434 | |
8 | 430 | |
9 | 420 | |
10 | 420 | |
11 | 418 | |
12 | 410 | |
13 | 401 | |
14 | 373 | |
15 | 371 | |
16 | 368 | |
17 | 362 | |
18 | 360 | |
19 | 360 | |
20 | 359 |