Motivation If you've never heard of why someone would study the "Theory of Computation" and how this differs from something perhaps more tangible like Motivation If you've never heard of why someone would study the "Theory of Computation" and how this differs from something perhaps more tangible like programming or software engineering, you might come to the conclusion that this is "all just theory"...*waves around hand in the air in a useless circular manner*, but I'd beg you to not jump to this thought too soon! It's not that the latter is practical, while the former is just theory, but rather that what we call "programming" or "software engineering" is usually very specific to a certain set of technologies of a specific era or even a specific hardware implementation, whereas the former "theory" contains concepts that can be applied agnostic of the hardware you are dealing with, agnostic to the time period you are living in, agnostic of the specific programming language you are using, and even in my case, agnostic to the field at which you are even applying this knowledge to!
Computing is a very general concept that can be applied to multiple fields and domains of expertise and is much more a "way of thinking" and collection of unique logical tools and methods for solving problems in whatever domain, either software, linguistics, mathematics, electrical engineering, philosophy, botany, physics, and in my case, the foundations of biology! It is kind of unfortunate given the name, but "computing" is not about computers per se, but rather about the nature of problem solving, talking about certain limits to how efficiently a problem can be solved, and even figuring out if our problem even has a way of solving it to begin with (which you'll come to learn is very different from merely checking whether an answer is correct)! The nature of time, memory, space, efficiency, and representation are all topics that are explored in this area.
Background Having just recently finished a Formal Grammars & Automata Theory course at the local university where we used the canonical textbook by Sipser (my review of that book here), I'm going to say that that book plus this one are the main reasons why I was able to keep up with the course and not fall behind. Whereas the Sipser book reads like a more traditional definition-lemma-proof book that you might encounter in some fields of math, this book is geared towards those that are practically-minded, where instead of proofs you get all your examples in modern-day Python code (with the online version of the book also giving examples in Java code as well). An example of that can be seen here:
[image]
I believe this is crucial for those that *learn by doing* or prefer a "visceral understanding", and for those that are lucky enough to be able to learn through both methods, they would be well-served by complementing this book with the Sipser one. Another thing to note is that the language and layout of this book is quite modern as well. It's hard to describe, but there's something somewhat old and dated about the Sipser book that sometimes might put one to sleep, whereas this book is just clean and crisp. Like check out this way of illustrating how our programs interact with each other (which in Sipser's case would instead just be one giant proof). Much more intuitive, huh?
[image]
It might just be the use of colors, extra spacing, and higher quality thicker paper, but little things like these do wonders for those that engage in long periods of study late at night with lower-than-usual lighting conditions, or maybe those of us who do a bit more rough-handling by bringing a book to a park or something (although I admit that this extra quality probably has the downside of raising the book's publishing costs).
For those that are thinking of using this book to teach, I think I should quickly note that there are some differences between learning from this book versus learning from Sipser's. Much of the more advanced theoretical material that is covered in Sipser's book has been eliminated from this book, with the main target audience for this book being at the undergraduate level. You can check out the Content section below for more, but this book basically includes the same material as Sipser's, minus the following from the "Computability" section: unrestricted grammars, recursive function theory, lambda calculus, recursively enumerable, recursive, and non-recursive languages, and minus the following from the "Complexity" section: space complexity, hierarchy theorems, circuit complexity, randomness, and interactive proofs. It also teaches concepts in a bit of a non-traditional order, with Turing machines being covered before finite automata, but this makes sense given that this book covers a practical approach that emphasizes computer programs first.
For the self-study people out there thinking about prerequisites, the author does an incredible job keeping requirements to a minimum (much more than Sipser in my opinion), in that basic high school level algebra will suffice (no calculus needed), and programming fluency is also minimal given that everything is in readable Python (and even at that, the programs are very simple in their complexity). As a disclaimer, although I'm just a data scientist with a former background in neuroscience, I have invested a non-trivial amount of both non-formal + official time in coursework such as logic, set theory, and generally "pure math" areas, and I was also concurrently going through another official and very complementary proof-heavy logic course in Undecidability & Incompleteness, so my theoretical fluency is probably a bit more than needed for this book, and given that most data scientists are well-versed in reading and writing Python, a book like this would be very much welcomed compared to something like Sipser's. So yeah, just take my review with all that in mind.
Other Helpful Material When studying some subject I always recommend trying to learn from multiple sources because you can't always guarantee that you'll never "get stuck" on some concept or section of a book. I've found that sometimes having multiple perspectives and different people explaining things to me can help. I've already mentioned working through this book in tandem with Sipser's, but two other books I was also reading in parallel that I recommend are The Annotated Turing and Gödel's Theorem: An Incomplete Guide to Its Use and Abuse, the former of which I highly recommend for its excellent historical treatment of Alan Turing's original 36-page paper establishing what is now known as the Turing Machine, and the latter book whose mathematical & philosophical topic arguably spurred the development of the former (for a short & neat explanation of this for the layman, ).
I usually like accompanying my studies with historical background like this to not only help motivate me, but also to give me a bigger "forest-over-trees" picture and context as to why these ideas were even formed to begin with, how this fits into the grander historical narrative, and why I should even care. It's also somewhat fun for my socially-inclined primate brain to know the people and controversies behind such ideas, which provides a useful scaffold and cognitive framework to remember this material much better and for longer (if you especially enjoy this, see the book Exact Thinking in Demented Times: The Vienna Circle and the Epic Quest for the Foundations of Science).
In addition to the aforementioned books, I would also recommend going through which covers the Theory of Computing and solves a lot of practice problems with you (the latter of which is key to becoming fluent with this material!) Furthermore, you can also download all the Python and Java code for this course . Hopefully all that linked material proves helpful on your learning journey :)
Content Somewhat similar to Sipser's book and similar to most "Theory of Computation" curricula, this book is broken up into 2 main parts: Computability Theory and Complexity Theory.
In the first section of this book we go over what can and cannot be computed by a program (using Python programs as examples), as well as some impossible Python programs. The Halting problem and proof by contradiction was smartly done here using practical examples. We then go over various computational problems, beginning with graphs, alphabets, strings, and languages, the different categories of problems (search, optimization, threshold, function, decision, etc), recognizing vs. deciding languages, and then finally the model of a Turing machine. I really think this latter part is how college courses should be teaching this material and I wish my official university course did something similar. Oftentimes it is very time consuming to draw Turing machines and then when it gets more complicated students are often forced to write pseudo-code and line-by-line high-level versions of algorithms on paper. Using this author's approach of writing tangible Python programs I think is quite superior in pedagogical strategy as there are multiple ways students can experiment, play, and "check" their programs in real-time, which grants much more intuition than something like an algorithm written on paper that can only really be "checked" for correctness once it's turned-in to an external grader/teacher and then handed back. The feedback loop for learning is just too wide and sometimes non-existent for the latter to really have a strong effect on one's learning. It is because of this that I think a book like this should be praised quite highly for moving the education field forward.
Going back to the material, after variations of Turing machines and then introduction to universal Turing machines, we then are taught the technique of reductions (for an interesting article on "time-traveling Turing machines" and closed-timelike curves in computation, by quantum computing theorist, Scott Aaronson). As we can see, compared to the Sipser book this book explains how the reduction technique in proofs works visually:
[image]
And here:
[image]
This is then followed up with nondeterminism, and finally DFAs and NFAs, regular expressions, and our famous pumping lemma. Here is where we can note the "flip-flop" order of this book compared to a more traditional curriculum which usually starts off with this material. Somewhat of an aside, but I really wished this book at least introduced or covered a little bit of context-sensitive grammars, since that was my primary interest and motivation for even taking this course to begin with (due to its relationship with cellular automata, lindenmayer systems, artificial life, and theoretical biology, all of which ). None of the books I have encountered so far even do this! Gah!
The book then moves on to the second half of the material concerning computational complexity theory, moving away from asking questions about "possibility" and more towards questions of "efficiency". Big-O notation is introduced, in addition to your usual complexity classes. Further depth is then achieved in the next section with the reader delving into polynomial and exponential complexities, with the next two sections covering polynomial-time mapping reductions and NP-completeness, with a nice diagram showing the polyreductions used in this book:
[image]
I believe this is where an author's more practical strategy of teaching through code shines here, as this allows one to actually see where these problems apply in their daily workplace settings or even maybe another course they might take in the future such as in cryptography, networking, or algorithms. The book concludes with more history and theoretically-bent material with the famous Church-Turing thesis, undecidability of Peano arithmetic, Karp's problems and reductions, etc.
Conclusion Overall, this book introduced highly fascinating material at the intersection of multiple disciplines of computer science, logic, math, philosophy, electrical engineering, linguistics, etc. The amount of accompanying explanatory discussion along with the very practically-minded approach via Python programs makes this book highly recommended in my opinion, especially for self-study.
My only comment for improvement is to include some introductory material in the computability section on *context-sensitive grammars! I would've loved to have an official and well-backed source that I could reference and learn this from (especially since I haven't yet come across a theory of computing book that does just that). And also, although it might seem a tad too advanced, I do think maybe a brief introduction to what is known as which observes the fundamental relationships between computation / programming languages, formal logic / type theory, and category theory / topology to be a highly relevant and significant perspective which would allow the student coming from another field to see all the fascinating connections linking everything together, or alternatively help a student to branch out to other fields to which the theory of computation can be applied. This "Rosetta stone" is a marvelous way to bring this book and field to higher prominence and relevance today. I know this book is aimed towards undergrads, but I think if the author chose to incorporate just these two aforementioned materials they would probably usurp the Sipser book's reign on Theory of Computing curricula!
Thanks for reading :)
*EDIT: From the comments below with Ritu, I was motivated to take a look at the textbook Automata, Computability and Complexity: Theory and Applications by Elaine Rich and just found out that by way of the Myhill–Landweber–Kuroda theorem! So technically to be fair, I guess the above textbook by MacCormick indirectly covered CSGs whether the author intended to or not....more
Loading...
