Turing's vision. The birth of computer science (Q2797848)

This book presents a layman's guide to answering the question of which problems can be solved by computers and which cannot. In effect, it presents step-by-step the concepts and arguments of \textit{A. M. Turing} [Proc. Lond. Math. Soc. (2) 42, 230--265 (1936; Zbl 0016.09701)] in modern terms. The path to computable and non-computable numbers leads through discussions of Hilbert's Tenth Problem, the halting problem, finite automata, Turing machines, lambda calculus, universal machines, diagonalization arguments, and the continuum hypothesis. Along the way lucid mini lessons are given in Boole's logic, alphabets and languages, regular expressions, and proofs by contradiction to name a few of the topics.NEWLINENEWLINEThe story as a whole makes clear why the 1936 paper is regarded as a foundation of computer science. The concluding biographical chapter gives due credit to the people who influenced Turing and who provided other essential contributions for the code breaking success at Bletchley Park. Some researchers would take issue, however, with the author's claim that the stored program concept originates with Turing's paper; see [\textit{T. Haigh} et al., ``Reconsidering the stored program concept'', IEEE Ann. History Comput. 36, 4--17 (2014; \url{doi:10.1109/MAHC.2013.56})].