Browsing by Author "Zhong, Ning"
Now showing 1 - 10 of 12
Results Per Page
Sort Options
- Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machinesPublication . Graça, Daniel; Zhong, NingIn this paper, we analyze the problem of finding the minimum dimension n such that an analytic map/ordinary differential equation over R n can simulate a Turing machine in a way that is robust to perturbations. We show that one-dimensional analytic maps are sufficient to robustly simulate Turing machines; but the minimum dimension for the analytic ordinary differential equations to robustly simulate Turing machines is two, under some reasonable assumptions. We also show that any Turing machine can be simulated by a two-dimensional C ∞ ordinary differential equation on the compact sphere S 2.
- 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.
- Computability in planar dynamical systemsPublication . Graça, Daniel; Zhong, NingIn this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time planar dynamical systems. We consider C1 systems and show that stability is in general necessary (but may not be sufficient) to attain computability. In particular, we show that (a) the problem of determining the number of attractors in a given compact set is in general undecidable, even for analytic systems and (b) the attractors are semi-computable for stable systems. We also show that the basins of attraction are semi-computable if and only if the system is stable.
- Computability of differential equationsPublication . Graça, Daniel; Zhong, NingIn this chapter, we provide a survey of results concerning the computability and computational complexity of differential equations. In particular, we study the conditions which ensure computability of the solution to an initial value problem for an ordinary differential equation (ODE) and analyze the computational complexity of a computable solution. We also present computability results concerning the asymptotic behaviors of ODEs as well as several classically important partial differential equations.
- Computability of limit sets for two-dimensional flowsPublication . Graça, Daniel; Zhong, NingA classical theorem of Peixoto qualitatively characterizes, on the two-dimensional unit ball, the limit sets of structurally stable flows defined by ordinary differential equations. Peixoto's density theorem further shows that such flows are typical in the sense that structurally stable systems form an open dense set in the space of all continuously differentiable flows. In this note, we discuss the problem of explicitly finding the limit sets of structurally stable planar flows.
- Computability of ordinary differential equationsPublication . Graça, Daniel; Zhong, NingIn this paper we provide a brief review of several results about the computability of initial-value problems (IVPs) defined with ordinary differential equations (ODEs). We will consider a variety of settings and analyze how the computability of the IVP will be affected. Computational complexity results will also be presented, as well as computable versions of some classical theorems about the asymptotic behavior of ODEs.
- 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.
- Computing domains of attraction for planar dynamicsPublication . Graça, Daniel; Zhong, NingIn this note we investigate the problem of computing the domain of attraction of a ow on R2 for a given attractor. We consider an operator that takes two inputs, the description of the ow and a cover of the attractors, and outputs the domain of attraction for the given attractor. We show that: (i) if we consider only (structurally) stable systems, the operator is (strictly semi-)computable; (ii) if we allow all systems de ned by C1-functions, the operator is not (semi-)computable. We also address the problem of computing limit cycles on these systems.
- Computing the exact number of periodic orbits for planar flowsPublication . Graça, Daniel; Zhong, NingIn this paper, we consider the problem of determining the exact number of periodic orbits for polynomial planar flows. This problem is a variant of Hilbert's 16th problem. Using a natural definition of computability, we show that the problem is noncomputable on the one hand and, on the other hand, computable uniformly on the set of all structurally stable systems defined on the unit disk. We also prove that there is a family of polynomial planar systems which does not have a computable sharp upper bound on the number of its periodic orbits.
- The connection between computability of a nonlinear problem and its linearization: the Hartman-Grobman theorem revisitedPublication . Graça, Daniel; Zhong, Ning; Dumas, H. S.As one of the seven open problems in the addendum to their 1989 book Computability in Analysis and Physics Pour-El and Richards (1989)[17], Pour-El and Richards asked, "What is the connection between the computability of the original nonlinear operator and the linear operator which results from it?" Yet at present, systematic studies of the issues raised by this question seem to be missing from the literature. In this paper, we study one problem in this direction: the Hartman-Grobman linearization theorem for ordinary differential equations (ODEs). We prove, roughly speaking, that near a hyperbolic equilibrium point x(0) of a nonlinear ODE (x) over dot = f(x), there is a computable homeomorphism H such that H circle phi = L circle H, where phi is the solution to the ODE and L is the solution to its linearization (x) over dot = Df (x(0)) x. (C) 2012 Elsevier B.V. All rights reserved.