Differential recursion

ABSTRACT

We present a redevelopment of the theory of real-valued recursive functions that was introduced by C. Moore in 1996 by analogy with the standard formulation of the integer-valued recursive functions. While his work opened a new line of research on analog computation, the original paper contained some technical inaccuracies. We discuss possible attempts to remove the ambiguity in the behavior of the operators on partial functions, with a focus on his “primitive recursive” functions generated by the differential recursion operator that solves initial value problems. Under a reasonable reformulation, the functions in this class are shown to be analytic and computable in a strong sense in computable analysis. Despite this well-behavedness, the class turns out to be too big to have the originally purported relation to differentially algebraic functions, and hence to C. E. Shannon's model of analog computation.

REFERENCES

• 1: Artin, E. 1964. The Gamma Function. Athena Series: Selected Topics in Mathematics. Holt, Rinehart and Winston, New York. Translated by Michael Butler from Einführung in die Theorie der Gamma-Funktion, 1931.
• 2: Lenore Blum , Felipe Cucker , Michael Shub , Steve Smale, Complexity and real computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: Bournez, O. and Campagnolo, M. L. 2008. A survey on continuous time computations. In New Computational Paradigms. Springer, New York, 383--423.
• 4: Olivier Bournez , Emmanuel Hainry, Recursive Analysis Characterized as a Class of Real Recursive Functions, Fundamenta Informaticae, v.74 n.4, p.409-433, December 2006
• 5: Bush, V. 1931. The Differential Analyzer: A new machine for solving differential equations. J. Franklin Institute 212, 447--488.
• 6: Campagnolo, M. L. 2001. Computational complexity of real valued recursive functions and analog circuits. Ph.D. thesis, Instituto Superior Técnico.
• 7: Manuel Lameiras Campagnolo , Cristopher Moore, Upper and Lower Bounds on Continuous-Time Computation, Proceedings of the Second International Conference on Unconventional Models of Computation, p.135-153, December 13-16, 2000
• 8: Manuel Lameiras Campagnolo , Cristopher Moore , José Félix Costa, Iteration, inequalities, and differentiability in analog computers, Journal of Complexity, v.16 n.4, p.642-660, Dec. 1, 2000 [doi>10.1006/jcom.2000.0559]
• 9: Campagnolo, M. L. and Ojakian, K. 2008. The elementary computable functions over the real numbers: Applying two new techniques. Arch. Math. Logic 46, 7--8, 593--627.
• 10: Edalat, A. and Pattinson, D. 2004. A domain theoretic account of Picard's theorem. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 3142, 494--505.
• 11: Graça, D. 2002. The General Purpose Analog Computer and recursive functions over the reals. M.S. thesis, Instituto Superior Técnico.
• 12: Graça, D. 2004. Some recent developments on Shannon's General Purpose Analog Computer. Math. Logic Quart. 50, 473--485.
• 13: Graça, D. S., Zhong, N., and Buescu, J. 2009. Computability, noncomputability and undecidability of maximal intervals of IVPs. Trans. Amer. Math. Soc. To appear.
• 14: Grzegorczyk, A. 1955. Computable functionals. Fundam. Math. 42, 168--202.
• 15: Hölder, O. L. 1886. Ueber die Eigenschaft der Gammafunction keiner algebraischen Differentialgleichung zu genügen. Mathematische Annalen 28, 1--13.
• 16: Katriel, G. 2003. Solution to Rubel's question about differentially algebraic dependence on initial values. Illinois J. Math. 47, 4, 1261--1272.
• 17: Kawamura, A. 2005. Type-2 computability and Moore's recursive functions. In Proceedings of the 6th International Workshop on Computability and Complexity in Analysis. Electronic Notes in Theoretical Computer Science, vol. 120, 83--95.
• 18: Ker-I Ko, On the computational complexity of ordinary differential equations, Information and Control, v.58 n.1-3, p.157-194, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80062-X]
• 19: Ko, K.-I. 1992. On the computational complexity of integral equations. Ann. Pure Appl. Logic 58, 3, 201--228.
• 20: Krantz, S. G. and Parks, H. R. 2002. A Primer of Real Analytic Functions, 2nd ed. Birkhäuser Advanced Texts. Birkhäuser, Boston.
• 21: Lipshitz, L. and Rubel, L. A. 1987. A differentially algebraic replacement theorem, and analog computability. Proc. Amer. Math. Soc. 99, 2, 367--372.
• 22: Loff, B., Costa, J. F., and Mycka, J. 2007. Computability on reals, infinite limits and differential equations. Appl. Math. Comput. 191, 2, 353--371.
• 23: Miller, W. 1970. Recursive function theory and numerical analysis. J. Comput. Syst. Sci. 4, 465--472.
• 24: Cristopher Moore, Recursion theory on the reals and continuous-time computation, Theoretical Computer Science, v.162 n.1, p.23-44, Aug. 5, 1996 [doi>10.1016/0304-3975(95)00248-0]
• 25: Moore, E. H. 1896. Concerning transcendentally transcendental functions. Mathematische Annalen 48, 1-2, 49--74.
• 26: Jerzy Mycka , José Félix Costa, Real recursive functions and their hierarchy, Journal of Complexity, v.20 n.6, p.835-857, December 2004 [doi>10.1016/j.jco.2004.06.001]
• 27: Orponen, P. 1997. A survey of continuous-time computation theory. In Advances in Algorithms, Languages, and Complexity. Kluwer Academic Publishers, 209--224.
• 28: Ostrowski, A. 1920. Über Dirichletsche Reihen und algebraische Differentialgleichungen. Mathematische Zeitschrift 8, 241--298.
• 29: Roger Penrose, The emperor's new mind: concerning computers, minds, and the laws of physics, Oxford University Press, Inc., New York, NY, 1989
• 30: Pour-El, M. B. 1974. Abstract computability and its relation to the General Purpose Analog Computer (some connections between logic, differential equations and analog computers). Trans. Amer. Math. Soc. 199, 1--28.
• 31: Pour-El, M. B. and Richards, I. 1979. A computable ordinary differential equation which possesses no computable solution. Ann. Math. Logic 17, 1-2, 61--90.
• 32: Ritt, J. F. and Gourin, E. 1927. An assemblage-theoretic proof of the existence of transcendentally transcendental functions. Bull. Amer. Math. Soc. 33, 182--184.
• 33: Rubel, L. A. 1992. Some research problems about algebraic differential equations II. Illinois J. Math. 36, 4, 659--680.
• 34: Shannon, C. E. 1941. Mathematical theory of the Differential Analyzer. J. Math. Phys. 20, 4, 337--354.
• 35: A Vergis , K Steiglitz , B Dickinson, The complexity of analog computation, Mathematics and Computers in Simulation, v.28 n.2, p.91-113, April 1986 [doi>10.1016/0378-4754(86)90105-9]
• 36: Walter, W. 1998. Ordinary Differential Equations. Graduate Texts in Mathematics, Readings in Mathematics, vol. 182. Springer, New York. Translated by Russell Thompson from the sixth edition of Gewöhnliche Differentialgleichungen, 1996.
• 37: Klaus Weihrauch, Computable analysis: an introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 38: Andrew Chi-Chih Yao, Classical physics and the Church--Turing Thesis, Journal of the ACM (JACM), v.50 n.1, p.100-105, January 2003 [doi>10.1145/602382.602411]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

General Terms:
Theory

Keywords:
Analog computation, differentially algebraic functions, initial value problems, real recursive functions, transcendentally transcendental functions