Sage Journals: Discover world-class research

Abstract

In this paper, we analyze the problem of finding the minimum dimension n such that an analytic map/ordinary differential equation over $R^{n}$ can simulate a Turing machine in a way that is robust to perturbations. We show that one-dimensional analytic maps are sufficient to robustly simulate Turing machines; but the minimum dimension for the analytic ordinary differential equations to robustly simulate Turing machines is two, under some reasonable assumptions. We also show that any Turing machine can be simulated by a two-dimensional $C^{\infty}$ ordinary differential equation on the compact sphere $S^{2}$ .

Keywords

Turing machines Turing universal analytic map Turing universal ordinary differential equation

Get full access to this article

View all access options for this article.

References

Asarin and

Bouajjani , Perturbed Turing machines and hybrid systems, in: Proc. 16th Annual IEEE Symposium on Logic in Computer Science, 2001, pp. 269–278.

Bournez , Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Theoretical Computer Science 210(1) (1999), 21–71. doi:10.1016/S0304-3975(98)00096-6.

Bournez and

M.L.

Campagnolo , A survey on continuous time computations, in: New Computational Paradigms. Changing Conceptions of What Is Computable,

S.B.

Cooper ,

Löwe and

Sorbi , eds, Springer, New York, 2008, pp. 383–423.

Bournez ,

M.L.

Campagnolo ,

D.S.

Graça and

Hainry , Polynomial differential equations compute all real computable functions on computable compact intervals, Journal of Complexity 23(3) (2007), 317–335. doi:10.1016/j.jco.2006.12.005.

Bournez ,

D.S.

Graça and

Hainry , Computation with perturbed dynamical systems, Journal of Computer and System Sciences 79(5) (2013), 714–724. doi:10.1016/j.jcss.2013.01.025.

Bournez ,

D.S.

Graça and

Pouly , On the complexity of solving initial value problems, in: Proc. 37h International Symposium on Symbolic and Algebraic Computation (ISSAC 2012), 2012, arXiv:1202.4407.

Bournez ,

D.S.

Graça and

Pouly , Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length, Journal of the ACM 64(6) (2017), 38:1–38:76. doi:10.1145/3127496.

Bournez and

Pouly , A survey on analog models of computation, in: Handbook of Computability and Complexity in Analysis, Springer International Publishing, Cham, 2021, pp. 173–226. doi:10.1007/978-3-030-59234-9_6.

M.S.

Branicky , Universal computation and other capabilities of hybrid and continuous dynamical systems, Theoretical Computer Science 138(1) (1995), 67–100. doi:10.1016/0304-3975(94)00147-B.

10.

Brattka ,

Hertling and

Weihrauch , A tutorial on computable analysis, in: New Computational Paradigms: Changing Conceptions of What Is Computable,

S.B.

Cooper ,

Löwe and

Sorbi , eds, Springer, 2008, pp. 425–491. doi:10.1007/978-0-387-68546-5_18.

11.

Braverman , Computational complexity of Euclidean sets: Hyperbolic Julia sets are poly-time computable, in: Proc. 6th Workshop on Computability and Complexity in Analysis (CCA 2004),

Brattka ,

Staiger and

Weihrauch , eds, Electronic Notes in Theoretical Computer Science, Vol. 120, Elsevier, 2005, pp. 17–30.

12.

M.L.

Campagnolo , Computational Complexity of Real Valued Recursive Functions and Analog Circuits, PhD thesis, Instituto Superior Técnico/Universidade Técnica de Lisboa, 2002.

13.

M.L.

Campagnolo ,

Moore and

J.F.

Costa , Iteration, inequalities, and differentiability in analog computers, Journal of Complexity 16(4) (2000), 642–660. doi:10.1006/jcom.2000.0559.

14.

Cardona ,

Miranda and

Peralta-Salas , Turing Universality of the Incompressible Euler Equations and a Conjecture of Moore, International Mathematics Research Notices (2021), rnab233. doi:10.1093/imrn/rnab233.

