The Recursion Theory of the Continuous Functionals
Published online by Cambridge University Press: 09 February 2010
Summary
INTRODUCTION
Classical or ordinary recursion theory has been subject to many generalizations and extensions. When we generalize a mathematical theory we want to give the old concepts a new meaning similar to the original one but within a new context. In generalized recursion theory this mainly means to generalize the concepts of finite, computation and reduction-procedure. There have been several successful generalizations of recursion theory, e.g. admissible recursion theory and recursion in normal higher type objects. There are also axiomatic approaches to a notion of ‘general recursion theory’. Fenstad [5] is a good introduction to this area.
When we extend a mathematical theory we want to see if the old concepts are meaningful in a wider context. The main concept of recursion theory is that of an algorithmic procedure. Elsewhere in this volume (Tucker [20]) there is a survey of finite algorithmic procedures over general algebraic structures, a typical example of extended recursion theory.
In [11] Kleene extended the notion of an algorithm to arbitrary objects of finite type. The pure finite types are defined as follows:
Tp (O) = ω = the natural numbers
Tp (n+1) = Tp(n)ω = the set of total maps from Tp(n) to ω.
He described indices e denoting algorithms for functions e operating on finite lists of functionals of finite type. The algorithms are described using nine schemata S1 – S9.
It can be and is discussed whether S1 – S9 gives a true extension of classical recursion theory, since computations no longer are finite. Moreover there are alternative ways to extend classical recursion theory to a hierarchy of functionals (Platek [19], Kleene [13]).
- Type
- Chapter
- Information
- Recursion Theory, its Generalisations and Applications , pp. 171 - 183Publisher: Cambridge University PressPrint publication year: 1980
- 1
- Cited by