Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Limits of computation : from a programming perspective
Reus B., Springer International Publishing, New York, NY, 2016. 348 pp. Type: Book (978-3-319278-87-2)
Date Reviewed: Jan 4 2017

In the early 1990s, a chance encounter with Douglas Hofstadter’s book Godel, Escher, Bach [1], an eclectic synthesis of philosophy, physics, and (dare I say it) computer science, left me intrigued about concepts of decidability and computational complexity. Being a physics undergraduate, I didn’t learn these things in a formal course, so I had to ask my friends studying computer science what I should read to have a more technical understanding of these concepts. While some recommended Hopcroft and Ullman [2], the recommended text for the theory of computation courses in most places at the time, another suggested Martin Davis’s Computability and unsolvability [3]. Yet others pointed out more mathematically rigorous texts, which I am sure were brilliant but somehow did not quite enthuse me to go beyond the first few pages without getting lost in the thicket of mathematical notations. Similarly, I was fascinated by a friend describing to me the traveling salesman problem, but when I tried reading Papadimitriou’s book on complexity [4], it proved to be heavy going. Frankly, I couldn’t quite see what the formal approach used in these books had to do with the languages I was using to program computers. So it was a feeling of deja vu when I learned from the preface of Bernhard Reus’s book that his original motivation to write the book was provided by a student asking him why one had to learn computation theory by writing tedious Turing machine programs when everyone programs their computers using high-level languages (the student mentioned Java, but in earlier times we would use C, Fortran, or even Basic).

Reus thinks the emphasis on such abstract models is because of the way computer science used to be taught even a decade or two earlier, when most computer scientists in academia would probably be mathematicians by training. In the institutions I have direct knowledge of, there is often a clear divide between those who work on the more abstract aspects (so much so that they are called “theoretical computer scientists”) and those who work on applications such as pattern recognition or learning. They often have very little to say to each other, with the former probably having more in common with their colleagues in the mathematics department, whereas the latter are possibly more comfortable talking to, for example, physicists. Given that the members of the former group would usually teach the courses on computability and complexity to the undergraduates, I can see how the situation that Reus has mentioned can persist even now in many places. Although I am sure that the more mathematically inclined of the students would love this approach, there is possibly room for a different method of teaching these topics to other students who may want to get into exciting topics such as undecidability and NP-completeness as quickly as possible. Reus searched for such a book and was rewarded by finding Neil Jones’s 1997 book Computability and complexity: from a programming perspective [5]. This book used the high-level While programming language that, like LISP, has lists as its datatype (and is simple enough to write its own interpreter) for illustrating the concepts of computability. However, despite the obvious attractions of Jones’s book, Reus found that occasionally students still found it difficult because of the prerequisites expected, such as a good knowledge of the notions of set theory and familiarity with a functional language having a built-in list type. The book under review (which is divided into two sections focusing on computability and complexity, respectively) resulted from Reus incorporating explanatory notes as well as additional material to Jones’s book that would make it attractive to a student of the mid-2010s. Some of the more obvious new topics are of course the fascinating developments that have taken place in the field after Jones’s book was published, including the Agrawal-Kayal-Saxena (AKS) algorithm that showed primality testing was in P, DNA computing, and the first quantum algorithms developed by Shor and Grover [6].

Overall, I think this is a very good update of Neil Jones’s brilliant approach at teaching computability and complexity in a nontraditional manner that may resonate with students who are not necessarily deeply interested in mathematical abstractions. One can gripe at the omission of one’s favorite topics. For example, the book focuses almost exclusively on time complexity and, unlike Jones, says almost nothing about space complexity classes such as PSPACE. I also found the use of large blocks of text quoted directly from cited sources (of course, with attribution) jarring in an otherwise smoothly flowing text. But all in all, these are minor complaints, and I think Reus’s book deserves a large readership and should be tried out as an alternative text (if necessary, augmented by that of Jones) in computing and communications courses worldwide.

Reviewer:  Sitabhra Sinha Review #: CR144986 (1703-0170)
1) Hofstadter, D. R.; , ; , Godel, Escher, Bach: an eternal golden braid. Basic Books, New York, NY, 1979.
2) Hopcroft, J. E.; Ullman, J. D. Introduction to automata theory, languages, and computation. Addison-Wesley, Boston, MA, 1979.
3) Davis, M. Computability and unsolvability. McGraw-Hill, New York, NY, 1958.
4) Papadimitriou, C. H. Computational complexity. Addison-Wesley, Boston, MA, 1993.
5) Jones, N. D. Computability and complexity: from a programming perspective. MIT Press, Cambridge, MA, 1997.
6) Nielsen, M. A.; Chuang, I. L. Quantum computation and quantum information. Cambridge University Press, New York, NY, 2000.
Bookmark and Share
 
Computability Theory (F.1.1 ... )
 
 
Modes Of Computation (F.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Computability Theory": Date
Decidability of the purely existential fragment of the theory of term algebras
Venkataraman K. Journal of the ACM 34(2): 492-510, 1987. Type: Article
Jul 1 1988
Computability
Weihrauch K. (ed), Springer-Verlag New York, Inc., New York, NY, 1987. Type: Book (9789780387137216)
Nov 1 1988
Computability and logic: 3rd ed.
Boolos G., Jeffrey R., Cambridge University Press, New York, NY, 1989. Type: Book (9789780521380263)
Jul 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy