RECORD
Computing with Polynomial Ordinary Differential Equations
Computational Complexity · Submitted 21 Jan 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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)=\int_{0}^{\infty}t^{x-1}e^{-t}dt$ or Riemann's Zeta function $\zeta(x)=\sum_{k=0}^\infty \frac1{k^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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | Following Shannon's arguments, functions generated by GPACs must be differentially algebraic. | background 1.00 | 0.05 | 0.02 | asserted 0.96 |
| s2 | As it is known that some computable functions like Euler's $\Gamma(x)=\int_{0}^{\infty}t^{x-1}e^{-t}dt$ or Riemann's Zeta function $\zeta(x)=\sum_{k=0}^\infty \frac1{k^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. | background 1.00 | 0.03 | 0.02 | asserted 0.98 |
| s3 | 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. | background 0.99 | 0.06 | 0.19 | asserted 1.00 |
| s4 | 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. | contribution 0.99 | 0.46 | 0.06 | asserted 0.80 |
| s5 | Second, to go considerations about (time) complexity, we explore several natural variants for measuring time/space complexity of a computation. | contribution 0.94 | 0.67 | 0.03 | asserted 0.72 |
| s6 | 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. | result 0.99 | 0.94 | 0.26 | asserted 1.00 |
| s7 | 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. | interpretation 0.83 | 0.83 | 0.48 | hedged possibility 0.90 |
| s8 | 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. | interpretation 0.82 | 0.92 | 0.11 | asserted 0.89 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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)=\int_{0}^{\infty}t^{x-1}e^{-t}dt$ or Riemann's Zeta function $\zeta(x)=\sum_{k=0}^\infty \frac1{k^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.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 2 sentences without a confident label
Cites as background 1 paper
-
A much more complete and detailed analysis of this class, with all the proofs, can be found in [ref] but we give a short overview below.
On the Functions Generated by the General Purpose Analog Computer · The PIVP Class · 0.89
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.