Limits of computation. From a programming perspective (Q518688)

This is a textbook about computability and complexity delivered as a one-semester final-year module for undergraduates. Regretfully, as the author observes in his Preface, many ``modern'' computer science curricula are such that ``allegedly `unpopular' modules, including formal theory and mathematics, are the victims (of curricula development). As a consequence, computer science students have to a degree lost the skills to digest material presented in an extremely formal and symbolic fashion.'' (p. vii). The term ``extremely'' here is, in the opinion of this reviewer, an exaggeration. Thus, the more or less ordinary requirement of mathematical maturity is often not satisfied by students. Such a state of affairs was very strongly criticized by E. W. Dijkstra as early as in the 1970s, and more recently commented upon by D. Bjørner: ``the `powers that be' have, in their infinite wisdom, apparently decided that courses and projects around Internet, Web design and collaborative work\dots having no theoretical foundations, are more important: `relevant to industry''' [\textit{D. Bjørner} and \textit{K. Havelund}, Lect. Notes Comput. Sci. 8442, 42--61 (2014; Zbl 1362.68007)]. As one of the results, to quote the author again, students asked, ``why (they) had to write tedious Turing machine programs, given that everyone programmed in languages like Java''. Fortunately, an excellent computability and complexity text using an actual programming language (instead of a Turing machine) exists [\textit{N. D. Jones}, Computability and complexity. From a programming perspective. London: MIT Press (1997; Zbl 0940.68050)] and was adopted by the author in his teaching. When picking and choosing ``the most important and appealing chapters'' from [loc. cit.] for his course, the author observed that ``not all the third-year students had this [good mathematical] maturity (given the heterogeneity of backgrounds and reduction of maths teaching in the undergraduate years one and two).'' Therefore the author wrote a lot of explanatory notes and comments and added a large amount of new material: ``The results of this effort are the 23 individual lectures of this book. A (British) semester is 12 weeks long, which usually requires 24 lectures to be delivered.'' The book under review, to which Neil Jones contributed a Foreword, contains many, and proper, references to [loc. cit.]. Each chapter of the book under review starts with its plan, also providing a ``taste'' of what follows. There are quite a few exercises and dozens of important references at the end of each chapter, as well as a lot of interesting historical footnotes throughout. Seven more or less detailed introductory chapters out of 23 are about setting the stage, especially explanation of the language used (WHILE -- a very simple but powerful language with a single data type -- binary trees), interpreters, etc. Both here and in the rest of the book, the presentation at times (but not always!) appears to be too detailed, and explicit abstracting the interesting high-level concepts out of the detailed narrative would be useful and enhance understanding. Such abstracting was done, for example, in proving the undecidability of the halting problem where the author properly starts with the plan of the proof, as well as on p. 187 (``sketch the idea of the proof''). It may be interesting to compare the author's approach with the one in [\textit{A. Shen} and \textit{N. K. Vereshchagin}, Computable functions. Transl. from the Russian by V. N. Dubrovskii. Providence, RI: American Mathematical Society (AMS) (2003; Zbl 1015.03002)] (that assumes a ``certain level of mathematical culture''): ``we attempt to select central notions and facts from the general theory of algorithms and present them clearly, trying not to shadow simple general ideas by technical details.'' It is also interesting to observe that ``a taste of computability theory'' in [Jones, loc. cit.] already on pp. 14--16 includes theorems (with proofs) stating that the set of all total functions is uncountable, that the set of all effectively computable partial functions is countable, and that therefore effectively uncomputable functions exist. The author properly notes, among other things, that his book may serve not only as an undergraduate text, but also as a reference source. The final two chapters present overviews of molecular computing and quantum computing. (Regretfully, conceptually new and interesting interactive computing [\textit{D. Goldin} (ed.) et al., Interactive computation. The new paradigm. Berlin: Springer (2006; Zbl 1106.68002)] is not mentioned.) The book concludes with a list of further reading -- 40 computability and complexity textbooks (including [Jones, loc. cit.; Shen and Vereshchagin, loc. cit.], but not including [\textit{Yu. I. Manin}, A course in mathematical logic for mathematicians. Chapters I--VIII translated from the Russian by Neal Koblitz. With new chapters by Boris Zilber and Yuri I. Manin. 2nd ed. Berlin: Springer (2010; Zbl 1180.03002)]). It may be instructive to add to this list a mini-course -- a short presentation of ``many of the major themes and theorems [of computability and complexity] with the basic language of category theory'' [\textit{N. S. Yanofsky}, ``Theoretical computer science for the working category theorist'', Preprint, \url{arXiv:1710.030906}].