Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1988 | Book

Functions and Predicates Read chapter Read first chapter

Reflexive Structures

An Introduction to Computability Theory

Author: Luis E. Sanchis

Publisher: Springer New York

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

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 ℓd ≠ ℓde. We shall see that both relations are possible, depending on the function c, but when c is a total function then ℓd ≠ ℓde, 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
Metadata
Title
Reflexive Structures
Author
Luis E. Sanchis
Copyright Year
1988
Publisher
Springer New York
Electronic ISBN
978-1-4612-3878-2
Print ISBN
978-1-4612-8386-7
DOI
https://doi.org/10.1007/978-1-4612-3878-2