Computability Theory, Second Edition
Purchasing Options
Features
- Discusses the motivation behind the main concepts and technical frameworks of computability theory
- Points to open problems and research topics
- Includes new sections on computability of structures and computability in science
- Contains new material on hyperarithmetical and Borel sets
Summary
Designed for advanced undergraduate or beginning graduate students, this book provides a complete introduction to computability theory. This second edition includes new material on hyperarithmetical and Borel sets as well as more material on computability of structures, Pi-0-1 classes, and computability in science. It features an expanded treatment of complexity of computations and updated future directions in computability. In addition, the section on randomness is now a separate chapter. The author also discusses advanced topics in greater depth, including Post’s problem, forcing and category, applications of determinacy, and the computability of theories.
Table of Contents
COMPUTABILITY AND UNSOLVABLE PROBLEMS
Hilbert and the Origins of Computability Theory
Models of Computability and the Church-Turing Thesis
Language, Proof and Computable Functions
Coding, Self-Reference and the Universal Turing Machine
Enumerability and Computability
The Search for Natural Examples of Incomputable Sets
Comparing Computability and the Ubiquity of Creative Sets
Godel’s Incompleteness Theorem
Decidable and Undecidable Theories
INCOMPUTABILITY AND INFORMATION CONTENT
Computing with Oracles
Nondeterminism, Enumerations and Polynomial Bounds
Complexity of Computations
MORE ADVANCED TOPICS
Post’s Problem: Immunity and Priority
Forcing and Category
The Computability of Theories
Randomness
Computability and Structure
Computability and Incomputability in Science
Author Bio(s)
S. Barry Cooper is a professor in the Department of Pure Mathematics at the University of Leeds, UK.
