Loading...
7 results
Search Results
Now showing 1 - 7 of 7
- 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.
- The ordinary differential equation defined by a computable function whose maximal interval of existence is non-computablePublication . Graça, Daniel; Zhong, Ning; Buescu, JorgeLet (®, ¯) ½ R denote the maximal interval of existence of solution for the initial-value problem ½ dx dt = f(t, x), f : E ! Rm,E is an open subset of Rm+1 x(t0) = x0, with (t0, x0) 2 E. We show that (®, ¯) is r.e. (recursively enumerable) open and the solution x(t) defined on (®, ¯) is computable, provided that (a) f is computable and effectively locally Lipschitz, and (b) (t0, x0) is a computable point. We also prove that this result is the best in the sense that, for some initial-value problems satisfying (a) and (b), their maximal intervals of existence are non-recursive.
- Computability, noncomputability and undecidability of maximal intervals of IVPsPublication . Graça, Daniel; Zhong, Ning; Buescu, JorgeLet (α, β) ⊆ R denote the maximal interval of existence of solution for the initial-value problem dx dt = f(t, x) x(t0) = x0, where E is an open subset of Rm+1, f is continuous in E and (t0, x0) ∈ E. We show that, under the natural definition of computability from the point of view of applications, there exist initial-value problems with computable f and (t0, x0) whose maximal interval of existence (α, β) is noncomputable. The fact that f may be taken to be analytic shows that this is not a lack of regularity phenomenon. Moreover, we get upper bounds for the “degree of noncomputability” by showing that (α, β) is r.e. (recursively enumerable) open under very mild hypotheses. We also show that the problem of determining whether the maximal interval is bounded or unbounded is in general undecidable.
- Computability and dynamical systemsPublication . Buescu, Jorge; Graça, Daniel; Zhong, NingIn this paper we explore results that establish a link between dynamical systems and computability theory (not numerical analysis). In the last few decades, computers have increasingly been used as simulation tools for gaining insight into dynamical behavior. However, due to the presence of errors inherent in such numerical simulations, with few exceptions, computers have not been used for the nobler task of proving mathematical results. Nevertheless, there have been some recent developments in the latter direction. Here we introduce some of the ideas and techniques used so far, and suggest some lines of research for further work on this fascinating topic.
- 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.
- 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.