Loading...
7 results
Search Results
Now showing 1 - 7 of 7
- Computing with polynomial ordinary differential equationsPublication . Bournez, Olivier; Graça, Daniel; Pouly, AmauryIn 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 on electronic) machines of that time.Following Shannon's arguments, functions generated by the GPAC must satisfy a polynomial differential algebraic equation (DAE). As it is known that some computable functions like Euler's Gamma(x) = integral(infinity)(0) t(x-1)e(-t) dt or Riemann's Zeta function zeta(x) = Sigma(infinity)(k=0)k(1/x), do not satisfy any polynomial DAE, this argument has often been used to demonstrate in the past that the GPAC is less powerful than digital computation.It was proved in Bournez et al. (2007), 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 Bournez et al. (2007), by establishing that many natural variants of the notion of computation from this paper lead to the same computability result.Second, to go from these computability results towards considerations about (time) complexity: we explore several natural variants for measuring time space complexity of a computation.Quite 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 actually be used as a kind of programming model, and that there is a rather nice and robust notion of ordinary differential equation (ODE) programming. (C) 2016 Published by Elsevier Inc.
- Solving analytic differential equations in polynomial time over unbounded domainsPublication . Bournez, Olivier; Graça, Daniel; Pouly, AmauryIn this paper we consider the computational complexity of solving initial-value problems de ned with analytic ordinary diferential equations (ODEs) over unbounded domains of Rn and Cn, under the Computable Analysis setting. We show that the solution can be computed in polynomial time over its maximal interval of de nition, provided it satis es a very generous bound on its growth, and that the function admits an analytic extension to the complex plane.
- A continuous characterization of PSPACE using polynomial ordinary differential equationsPublication . Bournez, Olivier; Gozzi, Riccardo; Graça, Daniel; Pouly, AmauryIn this paper we provide a characterization of the complexity class PSPACE by using a purely continuous model defined with polynomial ordinary differential equations.
- Computation with perturbed dynamical systemsPublication . Bournez, Olivier; Graca, Daniel S.; Hainry, EmmanuelThis paper analyzes the computational power of dynamical systems robust to infinitesimal perturbations. Previous work on the subject has delved on very specific types of systems. Here we obtain results for broader classes of dynamical systems (including those systems defined by Lipschitz/analytic functions). In particular we show that systems robust to infinitesimal perturbations only recognize recursive languages. We also show the converse direction: every recursive language can be robustly recognized by a computable system. By other words we show that robustness is equivalent to decidability. (C) 2013 Elsevier Inc. All rights reserved.
- The general purpose analog computer and computable analysis are two equivalent paradigms of analog computationPublication . Bournez, Olivier; Campagnolo, Manuel; Graça, Daniel; Hainry, EmmanuelIn this paper we revisit one of the rst models of analog computation, Shannon's General Purpose Analog Computer (GPAC). The GPAC has often been argued to be weaker than computable analysis. As main contribution, we show that if we change the notion of GPACcomputability in a natural way, we compute exactly all real computable functions (in the sense of computable analysis). Moreover, since GPACs are equivalent to systems of polynomial di erential equations then we show that all real computable functions can be de ned by such models.
- Robust computations with dynamical systemsPublication . Bournez, Olivier; Graça, Daniel; Hainry, EmmanuelIn this paper we discuss the computational power of Lipschitz dynamical systems which are robust to in nitesimal perturbations. Whereas the study in [1] was done only for not-so-natural systems from a classical mathematical point of view (discontinuous di erential equation systems, discontinuous piecewise a ne maps, or perturbed Turing machines), we prove that the results presented there can be generalized to Lipschitz and computable dynamical systems. In other words, we prove that the perturbed reachability problem (i.e. the reachability problem for systems which are subjected to in nitesimal perturbations) is co-recursively enumerable for this kind of systems. Using this result we show that if robustness to in nitesimal perturbations is also required, the reachability problem becomes decidable. This result can be interpreted in the following manner: undecidability of veri cation doesn't hold for Lipschitz, computable and robust systems. We also show that the perturbed reachability problem is co-r.e. complete even for C1-systems.
- Polynomial differential equations compute all real computable functions on computable compact intervalsPublication . Bournez, Olivier; Campagnolo, Manuel; Graça, Daniel; Hainry, EmmanuelIn the last decade, the eld of analog computation has experienced renewed interest. In particular, there have been several attempts to un- derstand which relations exist between the many models of analog com- putation. Unfortunately, most models are not equivalent. It is known that Euler's Gamma function is computable according to computable analysis, while it cannot be generated by Shannon's General Purpose Analog Computer (GPAC). This example has often been used to argue that the GPAC is less powerful than digital computation. However, as we will demonstrate, when computability with GPACs is not restricted to real-time generation of functions, we obtain two equiva- lent models of analog computation. Using this approach, it has been shown recently that the Gamma func- tion becomes computable by a GPAC [1]. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial di erential equations then we show that all real computable functions over compact intervals can be de ned by such models.