Higher generalizations of the Turing Model
Dag Normann · Cambridge University Press eBooks · 2014
. The “Turing Model”, in the form of “Classical Computability Theory”, was generalized in various ways. This paper deals with generalizations where computations may be infinite. We discuss the original motivations for generalizing computability theory and three directions such generalizations took. One direction is the computability theory of ordinals and of admissible structures. We discuss why Post's problem was considered the test case for generalizations of this kind and briefly how the problem was approached. This direction started with metarecursion theory, and so did the computability theory of normal functionals. We survey the key results of the computability theory of normal functionals of higher types, and how, and why, this theory led to the discovery and development of set recursion. The third direction we survey is the computability theory of partial functionals of higher types, and we discuss how the contributions by Platek on the one hand and Kleene on the other led to typed algorithms of interest in Theoretical Computer Science. Finally, we will discuss possible ways to axiomatize parts of higher computability theory. Throughout, we will discuss to what extent concepts like “finite” and “computably enumerable” may be generalized in more than one way for some higher models of computability. §1. Introduction . In this paper we will survey what we may call higher analogues of the Turing model. The Turing model, in the most restricted interpretation of the term, consists of the Turing machines as a basis for defining computable functions, decidable languages, semi-decidable languages and so forth.