This book offers an original and informative view of the development of
fundamental concepts of computability theory. The treatment is put into
historical context, emphasizing the motivation for ideas as well as
their logical and formal development. In Part I the author introduces
computability theory, with chapters on the foundational crisis of
mathematics in the early twentieth century, and formalism. In Part II he
explains classical computability theory, with chapters on the quest for
formalization, the Turing Machine, and early successes such as defining
incomputable problems, c.e. (computably enumerable) sets, and developing
methods for proving incomputability. In Part III he explains relative
computability, with chapters on computation with external help, degrees
of unsolvability, the Turing hierarchy of unsolvability, the class of
degrees of unsolvability, c.e. degrees and the priority method, and the
arithmetical hierarchy. Finally, in the new Part IV the author revisits
the computability (Church-Turing) thesis in greater detail. He offers a
systematic and detailed account of its origins, evolution, and meaning,
he describes more powerful, modern versions of the thesis, and he
discusses recent speculative proposals for new computing paradigms such
as hypercomputing.
This is a gentle introduction from the origins of computability theory
up to current research, and it will be of value as a textbook and guide
for advanced undergraduate and graduate students and researchers in the
domains of computability theory and theoretical computer science.
This new edition is completely revised, with almost one hundred pages of
new material. In particular the author applied more up-to-date, more
consistent terminology, and he addressed some notational redundancies
and minor errors. He developed a glossary relating to computability
theory, expanded the bibliographic references with new entries, and
added the new part described above and other new sections.
