Loading...
6 results
Search Results
Now showing 1 - 6 of 6
- Computability with polynomial differential equationsPublication . Graça, Daniel; Campagnolo, Manuel; Buescu, JorgeIn this paper, we show that there are Initial Value Problems de ned with polynomial ordinary di erential equations that can simulate univer- sal Turing machines in the presence of bounded noise. The polynomial ODE de ning the IVP is explicitly obtained and the simulation is per- formed in real time.
- Computational bounds on polynomial differential equationsPublication . Graça, Daniel; Buescu, Jorge; Campagnolo, ManuelIn this paper we study from a computational perspective some prop-erties of the solutions of polynomial ordinary di erential equations. We consider elementary (in the sense of Analysis) discrete-time dynam-ical systems satisfying certain criteria of robustness. We show that those systems can be simulated with elementary and robust continuous-time dynamical systems which can be expanded into fully polynomial ordinary diferential equations with coe cients in Q[ ]. This sets a computational lower bound on polynomial ODEs since the former class is large enough to include the dynamics of arbitrary Turing machines. We also apply the previous methods to show that the problem of de-termining whether the maximal interval of defnition of an initial-value problem defned with polynomial ODEs is bounded or not is in general undecidable, even if the parameters of the system are computable and comparable and if the degree of the corresponding polynomial is at most 56. Combined with earlier results on the computability of solutions of poly-nomial ODEs, one can conclude that there is from a computational point of view a close connection between these systems and Turing machines.
- 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.
- Boundedness of the domain of definition is undecidable for polynomial odesPublication . Graça, Daniel; Buescu, Jorge; Campagnolo, ManuelConsider the initial-value problem with computable parameters dx dt = p(t, x) x(t0) = x0, where p : Rn+1 ! Rn is a vector of polynomials and (t0, x0) 2 Rn+1. We show that the problem of determining whether the maximal interval of definition of this initial-value problem is bounded or not is in general undecidable.
- Robust simulations of Turing machines with analytic maps and flowsPublication . Graça, Daniel; Campagnolo, Manuel; Buescu, JorgeIn this paper, we show that closed-form analytic maps and ows can simulate Turing machines in an error-robust manner. The maps and ODEs de ning the ows are explicitly obtained and the simulation is performed in real time.
- 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.