کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436916 690051 2007 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new conceptual framework for analog computation
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A new conceptual framework for analog computation
چکیده انگلیسی

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?

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 374, Issues 1–3, 20 April 2007, Pages 277-290