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

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

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

Лит.:[1] П е т е р Р., Рекурсивные функции, пер. с нем., М., 1954. Н. В. Белякин.

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

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

1977—1985