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

DOI10.3233/com-210381arXiv2109.15073OpenAlexW3203009394WikidataQ115222737 ScholiaQ115222737MaRDI QIDQ6048001

Daniel Silva Graça, Ning Zhong

Publication date: 13 September 2023

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.15073

zbMATH Keywords

Turing machinesTuring universal analytic mapTuring universal ordinary differential equation

Mathematics Subject Classification ID

Computability and recursion theory (03Dxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computation with perturbed dynamical systems
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• Achilles and the tortoise climbing up the hyper-arithmetical hierarchy
• Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
• Classical recursion theory. Vol. II
• Computability with low-dimensional dynamical systems
• A family of universal recurrent networks
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Higher chain formula proved by combinatorics
• Computability with polynomial differential equations
• Computational Complexity of Smooth Differential Equations
• Kleene's Amazing Second Recursion Theorem
• Computability, noncomputability and undecidability of maximal intervals of IVPs
• Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
• A Multivariate Faa di Bruno Formula with Applications
• Effective Computability of Solutions of Ordinary Differential Equations The Thousand Monkeys Approach
• A Survey on Analog Models of Computation
• Turing Universality of the Incompressible Euler Equations and a Conjecture of Moore
• Generalized shifts: unpredictability and undecidability in dynamical systems
• On the complexity of solving initial value problems
• Unconventional Computation
• Iteration, inequalities, and differentiability in analog computers

This page was built for publication: Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines