Achilles and the tortoise climbing up the hyper-arithmetical hierarchy

DOI10.1016/S0304-3975(98)00096-6zbMath0912.68032OpenAlexW1991712029MaRDI QIDQ1274806

Olivier Bournez

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)00096-6

zbMATH Keywords

hybrid systemscomputabilitypiecewise constanthyper-arithmetical hierarchyderivative systems

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55)

Related Items

An analog characterization of the Grzegorczyk hierarchy ⋮ Computing with polynomial ordinary differential equations ⋮ Computability and Dynamical Systems ⋮ Computation with perturbed dynamical systems ⋮ Computability and Computational Complexity of the Evolution of Nonlinear Dynamical Systems ⋮ Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines ⋮ Iteration, inequalities, and differentiability in analog computers ⋮ Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs ⋮ Achilles and the tortoise climbing up the arithmetical hierarchy ⋮ How much can analog and hybrid systems be proved (super-)Turing ⋮ Abstract geometrical computation. III: Black holes for classical and analog computing ⋮ A new conceptual framework for analog computation ⋮ Computational bounds on polynomial differential equations ⋮ Classes of Timed Automata and the Undecidability of Universality ⋮ Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions ⋮ A theory of complexity for continuous time systems ⋮ A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• The algorithmic analysis of hybrid systems
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• Some bounds on the computational power of piecewise constant derivative systems
• A survey on real structural complexity theory
• Classical recursion theory. Vol. II
• Computing over the reals with addition and order
• On the computational power of dynamical systems and hybrid systems
• Recursion theory on the reals and continuous-time computation
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• On some relations between dynamical systems and transition systems
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Achilles and the tortoise climbing up the arithmetical hierarchy