Turing oracle machines, online computing, and three displacements in computability theory☆ Export

@article{citeulike:5326557, abstract = {We begin with the history of the discovery of computability in the 1930's, the roles of G\"{o}del, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines ( a -machines). To whom did G\"{o}del credit the definition of a computable function? We present Turing's notion [1939, {\S}4] of an oracle machine ( o -machine) and Post's development of it in [1944, {\S}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 {\S}10–{\S}13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in {\S}14.}, author = {Soare, Robert I.}, citeulike-article-id = {5326557}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.apal.2009.01.008}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0168007209000128}, day = {07}, doi = {10.1016/j.apal.2009.01.008}, issn = {01680072}, journal = {Annals of Pure and Applied Logic}, keywords = {computability, curch-turing\_thesis, history\_of\_science, turing\_machine}, month = {May}, posted-at = {2009-10-22 09:53:35}, priority = {4}, title = {Turing oracle machines, online computing, and three displacements in computability theory☆}, url = {http://dx.doi.org/10.1016/j.apal.2009.01.008}, year = {2009} }

TY - JOUR ID - citeulike:5326557 L3 - citeulike-article-id:5326557 N2 - 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. JF - Annals of Pure and Applied Logic SN - 01680072 TI - Turing oracle machines, online computing, and three displacements in computability theory☆ KW - computability KW - curch-turing_thesis KW - history_of_science KW - turing_machine AU - Soare, Robert PY - 2009/05/07/ UR - http://dx.doi.org/10.1016/j.apal.2009.01.008 ER -