Recursive Functionals - 1st Edition - ISBN: 9780444894472, 9780080887173

Recursive Functionals, Volume 131

1st Edition

Authors: L.E. Sanchis
eBook ISBN: 9780080887173
Imprint: North Holland
Published Date: 18th May 1992
Page Count: 276
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents

Mappings and Domains. Functionals and Predicates. Basic Operations. Primitive Recursive Operations. Basic Recursion. Church's Thesis. Functional Recursion. Recursive Algorithms. Formalization: Structural Semantics. Formalization: Reductional Semantics. Interpreters. A Universal Interpreter. Enumeration. Continuous Functionals. A Selector Theorem. Hyperenumeration. Recursion in Normal Classes. Recursion and Church's Thesis. References. Index.


This work is a self-contained elementary exposition of the theory of recursive functionals, that also includes a number of advanced results. Although aiming basically at a theory of higher order computability, attention is restricted to second order functionals, where the arguments are numerical functions and the values, when defined, are natural numbers. This theory is somewhat special, for to some extent it can be reduced to first order theory, but when properly extended and relativized it requires the full machinery of higher order computations. In the theory of recursive monotonic functionals the author formulates a reasonable notion of computation which provides the right frame for what appears to be a convincing form of the extended Church's thesis. At the same time, the theory provides sufficient room to formulate the classical results that are usually derived in terms of singular functionals. Presented are complete proofs of Gandy's selector theorem, Kleene's theorem on hyperarithmetical predicates, and Grilliot's theorem on effectively discontinuous functionals.


No. of pages:
© North Holland 1992
North Holland
eBook ISBN:

Ratings and Reviews

About the Authors

L.E. Sanchis Author

Affiliations and Expertise

School of Computer and Information Science, Syracuse University, Syracuse, NY, USA