×

Analog computers and recursive functions over the reals. (English) Zbl 1059.68041

Summary: In this paper we show that Shannon’s General Purpose Analog Computer (GPAC) is equivalent to a particular class of recursive functions over the reals with the flavour of Kleene’s classical recursive function theory.
We first consider the GPAC and several of its extensions to show that all these models have drawbacks and we introduce an alternative continuous-time model of computation that solves these problems. We also show that this new model preserves all the significant relations involving the previous models (namely, the equivalence with the differentially algebraic functions).
We then continue with the topic of recursive functions over the reals, and we show full connections between functions generated by the model introduced so far and a particular class of recursive functions over the reals.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bush, V., The differential analyzer. A new machine for solving differential equations, J. Franklin Inst., 212, 447-488 (1931) · Zbl 0003.06504
[2] Carlson, B. C., Special Functions of Applied Mathematics (1977), Academic Press: Academic Press New York · Zbl 0394.33001
[3] Campagnolo, M. L.; Moore, C., Upper and lower bounds on continuous-time computation, (Antoniou, I.; Calude, C. S.; Dinneen, M. J., Unconventional Models of Computation, UMC’2K, DMTCS (2001), Springer: Springer Berlin), 135-153 · Zbl 0967.68068
[4] Campagnolo, M. L.; Moore, C.; Costa, J. F., Iteration, inequalities, and differentiability in analog computers, J. Complexity, 16, 4, 642-660 (2000) · Zbl 0967.68075
[5] Campagnolo, M. L.; Moore, C.; Costa, J. F., An analog characterization of the Grzegorczyk hierarchy, J. Complexity, 18, 4, 977-1000 (2002) · Zbl 1030.68047
[6] D.S. Graça, The general purpose analog computer and recursive functions over the reals, M.Sc. Thesis, IST/UTL, 2002 (available online at http://w3.ualg.pt/ dgraca; D.S. Graça, The general purpose analog computer and recursive functions over the reals, M.Sc. Thesis, IST/UTL, 2002 (available online at http://w3.ualg.pt/ dgraca
[7] Hungerford, T. W., Algebra (1996), Springer: Springer Berlin
[8] Koiran, P.; Cosnard, M.; Garzon, M., Computability with low-dimensional dynamical systems, Theoret. Comput. Sci., 132, 113-128 (1994) · Zbl 0821.68053
[9] Lipshitz, L.; Rubel, L. A., A differentially algebraic replacement theorem, and analog computation, Proc. Amer. Math. Soc., 99, 2, 367-372 (1987) · Zbl 0626.34012
[10] Moore, C., Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett., 64, 2354-2357 (1990) · Zbl 1050.37510
[11] Moore, C., Recursion theory on the reals and continuous-time computation, Theoret. Comput. Sci., 162, 23-44 (1996) · Zbl 0871.68027
[12] Pour-El, M. B., Abstract computability and its relations to the general purpose analog computer, Trans. Amer. Math. Soc., 199, 1-28 (1974) · Zbl 0296.02022
[13] Shannon, C., Mathematical theory of the differential analyzer, J. Math. Phys. MIT, 20, 337-354 (1941) · Zbl 0061.29410
[14] Siegelmann, H. T., Neural Networks and Analog Computation: Beyond the Turing Limit (1999), Birkhäuser: Birkhäuser Basel · Zbl 0912.68161
[15] Stroock, D. W., A Concise Introduction to the Theory of Integration (1999), Birkhäuser: Birkhäuser Basel · Zbl 0912.28001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.