Repository logo
 
Loading...
Project Logo
Research Project

ConTComp: Continuous time computation and complexity

Authors

Publications

The general purpose analog computer and computable analysis are two equivalent paradigms of analog computation
Publication . Bournez, Olivier; Campagnolo, Manuel; Graça, Daniel; Hainry, Emmanuel
In 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.
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.
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.
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.
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.

Organizational Units

Description

Keywords

Contributors

Funders

Funding agency

Fundação para a Ciência e a Tecnologia

Funding programme

POCI

Funding Award Number

POCTI/MAT/45978/2002

ID