A foundation for real recursive function theory
type: Item
instance of: scholarly article
title: A foundation for real recursive function theory
zbMATH Open document ID: 1189.03047
author: Bruno Loff
author: Jerzy Mycka
author: José Félix Costa
published in: Annals of Pure and Applied Logic
publication date: 2009-10-26T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/17964
review text: 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)].
Mathematics Subject Classification ID: 03D78
Mathematics Subject Classification ID: 28A05
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 5620638
zbMATH Keywords: real recursive functions
zbMATH Keywords: infinite limits
zbMATH Keywords: differential recursion
zbMATH Keywords: computability on reals
reviewed by: Timothy H. McNicholl
MaRDI profile type: Publication
OpenAlex ID: W2049452137
cites work: A new recursion-theoretic characterization of the polytime functions
cites work: Machines, Computations, and Universality
cites work: Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions
cites work: Q3416089
cites work: Universal computation and other capabilities of hybrid and continuous dynamical systems
cites work: Q4437079
cites work: Iteration, inequalities, and differentiability in analog computers
cites work: An analog characterization of the Grzegorczyk hierarchy
cites work: The elementary computable functions over the real numbers: applying two new techniques
cites work: Q4934292
cites work: Simplifications of the recursion scheme
cites work: Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18--23, 2007. Proceedings.
cites work: New Computational Paradigms
cites work: Analog computers and recursive functions over the reals.
cites work: Q3995847
cites work: Computability on reals, infinite limits and differential equations
cites work: Recursion theory on the reals and continuous-time computation
cites work: Q4439455
cites work: \(\mu\)-recursion and infinite limits.
cites work: Real recursive functions and their hierarchy
cites work: The P\(\neq\) NP conjecture in the context of real and complex analysis
cites work: Undecidability over Continuous Time
cites work: A new conceptual framework for analog computation
cites work: Classical recursion theory. The theory of functions and sets of natural numbers
cites work: Q3532839
cites work: Q3838091
cites work: Q4952400
DOI: 10.1016/J.APAL.2009.01.013
description: scientific article; zbMATH DE number 5620638