Loading...
Research Project
ConTComp: Continuous time computation and complexity
Funder
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