An analog characterization of the Grzegorczyk hierarchy

DOI10.1006/jcom.2002.0655zbMath1030.68047OpenAlexW1965850345WikidataQ56532250 ScholiaQ56532250MaRDI QIDQ1872639

Moore, Cristopher, Campagnolo, Manuel Lameiras, Costa, José Félix

Publication date: 14 May 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.2002.0655

zbMATH Keywords

analog computationdynamical systemsdifferential equationselementary functionsrecursion theoryprimitive recursive functionsGrzegorczyk hierarchysubrecursive functions

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (21)

Characterizing time computational complexity classes with polynomial differential equations ⋮ A note on discreteness and virtuality in analog computing ⋮ Computability of analog networks ⋮ A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations ⋮ Analog computers and recursive functions over the reals. ⋮ The elementary computable functions over the real numbers: applying two new techniques ⋮ Continuous-time computation with restricted integration capabilities ⋮ Characterizing Computable Analysis with Differential Equations ⋮ The Methods of Approximation and Lifting in Real Computation ⋮ Computability with polynomial differential equations ⋮ A survey of recursive analysis and Moore's notion of real computation ⋮ The P\(\neq\) NP conjecture in the context of real and complex analysis ⋮ Real recursive functions and their hierarchy ⋮ Analog computation beyond the Turing limit ⋮ A characterization of computable analysis on unbounded domains using differential equations ⋮ Computability on reals, infinite limits and differential equations ⋮ A new conceptual framework for analog computation ⋮ Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations ⋮ A foundation for real recursive function theory ⋮ Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions ⋮ A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal computation and other capabilities of hybrid and continuous dynamical systems
• The complexity of analog computation
• Dynamical recognizers: real-time language recognition by analog computers
• Achilles and the tortoise climbing up the hyper-arithmetical hierarchy
• Classical recursion theory. Vol. II
• Real number models under various sets of operations
• Recursion theory on the reals and continuous-time computation
• Analog computation with dynamical systems
• A Differentially Algebraic Replacement Theorem, and Analog Computability
• Computable functionals
• On the definitions of computable real continuous functions
• Matrix Analysis
• Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
• Unpredictability and undecidability in dynamical systems
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Mathematical Theory of the Differential Analyzer
• Iteration, inequalities, and differentiability in analog computers

This page was built for publication: An analog characterization of the Grzegorczyk hierarchy