Общерекурсивная функция

- частично рекурсивная функция, определенная для всех значений аргументов. Понятие О. ф. может быть определено и независимо от понятия частично рекурсивной функции следующим образом. Класс всех О. ф.- это наименьший класс функций, содержащий все примитивно рекурсивные функции и замкнутый относительно композиции функций и наименьшего числа оператора при условии, что последний применяется к функции [img: http://localhost:8080/file/031603-108.jpg] лишь тогда, когда [img: http://localhost:8080/file/031603-109.jpg] Однако изучение О. ф. обычно ведется в классе всех частично рекурсивных функций. Это связано, в частности, с тем, что ни при каком натуральном n>0 не существует О. ф., универсальной для класса всех n-местных О. ф. Все О. ф. нумерически представимы в арифметике формальной, так что для любой такой функции [img: http://localhost:8080/file/031603-110.jpg] можно построить арифметич. формулу [img: http://localhost:8080/file/031603-111.jpg] обладающую следующим свойством: каковы бы ни были натуральные числа [img: http://localhost:8080/file/031603-112.jpg] [img: http://localhost:8080/file/031603-113.jpg] если [img: http://localhost:8080/file/031603-114.jpg] если же [img: http://localhost:8080/file/031603-115.jpg] [img: http://localhost:8080/file/031603-116.jpg], [img: http://localhost:8080/file/031603-117.jpg] - термы, изображающие числа k1,..., k п, k, символ [img: http://localhost:8080/file/031603-118.jpg] означает выводимость в арифметич. исчислении.