Recursive functionals (Q1202200)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recursive functionals |
scientific article |
Statements
Recursive functionals (English)
0 references
23 January 1993
0 references
The subject of the book is computability theory of higher order functions, i.e. functionals. Compared with other texts on the subject, e.g. \textit{P. G. Hinman's} book [Recursion-theoretic hierarchies (1978; Zbl 0371.02017)], the work under review has two distinctive features: it extends the standard theory by allowing partial functions as arguments, and it restricts it by disallowing higher order arguments which are not numerical functions. The author's reason for the restriction is simply that ``a good and sufficiently general description of the theory at this level should be in place before considering extensions to higher types'' (p. vii). Concerning the extension (allowing partial function arguments), the theory is made manageable by restricting to monotonic functionals, and the book demonstrates convincingly that a reasonable theory of computation can be developed in this setting. At the same time a fair amount of the classical theory is carried over to the present situation, most notably Gandy's selector theorem, Kleene's theorem on hyperarithmetic predicates and Grilliot's theorem on effectively discontinuous functionals. No attempt is made, however, to establish some relations with the more general theory of higher order computability due to Scott, although the existence of this theory is shortly mentioned in the preface (but no papers of Scott and e.g. Ershov or Plotkin are among the references). This is particularly disappointing since recently some progress has been made in establishing a proper mathematical context for the treatment of totality, a notion central for the book under review; cf. \textit{U. Berger} [Ann. Pure Appl. Logic 60, 91-117 (1993; Zbl 0776.03031)], or the recent book of \textit{E. R. Griffor}, \textit{I. Lindstroom} and \textit{V. Stoltenberg- Hansen} [Mathematical theory of domains (Cambridge University Press) (1994)]. The book develops the theory from scratch and contains full and carefully worked out proofs. A fair number of exercises is provided, as well as notes following each chapter, which provide some background information and give references to the literature.
0 references
higher-order computability
0 references
recursive functionals with partial arguments
0 references