Skip to main content
main-content

Über dieses Buch

Reflexive Structures: An Introduction to Computability Theory is concerned with the foundations of the theory of recursive functions. The approach taken presents the fundamental structures in a fairly general setting, but avoiding the introduction of abstract axiomatic domains. Natural numbers and numerical functions are considered exclusively, which results in a concrete theory conceptually organized around Church's thesis. The book develops the important structures in recursive function theory: closure properties, reflexivity, enumeration, and hyperenumeration. Of particular interest is the treatment of recursion, which is considered from two different points of view: via the minimal fixed point theory of continuous transformations, and via the well known stack algorithm. Reflexive Structures is intended as an introduction to the general theory of computability. It can be used as a text or reference in senior undergraduate and first year graduate level classes in computer science or mathematics.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Functions and Predicates

Abstract
This chapter introduces the fundamental objects to be discussed in this work: numerical functions and numerical predicates. Initially, we are concerned with different procedures that can be used to specify functions and predicates and the manner in which such procedures can be combined. The main tool in our discussion is the notion of minimal closure, which characterizes the class of all functions and predicates that can be generated by using a given set of specification rules.
Luis E. Sanchis

Chapter 2. Recursive Functions

Abstract
All the specification rules in the preceding chapter are explicit, in the sense that the function (or predicate) being specified is determined entirely by a procedure involving only the given functions and predicates. Now we consider recursive specifications, in which a function h is specified by a rule involving the function h itself. Such a procedure is essentially ambiguous, because in general there are many functions satisfying the specification. This ambiguity can be disposed of only by elimination of the recursion, and this can be done in several ways. Closure under recursive specifications is used to define recursive functions. The relation with Church’s thesis is discussed in some detail.
Luis E. Sanchis

Chapter 3. Enumeration

Abstract
This chapter is concerned mainly with predicates, in particular with the specification of functions via predicates. In a rather restricted form this takes place via the graph predicates of functions. In a more general setting we consider selector properties. Operations on predicates and the associated closure properties play a central role in our discussion. In particular, we consider the so-called unbounded quantification, existential and universal.
Luis E. Sanchis

Chapter 4. Reflexive Structures

Abstract
In this chapter we continue the study of classes closed under recursive operations, with emphasis on those classes of the form = RC(c), where c is some arbitrary function. There are many problems about these classes which cannot be solved with the techniques used in Chapter 2. For example, we do not know yet if d = de or dde. We shall see that both relations are possible, depending on the function c, but when c is a total function then dde, which means that there are predicates that are d-enumerable (i.e., recursively enumerable in c) but are not recursive in c. Results of this type require a diagonalization technique, involving a kind of internal enumeration, or indexing for the class RC(c).
Luis E. Sanchis

Chapter 5. Hyperenumeration

Abstract
In this chapter we introduce new closure conditions, much stronger than those considered before. These conditions apply primarily to classes of predicates but can be extended to classes of functions via graph predicates. They are nonfinitary, for they involve different forms of universal quantification. Our main interest is to find reflexive structures that are closed under this type of condition. While they are not total in the sense defined in Chapter 2, we shall see that they may satisfy important selector properties.
Luis E. Sanchis

Backmatter

Weitere Informationen