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

arXiv: https://arxiv.org/abs/2109.15073 · HTML: https://mlsanity.com/paper/2109.15073/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2021.

## Built on by (most cited first, 1 of 1)

- [Computational Dynamical Systems](https://mlsanity.com/paper/2409.12179/) (2024)

## Abstract (arXiv)

In this paper, we analyze the problem of finding the minimum dimension n such that a closed-form analytic map/ordinary differential equation can simulate a Turing machine over ℝn in a way that is robust to perturbations. We show that one-dimensional closed-form analytic maps are sufficient to robustly simulate Turing machines; but the minimum dimension for the closed-form 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 mathbbS2.