Seminários de Lógica Matemática

13 de Dezembro, 16h00

ON ROBOUST SIMULATIONS OF TURING MACHINES WITH ANALYTIC FLOWS
SALA 3.10 - IST

Daniel Graça (Universidade do Algarve e SQIG -- Instituto de Telecomunicaes)

Abstract:

In this talk we will present a procedure that shows that every Turing machine can be simulated by an initial-value problem defined with analytic ordinary differential equations (ODEs), in an error-robust manner. We show that the method is constructive and that the ODE system can be expanded to an equivalent polynomial ODE. We will use this result to show that the problem of deciding whether the maximal interval of existence of solutions for polynomial ODEs is finite or not is undecidable.

| back