Рекурсивный Оператор

такое отношение , где - множество натуральных чисел, что функция f, определенная на условием является рекурсивной функцией. В частности, при любом пуниверсальное отношение и нуль-отношение являются Р. О. Если Rи Sсуть n-местные Р. О., то отношения также будут Р. О. Относительно операций ,' система всех n-местных Р. О. Образует булеву алгебру. В. Е Плиско. ..

- класс эквивалентности для отношения рекурсивной эквивалентности, т. Е. Совокупность всех подмножеств натурального ряда, каждые два из к-рых могут быть приведены во взаимно однозначное соответствие с помощью частично рекурсивной функции. Таким образом, понятие Р. Э. Т. Служит в рекурсивной теории множеств аналогом понятия мощности в классич. Теории множеств. Так как любые два конечных множества рекурсивно эквивалентны тогда и только тогда, когда они содержат одинаковое число элементов, то ..

предикат Р(х 1, . .,х п), определенный на натуральных числах и такой, что функция f, заданная на натуральных числах условием истинно, ложно, является рекурсивной функцией. В. ..

рекурсивные определения, в к-рых в качестве вспомогательных объектов наряду с числовыми функциями используются нек-рые функционалы более высоких типов. Напр., для случая рекурсии второй ступени таковыми являются "подстановочные" функционалы вида а также функционалы, получаемые из них посредством этой рекурсии. Интересное свойство Р. В. С. Заключается в том, что многократную рекурсию можно свести к однократной за счет перехода к более высокой ступени. На этом основан метод приведения мног..