Foundations of Computability Theory

Part I, The Roots of Computability Theory.- Introduction.- The Foundational Crisis of Mathematics.- Formalism.- Hilbert's Attempt at Recovery.- Part II, Classicial Computability Theory.- The Quest for a Formalization.- The Turing Machine.- The First Basic Results.- Incomputable Problems.- Methods of Proving Incomputability.- Part III, Relative Computability.- 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.- Part IV, Back to the Roots.- Computability (Church-Turing) Thesis Revisited.- Further Reading.- App. A, Mathematical Background.- App. B, Notation Index.- Glossary.- References.- Index.

Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.

• História da engenharia e da tecnologia
• Teoria matemática da computação
• Fundamentos da Matemática
• História da Matemática

Algorithms;Computability Theory;Relative Computability;Turing Machine;Oracles;Models of Computation;Church-Turing Thesis;Computably Enumerable (c.e.) Sets;History of Computing