Turing computability. Theory and applications. (English) Zbl 1350.03001

Theory and Applications of Computability. Berlin: Springer (ISBN 978-3-642-31932-7/hbk; 978-3-642-31933-4/ebook). xxxvi, 263 p. (2016).
The aim of the book under review is – as the author writes in the preface – to provide “a comprehensive treatment of the craft of computability in the sense of knowledge, skill in solving problems and presenting the solution in the most comprehensible, elegant form”. And it is added that “in a larger sense, the book is intended to develop the art of computability as an artistic endeavor, and with appreciation of its mathematical beauty” (Preface, p. xvii). The book consists of five parts. Part I “Foundations of computability” gives a thorough development of the foundations of computability from the definition of Turing machines up to finite injury priority arguments. Topics presented and discussed there include relative computability, computably enumerable sets, Turing reducibility, the arithmetical hierarchy classification of computably enumerable sets, oracle constructions and forcing and the finite injury method. In Part II “Trees and \(\Pi^0_1\) classes”, the following items are considered: open and closed classes, basic theorems, Peano arithmetic and \(\Pi^0_1\)-classes, randomness and \(\Pi^0_1\)-classes. Part III “Minimal degrees” is devoted to minimal degrees. It consists of two chapters in which minimal degrees below \(\empty ''\) and minimal degrees below \(\empty '\) are considered, respectively. In Part IV “Games in computability theory”, various games are considered, in particular Banach-Mazur games, Gale-Stewart games and Lachlan games. The book is closed by Part V “History of computability” in which the reader will find information on Hilbert’s programme, on Gödel, Church and recursive functions, on Turing’s analysis, Turing’s oracle machine, Emil Post contributions, finite injury priority arguments as well as on computability and recursion terminology. Most chapters include exercises. There is also an extensive bibliography and index. As the author says in the preface, particular sections have been rewritten over and over in response to comments made by students, lecturers and researchers around the world. The book can be used by advanced undergraduate and graduate students in computer science and mathematics. It will be useful also for researchers in computability and mathematical logic.


03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
03Dxx Computability and recursion theory
Full Text: DOI