Turing oracle machines, online computing, and three displacements in computability theory (Q1032637)

This paper gives well-structured material about Turing oracle machines in relation with computability theory. By comparing the notions introduced in the past by different researchers, the author justifies his own mode of presenting the subject. In the first part of the paper, \S1--\S3, the author describes the history of computability theory, the roles of Gödel, Church and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). In \S4--\S6 he presents Turing oracle machines (o-machines) and Post's introduction of them into relative computability. Continuous functionals on Cantor space and online computations, two topics that arose from Turing functionals, are presented in \S7. After that, the author argues that Turing o-machines, relative computability, and online computing are the most important concepts in this subject area, more so than Turing a-machines and standard computable functions. In the last part, the author presents three displacements in computability theory: ``computable'' versus ``recursive'', renaming the Church-Turing thesis as computability thesis, and Turing a-machines versus Turing o-machines. Also, the historical reasons they occurred are presented