Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines

Article type: Research Article

Authors: Graça, Daniel^{a; b; *} | Zhong, Ning^c

Affiliations: [a] Universidade do Algarve, Portugal | [b] Instituto de Telecomunicações, Portugal | [c] DMS, University of Cincinnati, OH, USA

Correspondence: [*] Corresponding author. dgraca@ualg.pt.

Abstract: In this paper, we analyze the problem of finding the minimum dimension n such that an analytic map/ordinary differential equation over Rn 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∞ ordinary differential equation on the compact sphere S2.

Keywords: Turing machines, Turing universal analytic map, Turing universal ordinary differential equation

DOI: 10.3233/COM-210381

Journal: Computability, vol. 12, no. 2, pp. 117-144, 2023