ЧАСТИЧНО РЕКУРСИВНЫЙ ОПЕРАТОР
- ЧАСТИЧНО РЕКУРСИВНЫЙ ОПЕРАТОР
- отображение класса всех одноместных функций в себя, определяемое следующим образом. Пусть Ф z- нек-рый перечисления оператор. С этим оператором естественным образом связан другой оператор 
к-рый действует на одноместных функциях. А именно, всякая функция 
имеет график - множество всех пар ( х, у )таких, что 
При фиксированном способе кодирования пар натуральными числами этот график может рассматриваться как множество 
натуральных чисел. Если теперь 
также является графиком нек-рой функции 
то полагают 
В противном случае считают, что значение 
не определено. Таким образом, каждый оператор перечисления Ф z определяет нек-pый Ч. р. о. 
Если Ч. р. о. определен на всех функциях, он наз. рекурсивным оператором. Ч. р. о., к-рый определен на всех всюду определенных функциях и переводит всюду определенные функции во всюду определенные, наз. общерекурсивным оператором. Не всякий Ч. р. о. может быть продолжен до рекурсивного оператора. Всякий общерекурсивный оператор является рекурсивным оператором. Обратное включение не имеет места.
Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.
В. Е. Плиско.
Математическая энциклопедия. — М.: Советская энциклопедия.
И. М. Виноградов.
1977—1985.
Полезное
Смотреть что такое "ЧАСТИЧНО РЕКУРСИВНЫЙ ОПЕРАТОР" в других словарях:
РЕКУРСИВНЫЙ ОПЕРАТОР — всюду определенный частично рекурсивный оператор. В. Е. Плиско … Математическая энциклопедия
ОБЩЕРЕКУРСИВНЫЙ ОПЕРАТОР — частично рекурсивный оператор, к рый определен на всех всюду определенных функциях и переводит всюду определенные функции во всюду определенные. В. Е. Плиско … Математическая энциклопедия
СВОДИМОСТЬ — отношение между понятиями (предложениями, задачами, теориями и др.), играющее важнейшую роль в логике и математике; означает возможность редукции (сведéния) одного понятия к другому (аналогично для предложений, задач и др.). Интуитивное понимание … Философская энциклопедия
Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… … Энциклопедия инвестора
РЕКУРСИВНЫЕ ФУНКЦИИ И ПРЕДИКАТЫ — один из важнейших для оснований математики и математич. логики классов понятий, служащих уточнениями содержат. понятий эффективно вычислимой арифметической функции и эффективно разрешимого арифметического предиката, а в конечном счете, – и… … Философская энциклопедия
