Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
From MaRDI portal
Publication:1274815
DOI10.1016/S0304-3975(98)00117-0zbMath0912.68033OpenAlexW1991903325MaRDI QIDQ1274815
Pascal Koiran, Moore, Cristopher
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00117-0
Related Items
Computability and Dynamical Systems, Computation with perturbed dynamical systems, Computability and Computational Complexity of the Evolution of Nonlinear Dynamical Systems, Dynamical recognizers: real-time language recognition by analog computers, An RNA-based theory of natural universal computation, Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines, Low dimensional hybrid systems -- decidable, undecidable, don't know, An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable, Computation in gene networks, SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY, On undecidability bounds for matrix decision problems, Iteration, inequalities, and differentiability in analog computers, A survey of computational complexity results in systems and control, Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs, Physical constraints on hypercomputation, Computability with polynomial differential equations, The P\(\neq\) NP conjecture in the context of real and complex analysis, Real recursive functions and their hierarchy, A Universal Ordinary Differential Equation, Neo-classical theory of competition or Adam Smith's hand as mathematized ideology, Analog computation beyond the Turing limit, Average-Case Completeness in Tag Systems, What is a universal computing machine?, Instability, complexity, and evolution, The futility of utility: how market dynamics marginalize Adam Smith, A theory of complexity for continuous time systems, A Survey on Analog Models of Computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Busy beaver competition and Collatz-like problems
- Functional equations associated with congruential functions
- Computability and complexity of ray tracing
- Analog computation via neural networks
- Computability with low-dimensional dynamical systems
- Small universal Turing machines
- Reachability analysis of dynamical systems having piecewise-constant derivatives
- The 3x + 1 Problem and Its Generalizations
- Generalized shifts: unpredictability and undecidability in dynamical systems
