Analog Computation
(a new research program?)

J. Felix Costa


We show how to explore the classical theory of computability using the tools
of Analysis: a differential scheme is substituted for the classic 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?


(Joint work with Jerzy Mycka)