کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662146 1633516 2009 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Turing oracle machines, online computing, and three displacements in computability theory
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Turing oracle machines, online computing, and three displacements in computability theory
چکیده انگلیسی

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine (o-machine) and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form.A number of topics arose from Turing functionals including continuous functionals on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 160, Issue 3, September 2009, Pages 368-399