Recursive Analysis Characterized as a Class of Real Recursive Functions

• Autorzy: Bournez O. , Hainry E.
• Języki publikacji: EN

Abstrakty

EN

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.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 409--433
• Opis fizyczny: bibliogr. 36 poz., wykr.

Twórcy

autor

Bournez O.

autor

Hainry E.

• INRIA, LORIA (UMR 7503 CNRS-INPL-INRIA-Nancy2-UHP), Campus scientifique, BP 239, 54506 Vandoeuvre-Les-Nancy, France,

Bibliografia

• [1] Arnold, V. I.: Ordinary differential equations, Springer-Verlag, Berlin, 1992.
• [2] Asarin, E., Maler, O.: Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy, Journal of Computer and System Sciences, 57(3), December 1998, 389-398.
• [3] Bournez, O.: Complexité Algorithmique des Systèmes Dynamiques Continus et Hybrides, Ph.D. Thesis, Ecole Normale Supérieure de Lyon, Janvier 1999.
• [4] Bournez, O., Hainry, E.: An Analog Characterization of Elementarily Computable Functions Over the Real Numbers, 31th International Colloquium on Automata Languages and Programming (ICALP'04) (J. Dıaz, J. Karhumäki, A. Lepisto, D. T. Sannella, Eds.), 3142, Springer, Turku, Finland, 2004.
• [5] Bournez, O., Hainry, E.: Real Recursive Functions and Real Extentions of Recursive Functions, Machines, Computations and Universality (MCU'2004) (M. Margenstern, Ed.), 3354, Springer-Verlag, Saint-Petersburg, Russia, 2004.
• [6] Bournez, O., Hainry, E.: Elementarily Computable Functions Over the Real Numbers and R-Sub-Recursive Functions, Theoretical Computer Science, 348(2-3), December 2005, 130-147.
• [7] Bowles, M. D.: U.S. technological enthusiasm and British technological skepticism in the age of the analog brain, IEEE Annals of the History of Computing, 18(4), October-December 1996, 5-15, ISSN 1058-6180.
• [8] Brattka, V.: Computability over Topological Structures, in: Computability and Models (S. B. Cooper, S. S. Goncharov, Eds.), Kluwer Academic Publishers, New York, 2003, 93-136.
• [9] Bush, V.: The differential analyser, Journal of the Franklin Institute, 1931, 447-488.
• [10] Campagnolo, M., Moore, C., Costa, J. F.: An Analog Characterization of the Subrecursive Functions, Proc. 4th Conference on Real Numbers and Computers (P. Kornerup, Ed.), Odense University Press, 2000.
• [11] Campagnolo,M., Moore, C., Costa, J. F.: An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity, 18(4), 2002, 977-1000.
• [12] Campagnolo,M. L.: Computational complexity of real valued recursive functions and analog circuits, Ph.D. Thesis, IST, Universidade Técnica de Lisboa, 2001.
• [13] Clote, P.: Computational Models and Function Algebras, in: Handbook of Computability Theory (E. R. Griffor, Ed.), North-Holland, Amsterdam, 1998, ISBN 0-444-89882-4, 589-681.
• [14] Etesi, G., Németi, I.: Non-Turing computations via Malament-Hogarth space-times, International Journal Theoretical Physics, 41, 2002, 341-370.
• [15] Grac¸a, D. S., Costa, J. F.: Analog computers and recursive functions over the reals, Journal of Complexity, 19(5), 2003, 644-664.
• [16] Grzegorczyk, A.: Computable functionals, Fundamenta Mathematicae, 42, 1955, 168-202.
• [17] Hogarth, M. L.: Does General Relativity Allow an Observer to View an Eternity in a Finite Time?, Foundations of Physics Letters, 5, 1992, 173-181.
• [18] Kalmár, L.: Egyszerü példa eld¨onthetetlen aritmetikai problémára, Mate és fizikai lapok, 50, 1943, 1-23.
• [19] Lacombe, D.: Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables rélles III, Comptes Rendus de l'Académie des Sciences Paris, 241, 1955, 151-153.
• [20] Mills, J.: Programmable VLSI Extended Analog Computer for Cyclotron Beam Control, Technical Report 441, Indiana University Computer Science, September 1995.
• [21] Moore, C.: Recursion theory on the reals and continuous-time computation, Theoretical Computer Science, 162(1), 5 August 1996, 23-44.
• [22] Mycka, J.: Infinite limits and R-recursive functions, Acta Cybernetica, 16, 2003, 83-91.
• [23] Mycka, J.: μ-Recursion and infinite limits, Theoretical Computer Science, 302, 2003, 123-133.
• [24] Mycka, J., Costa, J. F.: The P 6= NP conjecture, Submitted.
• [25] Mycka, J., Costa, J. F.: Real recursive functions and their hierarchy, Journal of Complexity, 20(6), 2004, 835-857.
• [26] Mycka, J., Costa, J. F.: Undecidability over continuous-time, 2005, Submitted to the Logic Journal of the IGPL, Oxford University Press.
• [27] Odifreddi, P.: Classical Recursion Theory, Volume I, vol. 125 of Studies in Logic and the Foundations of Mathematics, North-Holland, April 1992.
• [28] Odifreddi, P.: Classical Recursion Theory, Volume II, vol. 143 of Studies in Logic and the Foundations of Mathematics, North-Holland, 1999.
• [29] Pour-El, M. B., Richards, J. I.: Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer, Berlin, 1989.
• [30] Ramis, E., Deschamp, C., Odoux, J.: Cours de Mathématiques Spéciales, Tome 3, Topologie et éléments d'analyse, Masson, February 1995.
• [31] Rose, H.: Subrecursion: Functions and Hierarchies, Clarendon Press, 1984.
• [32] Rubel, L. A.: The Extended Analog Computer, Advances in Applied Mathematics, 14, 1993, 39-50.
• [33] Shannon, C. E.: Mathematical Theory of the Differential Analyser, Journal of Mathematics and Physics MIT, 20, 1941, 337-354.
• [34] Thomson (Lord Kelvin), W.: On an instrument for calculating the integral of the product of two given functions, Proceedings of the Royal Society of London, 24, 1876.
• [35] Turing, A.: On computable numbers, with an application to the "Entscheidungsproblem", Proceedings of the London Mathematical Society, 42(2), 1936, 230-265.
• [36] Weihrauch, K.: Computable Analysis, Springer, 2000.