Computing with polynomial ordinary differential equations

DOI10.1016/J.JCO.2016.05.002MaRDI QIDQ306694zbMATH OpenOpenAlexFDO

Authors Olivier Bournez, Amaury Pouly, Daniel Graça

Publication date 1 September 2016

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

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

zbMATH Keywords

analog computationcontinuous-time computationsgeneral-purpose analog computerreal computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computation over the reals, computable analysis (03D78) General theory for ordinary differential equations (34A99) Classical models of computation (Turing machines, etc.) (68Q04)

Abstract: In 1941, Claude Shannon introduced the General Purpose Analog Computer(GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. Following Shannon's arguments, functions generated by GPACs must be differentially algebraic. As it is known that some computable functions like Euler's $Gamma(x)=in{t}_0^{infty}{t}^{x-1}{e}^{-t}dt$ or Riemann's Zeta function $zeta(x)=su{m}_{k=0}^{i}nftyfrac1k^x$ are not differentially algebraic, this argument has been often used to demonstrate in the past that the GPAC is less powerful than digital computation. It was proved in JOC2007, that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines. Our purpose is first to discuss the robustness of the notion of computation involved in JOC2007, by establishing that natural variants of the notion of computation from this paper leads to the same computability result. Second, to go considerations about (time) complexity, we explore several natural variants for measuring time/space complexity of a computation. Rather surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations. Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can be used as a kind of programming model, and that there is a rather nice and robust notion of ODE programming.

Recommendations

• Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations
• Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Theory and Applications of Models of Computation
• On the functions generated by the general purpose analog computer

Cites work

• scientific article; zbMATH DE number 1189126 (Why is no real title available?)
• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 166937 (Why is no real title available?)
• scientific article; zbMATH DE number 177824 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1869997 (Why is no real title available?)
• scientific article; zbMATH DE number 5224002 (Why is no real title available?)
• Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
• Achilles and the tortoise climbing up the hyper-arithmetical hierarchy
• Analog computers and recursive functions over the reals.
• Building Infinite Machines
• Computational bounds on polynomial differential equations
• Mathematical Theory of the Differential Analyzer
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Recursion theory on the reals and continuous-time computation
• Some bounds on the computational power of piecewise constant derivative systems
• Some recent developments on Shannon's General Purpose Analog Computer
• The differential analyzer. A new machine for solving differential equations

Cited in

(9)

• Some recent developments on Shannon's General Purpose Analog Computer
• Programming with ordinary differential equations: some first steps towards a programming language
• Characterizing time computational complexity classes with polynomial differential equations
• A universal ordinary differential equation
• Computational bounds on polynomial differential equations
• On the functions generated by the general purpose analog computer
• Computability with polynomial differential equations
• Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations
• Approximability in the GPAC

This page was built for publication: Computing with polynomial ordinary differential equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306694)