We are pleased to announce that we now have also an online WebAssembly interpreter for the WHILE language called whilers.

whilers is a  WHILE interpreter developed by Jak Kostrzanowski specifically for the Limits of Computation module. It is implemented a WebAssembly-Rust app and thus can be run online without installation.

Toby Dennison has implemented syntax highlighting for the WHILE language for the Sublime 3 editor. The necessary files and installation descriptions can be found at:

https://github.com/z5229221/WHILE-Syntax-Highlighter

!

This textbook discusses the most fundamental and puzzling questions about the foundations of computing. In 23 lecture-sized chapters it provides an exciting tour through the most important results in the field of computability and time complexity, including the Halting Problem, Rice’s Theorem, Kleene’s Recursion Theorem, the Church-Turing Thesis, Hierarchy Theorems, and Cook-Levin’s Theorem. Each chapter contains classroom-tested material, including examples and exercises. Links between adjacent chapters provide a coherent narrative.

Fundamental results are explained lucidly by means of programs written in a simple, high-level imperative programming language, which only requires basic mathematical knowledge. Throughout the book, the impact of the presented results on the entire field of computer science is emphasised. Examples range from program analysis to networking, from database programming to popular games and puzzles. Numerous biographical footnotes about the famous scientists who developed the subject are also included.

“Limits of Computation” offers a thorough, yet accessible, introduction to computability and complexity for the computer science student of the 21st century.

“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. … I think Reus’s book deserves a large readership and should be tried out as an alternative text … in computing and communications courses worldwide.”
(Sitabhra Sinha, Computing Reviews, January, 2017)

Book stats for its first year:

• 14,420 chapter downloads
• top 25% of Springer eBooks

ERRATA

• Page 1: Unfortunately the first sentence of the book contains a typo (Thanks to Philip Saville for pointing this out). Where the first sentence ends, there should actually be a comma and the sentence continue.
• page 68, Fig. 6.2., first line: the “S” on the right hand side should be “{S}”
• page 168, Def. 13.5 “much slower than f” must be “much more slowly than g”.
• page 179, Def. 14.3 “Cobham-Edmons Thesis” must be “Cobham-Edmonds Thesis”.
• page 211, last line: in the Big-O complexity one “ln” has been swallowed up. It must be “O(n^{3.5} L^2 ln L ln (ln L))”.
• page 208, Fig 16.6 b (and Example 16.6): the max flow (and min cut) is actually 4 in the graph as printed. Add one more flow from source s to 2, 2 to 5, and 5 to sink t. This is all in line with max capacities. (Thanks to Oliver Thomas, who’s on my module, for spotting this.)
• page 242, line -12: angle brackets should be square brackets, i.e. f([G,K,A]) = [G,K,a,a,].
• page 244, footnote 4: There is a slightly embarrassing mistake here (which we hope to discuss more in detail in a future second edition), namely it is not the case that f(|d|) <= p1(|d|), as one can construct exponentially large tree in polynomial (quadratic) time with the help of the input (It is a good exercise to program that.). For Turing machines things are simpler, there the output of a polynomial algorithm can only be polynomially large. The WHILE language behaves very differently from Turing machine programs here. The previously suggested measure for cons (also for the GOTO language) is justified by a dag implementation but it does not guarantee that polynomial programs produce polynomial output. This simply has to be added as a requirement for WHILE (GOTO).
• Theorems 19.1 and 19.2. only hold if we add that the reduction functions is implemented by polynomial program that produce output whose size is bounded polynomiallly in the input. Thanks to Jak Kostrzanowski for pointing out the oversight.
• page 272, Exercise 12c: “(¬A,¬C₁)” must be “(¬A,C₁)”
• page 281, In item 2 “the approximation threshold such that no algorithm can produce a solution” must of course be “the approximation threshold such that an algorithm can produce a solution”.

If you are teaching a computability and complexity module at your institution, you can obtain useful resources (slides, exercises) from the author, if you adopt this book as your official course textbook.
Interested? If so, please get in touch by sending a message to the email address given further below. Many thanks!

This website uses Google Analytics, but only for page tracking. This installs cookies to help us accurately estimate the number of visitors to the website and volumes, dates, and regions of usage.

We do not use cookies to collect personally identifiable information about you. All information collected is anonymous. Google Analytics does not store any personal information about website users. Read the Google Analytics privacy document for more details.

However, if you wish to restrict or block the cookies which are set by our website, or indeed any other website, you can do this through your browser settings. For more information, visit for instance aboutcookies.org. There you will also find details on how to delete cookies from your machine as well as more general information about cookies.