Computability Theory

Series:
Published:
Content:
Author(s):
Free Standard Shipping

Purchasing Options

Hardback
ISBN 9781584882374
Cat# C2379

$99.95

$79.96

SAVE 20%


Features

  • Offers a concise introduction to the results and techniques of contemporary computability theory
  • Reflects modern developments in treatment and subject matter in this fundamentally important area
  • Provides an accessible guide to the direction of current research
  • Includes discussions of Turing definability, complexity of computations, and the relevance of computability theory to science
  • Summary

    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.

    Table of Contents

    SECTION I: COMPUTABILITY, AND UNSOLVABLE PROBLEMS

    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

    Editorial Reviews

    "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