15.

Cardona ,

Miranda ,

Peralta-Salas and

Presas , Constructing Turing complete Euler flows in dimension 3, Proceedings of the National Academy of Sciences 118(19) (2021). doi:10.1073/pnas.2026818118.

16.

Collins and

D.S.

Graça , Effective computability of solutions of ordinary differential equations the thousand monkeys approach, in: Proc. 5th International Conference on Computability and Complexity in Analysis (CCA 2008),

Brattka ,

Dillhage ,

Grubba and

Klutsch , eds, Electronic Notes in Theoretical Computer Science, Vol. 221, Elsevier, 2008, pp. 103–114.

17.

G.M.

Constantine and

T.H.

Savits , A multivariate Faa di Bruno formula with applications, Trans. Amer. Math. Soc. 348(2) (1996). doi:10.1090/S0002-9947-96-01501-2.

18.

D.S.

Graça ,

M.L.

Campagnolo and

Buescu , Computability with polynomial differential equations, Advances in Applied Mathematics 40(3) (2008), 330–349. doi:10.1016/j.aam.2007.02.003.

19.

D.S.

Graça ,

Zhong and

Buescu , Computability, noncomputability and undecidability of maximal intervals of IVPs, Transactions of the American Mathematical Society 361(6) (2009), 2913–2927. doi:10.1090/S0002-9947-09-04929-0.

20.

Kawamura , Lipschitz continuous ordinary differential equations are polynomial-space complete, Computational Complexity 19(2) (2010), 305–332. doi:10.1007/s00037-010-0286-0.

21.

Kawamura ,

Ota ,

Rösnick and

Ziegler , Computational complexity of smooth differential equations, Logical Methods in Computer Science 10(1:6) (2014), 1–15.

22.

K.-I.

Ko , Complexity Theory of Real Functions, Birkhäuser, 1991.

23.

Koiran , A family of universal recurrent networks, Theoretical Computer Science 168(2) (1996), 473–480. doi:10.1016/S0304-3975(96)00088-6.

24.

Koiran ,

Cosnard and

Garzon , Computability with low-dimensional dynamical systems, Theoretical Computer Science 132 (1994), 113–128. doi:10.1016/0304-3975(94)90229-1.

25.

Koiran and

Moore , Closed-form analytic maps in one and two dimensions can simulate universal Turing machines, Theoretical Computer Science 210(1) (1999), 217–223. doi:10.1016/S0304-3975(98)00117-0.

26.

Kurganskyy and

Potapov , Computation in one-dimensional piecewise maps and planar pseudo-billiard systems, in: Proc. 4th International Conference on Unconventional Computation (UC 2005), Lecture Notes in Computer Science, Vol. 3699, Springer, 2005, pp. 169–175. doi:10.1007/11560319_16.

27.

T.-W.

Ma , Higher chain formula proved by combinatorics, The Electronic Journal of Combinatorics 16(1) (2009).

28.

Maass and

Orponen , On the effect of analog noise in discrete-time analog computations, Neural Computation 10(5) (1998), 1071–1095. doi:10.1162/089976698300017359.

29.

Matiyasevich , Hilbert’s 10th Problem, The MIT Press, 1993.

30.

Moore , Generalized shifts: Unpredictability and undecidability in dynamical systems, Nonlinearity 4(2) (1991), 199–230. doi:10.1088/0951-7715/4/2/002.

31.

Moschovakis , Kleene’s amazing second recursion theorem, The Bulletin of Symbolic Logic 16 (2010), 189–239. doi:10.2178/bsl/1286889124.

32.

Odifreddi , Classical Recursion Theory, Vol. 1, Elsevier, 1989.

33.

Sipser , Introduction to the Theory of Computation, 3rd edn, Cengage Learning, 2012.

34.

A.M.

Turing , On computable numbers, with an application to the entscheidungsproblem, Proceedings of the London Mathematical Society s2–42(1) (1937), 230–265. doi:10.1112/plms/s2-42.1.230.