Математическая энциклопедия - общерекурсивная функция
Связанные словари
Общерекурсивная функция
частично рекурсивная функция, определенная для всех значений аргументов. Понятие О. ф. может быть определено и независимо от понятия частично рекурсивной функции следующим образом. Класс всех О. ф.это наименьший класс функций, содержащий все примитивно рекурсивные функции и замкнутый относительно композиции функций и наименьшего числа оператора при условии, что последний применяется к функции лишь тогда, когда
Однако изучение О. ф. обычно ведется в классе всех частично рекурсивных функций. Это связано, в частности, с тем, что ни при каком натуральном n>0 не существует О. ф., универсальной для класса всех n-местных О. ф.
Все О. ф. нумерически представимы в арифметике формальной, так что для любой такой функции можно построить арифметич. формулу обладающую следующим свойством: каковы бы ни были натуральные числа если если же , термы, изображающие числа k1 , . .., k п , k, символ означает выводимость в арифметич. исчислении.
Лит.:[1] Новиков П. С, Элементы математической логики, 2 изд., М., 1973; [2] Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1971.
В. Е. Плиспо.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 550 | |
2 | 477 | |
3 | 472 | |
4 | 466 | |
5 | 449 | |
6 | 433 | |
7 | 431 | |
8 | 427 | |
9 | 418 | |
10 | 418 | |
11 | 416 | |
12 | 407 | |
13 | 399 | |
14 | 372 | |
15 | 369 | |
16 | 365 | |
17 | 360 | |
18 | 358 | |
19 | 358 | |
20 | 356 |