Математическая энциклопедия - примитивная рекурсия
Связанные словари
Примитивная рекурсия
способ определения функций от натуральных аргументов с натуральными значениями. Говорят, что (n+1)-местная функция f(x1, ... , х п, у). получена примитивной рекурсией из n-местной функции g( х 1, ... , х п).и ( п+2).местной функции h( х 1, ... , х n у, z), если для всех натуральных значений x1 ... , х п, у имеет место
и
Для данных gи hтакая функция f всегде существует и единственна. При n=0 определяющие равенства для f записываются в виде
Фундаментальным свойством П. р. является то, что при любом разумном уточнении понятия вычислимости функция f, полученная из вычислимых функций gи h с помощью П. р., сама вычислимая. П. р.одно из основных правил порождения из исходного набора простейших функций всех примитивно рекурсивных и всех частично рекурсивных функций.
Лит.:[1] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [2] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [3] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972. С. Н. Артемов.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 558 | |
2 | 484 | |
3 | 482 | |
4 | 474 | |
5 | 455 | |
6 | 443 | |
7 | 439 | |
8 | 436 | |
9 | 427 | |
10 | 425 | |
11 | 424 | |
12 | 415 | |
13 | 407 | |
14 | 378 | |
15 | 378 | |
16 | 374 | |
17 | 367 | |
18 | 367 | |
19 | 366 | |
20 | 365 |