Article ID Journal Published Year Pages File Type
436916 Theoretical Computer Science 2007 14 Pages PDF
Abstract

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 minimization. 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 can be represented (the classical halting problem being solvable at 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, as Popper says, the toolbox of Analysis?

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics