Polynomial differential equations compute all real computable functions on computable compact intervals

DOI10.1016/j.jco.2006.12.005zbMath1125.68059OpenAlexW2108904240WikidataQ56018224 ScholiaQ56018224MaRDI QIDQ2371306

Emmanuel Hainry, Olivier Bournez, Campagnolo, Manuel Lameiras, Daniel Silva Graça

Publication date: 4 July 2007

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

Full work available at URL: http://hdl.handle.net/10400.1/1011

zbMATH Keywords

analog computationdifferential equationscomputable analysisgeneral-purpose analog computerChurch-Turing thesis

Mathematics Subject Classification ID

Related Items (22)

Characterizing time computational complexity classes with polynomial differential equations ⋮ Constructibility of the universal wave function ⋮ Computing with polynomial ordinary differential equations ⋮ Compiling elementary mathematical functions into finite chemical reaction networks via a polynomialization algorithm for ODEs ⋮ Computability and Dynamical Systems ⋮ Computability of analog networks ⋮ Constructing general partial differential equations using polynomial and neural networks ⋮ On the functions generated by the general purpose analog computer ⋮ Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines ⋮ Computing with chemical reaction networks: a tutorial ⋮ A continuous characterization of PSPACE using polynomial ordinary differential equations ⋮ The elementary computable functions over the real numbers: applying two new techniques ⋮ Distributed Learning of Wardrop Equilibria ⋮ Characterizing Computable Analysis with Differential Equations ⋮ Abstract geometrical computation. V: Embedding computable analysis ⋮ A survey of recursive analysis and Moore's notion of real computation ⋮ Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer ⋮ A characterization of computable analysis on unbounded domains using differential equations ⋮ Uniqueness in Planar Endogenous Business Cycle Theories ⋮ A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations ⋮ Programming with ordinary differential equations: some first steps towards a programming language ⋮ A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Real recursive functions and their hierarchy
• Recursion theory on the reals and continuous-time computation
• Analog computers and recursive functions over the reals.
• The differential analyzer. A new machine for solving differential equations
• Computability with polynomial differential equations
• A Differentially Algebraic Replacement Theorem, and Analog Computability
• Some recent developments on Shannon's General Purpose Analog Computer
• On the definitions of computable real continuous functions
• Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• New Computational Paradigms
• A Survey of Transcendentally Transcendental Functions
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Mathematical Theory of the Differential Analyzer

This page was built for publication: Polynomial differential equations compute all real computable functions on computable compact intervals