Undecidable event detection problems for ODEs of dimension one and two. (English) Zbl 0878.68062

Summary: The ability of dynamical systems of various kinds to simulate Turing machines and thus manifest a universal computation power (and beyond) has gathered a lot of interest lately. A similar line of investigation for ordinary differential equations was started by the author [J. Inf. Process. Cybern. 29, No. 2, 101-113 (1993; Zbl 0771.65035)] and continued in [Event detection and nonrecursive hierarchies, Lect. Notes Comput. Sci. 812, 358-371 (1994), Decidability and complexity of event detection problems for ODEs (to appear in complexity)]. In this context the minimum dimension required for universal computation is of interest. The dynamical systems in C. Moore [Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett. 64, 2354-2357 (1990) and Nonlinearity 4, No. 2, 199-230 (1991; Zbl 0725.58013)] are of small dimension and the topic of P. Koiran, M. Cosnard and M. Garzon [Theor. Comput. Sci. 132, No. 1-2, 113-128 (1994; Zbl 0821.68053)] is to find the smallest dimension for certain types of dynamical systems. The results in this paper show that for ODEs dimension two can be reached and, allowing somewhat complicated events, even dimension one.


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


Turing machines
Full Text: DOI EuDML


[1] 1. C. H. BENNETT, Logical Reversibility of Cornputation. IBM J. Res. Dev. 17, 1973, pp. 525-523. Zbl0267.68024 MR449020 · Zbl 0267.68024 · doi:10.1147/rd.176.0525
[2] 2. P. HARTMAN, Ordinary Differential Equations. Birkhäuser, 1982. MR658490 · Zbl 0476.34002
[3] 3. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[4] 4. P. KOIRAN, P. COSNARD and M. GARZON, Computability with Low-Dimensional Dynamical Systems. Theoret Comput. Sci. 132, 1994, pp. 113-128. Zbl0821.68053 MR1290538 · Zbl 0821.68053 · doi:10.1016/0304-3975(94)90229-1
[5] 5. C. MOORE, Unpredictability and Undecidability in Dynamical Systems. Phys. Rev. Lett. 64, 1990, pp. 2354-2357. Zbl1050.37510 MR1050259 · Zbl 1050.37510 · doi:10.1103/PhysRevLett.64.2354
[6] 6. C. MOORE, Generalized Shifts: Unpredictability and Undecidability in Dynamical Systems. Nonlinearity 4, 1991, pp. 199-230. Zbl0725.58013 MR1107005 · Zbl 0725.58013 · doi:10.1088/0951-7715/4/2/002
[7] 7. M. Y. LECERF, Machines de Turing réversibles. Récursive insolubilité en n \in N de l’équation u = \theta nu, où \theta est un ”isomorphisme de codes”. Comptes Rendus 257, 1963, pp. 2597-2600. Zbl0192.06901 MR175790 · Zbl 0192.06901
[8] 8. M. B. POUR-EL and I. RICHARDS, A Computable Ordinary Differential Equation which Possesses No Computable Solutions. Ann. Math. Logic 17, 1979, pp. 61-90. Zbl0424.68028 MR552416 · Zbl 0424.68028 · doi:10.1016/0003-4843(79)90021-4
[9] 9. M. B. POUR-EL and I. RICHARDS, Computability in Analysis and Physics. Springer-Verlag, 1989. Zbl0678.03027 MR1005942 · Zbl 0678.03027
[10] 10. E. O. ROXIN, Ordinary Differential Equations. Wadsworth, 1972. Zbl0255.34001 MR463536 · Zbl 0255.34001
[11] 11. K. RUOHONEN, Undecidability of Event Detection for ODEs. J. Inform. Proc. Cybern. EIK, 29, 1993, pp. 101-113. Zbl0771.65035 · Zbl 0771.65035
[12] 12. K. RUOHONEN, Event Detection and Nonrecursive Hierarchies. Results and Trends in Theoretical Computer Science (J. Karhumäki, H. Maurer and G. Rozenberg, Eds.). Lecture Notes in Computer Science 812. Springer-Verlag, 1994, pp. 358-371. MR1286976
[13] 13. K. RUOHONEN, Decidability and Complexity of Event Detection Problems for ODEs. To appear in Complexity. MR1473602 · Zbl 0878.68062
[14] 14. K. RUOHONEN, Reversible Machines and Post’s Correspondence Problem for Biprefix Morphisms. Elektron. Inf.verarb. Kybern. EIK 21, 1985, pp. 579-595. Zbl0604.68057 MR825861 · Zbl 0604.68057
[15] 15. L. F. SHAMPINE, I. GLADWELL and R. W. BRANKIN, Reliable Solution of Special Event Location Problems for ODEs. ACM Trans. Math. Software 17, 1991, pp. 11-25. Zbl0900.65208 MR1103624 · Zbl 0900.65208 · doi:10.1145/103147.103149
[16] 16. H. T. STEGELMANN, Computation Beyond the Turing Limit. Science 268, 1995, pp. 545-548.
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.