Математическая энциклопедия - частично рекурсивный оператор

отображение класса всех одноместных функций в себя, определяемое следующим образом. Пусть Ф zнек-рый перечисления оператор. С этим оператором естественным образом связан другой оператор к-рый действует на одноместных функциях. А именно, всякая функция имеет график множество всех пар ( х, у )таких, что При фиксированном способе кодирования пар натуральными числами этот график может рассматриваться как множество натуральных чисел. Если теперь также является графиком нек-рой функции то полагают В противном случае считают, что значение не определено. Таким образом, каждый оператор перечисления Ф z определяет нек-pый Ч. р. о.

Если Ч. р. о. определен на всех функциях, он наз. рекурсивным оператором. Ч. р. о., к-рый определен на всех всюду определенных функциях и переводит всюду определенные функции во всюду определенные, наз. общерекурсивным оператором. Не всякий Ч. р. о. может быть продолжен до рекурсивного оператора. Всякий общерекурсивный оператор является рекурсивным оператором. Обратное включение не имеет места.

Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.

В. Е. Плиско.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985