کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436916 | 690051 | 2007 | 14 صفحه PDF | دانلود رایگان |
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?
Journal: Theoretical Computer Science - Volume 374, Issues 1–3, 20 April 2007, Pages 277-290