The Foundations of Computability Theory

by Borut Robic

Introduction.- The Foundational Crisis of Mathematics.- Formalism.- Hilbert's Attempt at Recovery.- The Quest for a Formalization.- The Turing Machine.- The First Basic Results.- Incomputable Problems.- Methods of Proving the Incomputability.- Computation with External Help.- Degrees of Unsolvability.- The Turing Hierarchy of Unsolvability.- The Class D of Degrees of Unsolvability.- C.E. Degrees and the Priority Method.- The Arithmetical Hierarchy.- Further Reading.- App. A, Mathematical Background.- References.- Index.

Genres: Computer Science

352 pages, Paperback

First published October 9, 2015