A foundation for real recursive function theory (Q1032628): Difference between revisions

The class of recursive real functions, REC\((\mathbb R)\), is defined as the smallest set containing the constant functions 0, 1, and \(-1\), the projection functions, and closed under composition, aggregation, differential recursion, and the lim sup operator. The differential recursion operator is the solution operator for a class of Cauchy problems and is a continuous analog of primitive recursion. It is shown that step functions such as Kronecker's \(\delta\) are in REC\((\mathbb R)\). A hierarchy of functions in REC\((\mathbb R)\) is also developed. It is also shown that REC\((\mathbb R)\) is precisely the class of functions whose graph lies in the analytic hierarchy. This work builds on the work of \textit{C. Moore} [Theor. Comput. Sci. 162, No.~1, 23--44 (1996; Zbl 0871.68027)] and previous work by the first and third authors [\textit{J. Mycka} and \textit{J. F. Costa}, J. Complexity 20, No.~6, 835--857 (2004; Zbl 1085.03030)].