(IST, UTL)
Computing over the reals: a new non-standard approach
Data: 2/3/06
Local: Sala 2.5.
Hora: 16:30
Resumo
In this paper we show how to explore the classical theory of
computability using the tools of Analysis: a differential scheme is
substituted for the classical recurrence scheme and a limit operator
is substituted for the classical minimalization. We show that most
relevant problems of computability over the non-negative integers can
be dealt with over the reals: elementary functions are computable,
Turing machines can be simulated, the hierarchy of non-computable
functions be represented (being the classical halting problem solvable
in some level). The most typical concepts in Analysis become natural
in this framework. The most relevant question is posed: can we solve
open problems of classical computability and computational complexity
using, in the Popper saying, the toolbox of Analysis?
Reinhard Kahle, 24.02.06