Computability Theory, Second Edition

Computability Theory, Second Edition

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

Purchasing Options

Hardback
$79.95
ISBN 9781439838433
Cat# K11743
Add to cart
 

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.

Textbooks
Other CRC Press Sites
Featured Authors
STAY CONNECTED
Facebook Page for CRC Press Twitter Page for CRC Press You Tube Channel for CRC Press LinkedIn Page for CRC Press Google Plus Page for CRC Press
Sign Up for Email Alerts
© 2014 Taylor & Francis Group, LLC. All Rights Reserved. Privacy Policy | Cookie Use | Shipping Policy | Contact Us