×

Iteration, inequalities, and differentiability in analog computers. (English) Zbl 0967.68075

Summary: Shannon’s General Purpose Analog Computer (GPAC) is an elegant model of analog computation in continuous time. In this paper, we consider whether the set \({\mathcal G}\) of GPAC-computable functions is closed under iteration, that is, whether for any function \(f(x)\in{\mathcal G}\) there is a function \(F(x,t)\in{\mathcal G}\) such that \(F(x,t)= f^t(x)\) for nonnegative integers \(t\). We show that \({\mathcal G}\) is not closed under iteration, but a simple extension of it is. In particular, if we relax the definition of the GPAC slightly to include unique solutions to boundary value problems, or equivalently if we allow functions \(x^k\theta(x)\) that sense inequalities in a differentiable way, the resulting class, which we call \({\mathcal G}+ \theta_k\), is closed under iteration. Furthermore, \({\mathcal G}+\theta_k\) includes all primitive recursive functions and has the additional closure property that if \(T(x)\) is in \({\mathcal G}+\theta_k\), then any function of \(x\) computable by a Turing machine in \(T(x)\) time is also.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)

References:

[1] Babakhanian, A., Exponentials in differentially algebraic extension fields, Duke Math. J., 40, 455-458 (1973) · Zbl 0264.12103
[2] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc., 21, 1-46 (1989) · Zbl 0681.03020
[3] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer-Verlag: Springer-Verlag Berlin/New York
[4] Bournez, O., Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Theoret. Comput. Sc., 210, 21-71 (1999) · Zbl 0912.68032
[5] Bowles, M. D., U. S. technological enthusiasm and the British technological skepticism in the age of the analog brain, IEEE Ann. History Comput., 18, 5-15 (1996)
[6] Branicky, M. S., Universal computation and other capabilities of hybrid and continuous dynamical systems, Theoret. Comput. Sc., 138, 67-100 (1995) · Zbl 0874.68207
[7] Grzegorczyk, A., On the definition of computable real continuous functions, Fund. Math., 44, 61-71 (1957) · Zbl 0079.24801
[8] Hale, J.; Koçak, H., Dynamics and Bifurcations (1991), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0745.58002
[9] Hayman, W. K., The growth of solutions of algebraic differential equations, Rend. Mat. Acc. Lincei, 7, 67-73 (1996) · Zbl 0877.34007
[10] Koiran, P.; Cosnard, M.; Garzon, M., Computability with low-dimensional dynamical systems, Theoret. Comput. Sc., 132, 113-128 (1994) · Zbl 0821.68053
[11] Koiran, P.; Moore, C., Closed-form analytic maps in one or two dimensions can simulate Turning machines, Theoret. Comput. Sc., 210, 217-223 (1999) · Zbl 0912.68033
[12] Lipshitz, L.; Rubel, L. A., A differentially algebraic replacement theorem, and analog computation, Proc. Amer. Math. Soc., 99, 367-372 (1987) · Zbl 0626.34012
[13] Meer, K., Real number models under various sets of operations, J. Complexity, 9, 366-372 (1993) · Zbl 0782.68048
[14] Moore, C., Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett., 64, 2354-2357 (1990) · Zbl 1050.37510
[15] Moore, C., Recursion theory on the reals and continuous-time computation, Theoret. Comput. Sc., 162, 23-44 (1996) · Zbl 0871.68027
[16] Moore, C., Dynamical recognizers: real-time language recognition by analog computers, Theoret. Comput. Sc., 201, 99-136 (1998) · Zbl 0902.68098
[17] Odifreddi, P., Classical Recursion Theory (1989), Elsevier: Elsevier Amsterdam · Zbl 0931.03057
[18] Orponen, P., A survey of continuous-time computation theory, (Du, D.-Z.; Ko, K.-I., Advances in Algorithms, Languages, and Complexity (1997), Kluwer Academic: Kluwer Academic Dordrecht), 209-224 · Zbl 0867.68047
[19] Orponen, P., On the computational power of continuous time neural networks, Proc. SOFSEM ’97, the 24th Seminar on Current Trends in Theory and Practice of Informatics. Proc. SOFSEM ’97, the 24th Seminar on Current Trends in Theory and Practice of Informatics, Lecture Notes in Computer Science (1997), Springer-Verlag: Springer-Verlag Berlin/New York, p. 86-103
[20] Ostrowski, A., Zum Hölderschen Satz über \(Γ(x)\), Math. Annal., 94, 248-251 (1925) · JFM 51.0276.06
[21] Pour-El, M. B., Abstract computability and its relation to the general purpose analog computer, Trans. Amer. Math. Soc., 199, 1-28 (1974) · Zbl 0296.02022
[22] Pour-El, M. B.; Richards, J. I., Computability in Analysis and Physics (1989), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0678.03027
[23] Rubel, L. A., Some mathematical limitations of the general-purpose analog computer, Adv. Appl. Math., 9, 22-34 (1988) · Zbl 0678.68115
[24] Rubel, L. A., Digital simulation of analog computation and Church’s thesis, J. Symbolic Logic, 54, 1011-1017 (1989) · Zbl 0683.03040
[25] Rubel, L. A., A survey of transcendentally transcendental functions, Amer. Math. Monthly, 96, 777-788 (1989) · Zbl 0719.12006
[26] Rubel, L. A., The extended analog computer, Adv. Appl. Math., 14, 39-50 (1993) · Zbl 0805.68010
[27] Shannon, C., Mathematical theory of the differential analyser, J. Math. Phys. MIT, 20, 337-354 (1941) · Zbl 0061.29410
[28] Siegelmann, H.; Sontag, E. D., Analog computation via neural networks, Theoret. Comput. Sc., 131, 331-360 (1994) · Zbl 0822.68029
[29] Siegelmann, H., Neural Networks and Analog Computation: Beyond the Turning Limit (1998), Birkhäuser: Birkhäuser Basel
[30] Siegelmann, H. T.; Fishman, S., Analog computation with dynamical systems, Physica D, 120, 235-241 (1998) · Zbl 0954.37038
[31] Thomson, W., On a instrument for calculating the integral of the product of two given functions, Proc. Royal Soc. London, 24, 266-268 (1876) · JFM 08.0176.01
[32] Vergis, A.; Steiglitz, K.; Dickinson, B., The complexity of analog computation, Math. Comput. Simulation, 28, 91-113 (1986) · Zbl 0594.68040
[33] Wang, Y.; Sontag, E. D., Algebraic differential equations and rational control systems, SIAM J. Control Optim., 30, 1126-1149 (1992) · Zbl 0762.93015
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.