Recursive Analysis Characterized as a Class of Real Recursive Functions

Issue title: SPECIAL ISSUE MCU2004

Article type: Research Article

Authors: Bournez, Olivier | Hainry, Emmanuel

Affiliations: INRIA LORIA (UMR 7503 CNRS-INPL-INRIA-Nancy2-UHP), Campus scientifique, BP 239, 54506 Vandoeuvre-Lés-Nancy, France. E-mail: Olivier.Bournez@loria.fr | INPL LORIA (UMR 7503 CNRS-INPL-INRIA-Nancy2-UHP), Campus scientifique, BP 239, 54506 Vandoeuvre-Lés-Nancy, France. E-mail: Emmanuel.Hainry@loria.fr

Abstract: Recently, using a limit schema, we presented an analog and machine independent algebraic characterization of elementary functions over the real numbers in the sense of recursive analysis. In a different and orthogonal work, we proposed a minimalization schema that allows to provide a class of real recursive functions that corresponds to extensions of computable functions over the integers. Mixing the two approaches we prove that computable functions over the real numbers in the sense of recursive analysis can be characterized as the smallest class of functions that contains some basic functions, and closed by composition, linear integration, minimalization and limit schema.

Journal: Fundamenta Informaticae, vol. 74, no. 4, pp. 409-433, 2006