Recursions of higher degrees

From Encyclopedia of Mathematics
Revision as of 17:23, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Recursive definitions (cf. Recursive definition) that, in addition to numerical functions, use some functions of higher types as auxiliary objects. For example, in the case of recursion of the second degree such are the "substituting" functionals of type

as well as functionals that can be obtained from these by this recursion. The interesting property of recursion of higher degree is that multiple recursion can be reduced to single recursion using a transition to a higher degree. This forms the basis for the method of reducing multiple recursions to a normal form. It should be borne in mind that the terminology in this field is not definitely established. In particular, the term "recursions of higher degrees" is sometimes taken to mean normal forms of multiple recursions.


[1] R. Peter, "Recursive functions" , Acad. Press (1967) (Translated from German)



[a1] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1950) pp. 234
[a2] P. Odifreddi, "Classical recursion theory" , North-Holland (1989) pp. Chapt. II; esp. pp. 199ff
How to Cite This Entry:
Recursions of higher degrees. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by N.V. Belyakin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article