Untitled

Funder

Organizational Unit

Publications

Computability and dynamical systems: a perspective

Publication . Graça, Daniel

In this paper we look at dynamical systems from a computability perspective. We survey some topics and themes of research for dynamical systems and then see how they can be fitted in a computational framework. We will recall some selected results, and enounce problems that might lay possible routes for further research.

2008Conference object

Open Access

Computability, noncomputability and undecidability of maximal intervals of IVPs

Publication . Graça, Daniel; Zhong, Ning; Buescu, Jorge

Let (α, β) ⊆ 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.

2009Journal article

Open Access

Computability with polynomial differential equations

Publication . Graça, Daniel

Nesta dissertação iremos analisar um modelo de computação analógica, baseado em equações diferenciais polinomiais. Começa-se por estudar algumas propriedades das equações diferenciais polinomiais, em particular a sua equivalência a outro modelo baseado em circuitos analógicos (GPAC), introduzido por C. Shannon em 1941, e que é uma idealização de um dispositivo físico, o Analisador Diferencial. Seguidamente, estuda-se o poder computacional do modelo. Mais concretamente, mostra-se que ele pode simular máquinas de Turing, de uma forma robusta a erros, pelo que este modelo é capaz de efectuar computações de Tipo-1. Esta simulação é feita em tempo contínuo. Mais, mostramos que utilizando um enquadramento apropriado, o modelo é equivalente à Análise Computável, isto é, à computação de Tipo-2. Finalmente, estudam-se algumas limitações computacionais referentes aos problemas de valor inicial (PVIs) definidos por equações diferenciais ordinárias. Em particular: (i) mostra-se que mesmo que o PVI seja definido por uma função analítica e que a mesma, assim como as condições iniciais, sejam computáveis, o respectivo intervalo maximal de existência da solução não é necessariamente computável; (ii) estabelecem-se limites para o grau de não-computabilidade, mostrando-se que o intervalo maximal é, em condições muito gerais, recursivamente enumerável; (iii) mostra-se que o problema de decidir se o intervalo maximal é ou não limitado é indecídivel, mesmo que se considerem apenas PVIs polinomiais.

2007Doctoral thesis

Open Access

The ordinary differential equation defined by a computable function whose maximal interval of existence is non-computable

Publication . Graça, Daniel; Zhong, Ning; Buescu, Jorge

Let (®, ¯) ½ 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.

2006Conference object

Open Access

Robust simulations of Turing machines with analytic maps and flows

Publication . Graça, Daniel; Campagnolo, Manuel; Buescu, Jorge

In 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.

2005Book part

Open Access