Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences.
Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level.
The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science.
Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way.
HILBERT AND THE ORIGINS OF COMPUTABILITY THEORY
Algorithms and Algorithmic Content
Hilbert's Programme
Gödel, and the Discovery of Incomputability
Computability and Unsolvability in the Real World
MODELS OF COMPUTABILITY AND THE CHURCH-TURING THESIS
The Recursive Functions
Church's Thesis, and the Computability of Sets and Relations
Unlimited Register Machines
Turing's Machines
Church, Turing, and the Equivalence of Models
LANGUAGE, PROOF AND COMPUTABLE FUNCTIONS
Peano Arithmetic and its Models
What Functions Can We Describe in a Theory?
CODING, SELF-REFERENCE AND THE UNIVERSAL TURING MACHINE
Russell's Paradox
Gödel Numberings
A Universal Turing Machine
The Fixed Point Theorem
Computable Approximations
ENUMERABILITY AND COMPUTABILITY
Basic Notions
The Normal Form Theorem
Incomputable Sets and the Unsolvability of the Halting Problem for Turing Machines
The Busy Beaver function
THE SEARCH FOR NATURAL EXAMPLES OF INCOMPUTABLE SETS
The Ubiquitous Creative Sets
Some Less Natural Examples of Incomputable Sets
Hilbert's Tenth Problem and the Search for Really Natural Examples
COMPARING COMPUTABILITY
Many-One Reducibility
The Non-Computable Universe and Many-One Degrees
Creative Sets Revisited
GÖDEL'S INCOMPLETENESS THEOREM
Semi-Representability and C.E. Sets
Incomputability and Gödel's Theorem
DECIDABLE AND UNDECIDABLE THEORIES
PA is Undecidable
Other Undecidable Theories, and their Many-One Equivalence
Some Decidable Theories
SECTION II: INCOMPUTABILITY AND INFORMATION CONTENT
COMPUTING WITH ORACLES
Oracle Turing Machines
Relativising, and Listing the Partial Computable Functionals
Introducing the Turing Universe
Enumerating with Oracles, and the Jump Operator
The Arithmetical Hierarchy and Post's Theorem
The Structure of the Turing Universe
NONDETERMINISM, ENUMERATIONS AND POLYNOMIAL BOUNDS
Oracles versus Enumerations of Data
Enumeration Reducibility and the Scott Model for Lambda Calculus
The Enumeration Degrees,and the Natural Embedding of the
Turing Degrees
The Structure of De and the Arithmetical Hierarchy
The Medvedev Lattice
Polynomial Bounds and P =?NP
SECTION III: MORE ADVANCED TOPICS
POST'S PROBLEM: IMMUNITY AND PRIORITY
Information Content and Structure
Immunity Properties
Approximation and Priority
Sacks Splitting Theorem and Cone Avoidance
Minimal Pairs and Extensions of Embeddings
The |3 Theory - Information Content Regained
Higher Priority and Maximal Sets
The Computability of Theories
FORCING AND CATEGORY
Forcing in Computability Theory
Baire Space, Category and Measure
n-Genericity and Applications
Forcing with Trees, and Minimal Degrees
APPLICATIONS OF DETERMINACY
Gale-Stewart Games
An Upper Cone of Minimal Covers
Borel and Projective Determinacy, and the Global Theory of D
THE COMPUTABILITY OF THEORIES
Feferman's Theorem
Truth versus Provability
Complete extensions of Peano Arithmetic and Classes
The Low Basis Theorem
Arslanov's Completeness Criterion
A Priority-Free Solution to Post's Problem
Randomness
COMPUTABILITY AND STRUCTURE
Computable Models
Computability and Mathematical Structures
Effective Ramsey Theory
Computability in Analysis
Computability and Incomputability in Science
FURTHER READING
INDEX
"A very nice volume indeed. Although primarily a textbook, it lives up to the author's aim to have 'plenty here to interest and inform everyone, from the beginner to the expert.' … Cooper writes in an informal style, emphasizing the ideas underlying the techniques. All the standard topics and classic results are here. … Students will find useful pointers to the literature and an abundance of exercises woven into the text."
- Zentralblatt MATH, 1041
"[It] provides not only a reference repository of well-crafted proofs or proof-outlines for a large number of basic and beyond-basic facts in several areas of computability theory, but can also serve well as the textual basis for a course on the subject…"
- Mathematical Reviews, 2005h
