A lot more detailed than your average "pop-sci" book, especially when it came to Conway's Game of Life / cellular automata sections (whereas the physiA lot more detailed than your average "pop-sci" book, especially when it came to Conway's Game of Life / cellular automata sections (whereas the physics sections were just meh). It is a bit dated though, but so is the majority of the artificial life field wrt popularity nowadays, with deep learning hogging all the spotlight. Also somewhat cool, in that at the end it even includes the code for Life written in an Assembler language!...more
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, see this YouTube video by Veritaseum).
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 this YouTube series by Easy Theory 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 for free here. 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, see this neat post 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 I discuss in my blog series here). 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 Computational Trinitarianism / Trilogy 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!
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 this as our textbook, I have to say that this book was probably the main reason for why I was able to keep up and not fall behind in the course. It doesn't read like a dry definition-lemma-proof book you might have encountered in some fields of math, but rather a hybrid of that with lots of helpful injected commentary going over the thought processes of how to solve these problems and how to work your way through these proofs in plain old regular english, with lots of useful diagrams when needed. One thing I especially appreciated was the author giving a theorem or making a claim, then following that up with a helpful discussion on the "proof idea" behind that claim, and then next with the proof written in a combination of english + symbols, and finally if needed, a very formal "algorithmic" way with the steps clearly enumerated line-by-line and in concise fashion.
An example of that can be seen here: [image]
This is a really good pedagogical technique that I wish more authors would follow, as students are given a choice as to "what level" of explanation and rigor best appeals to them. Here's another example, this time with an accompanying picture: [image]
For the self-study people out there thinking about prerequisites, it would probably be wise to have some practice and former experience with "proofs", but regardless, the author does a great job reviewing common mathematical notation and basic proof techniques at the beginning of the book, which would usually correspond to your common undergraduate first course in discrete mathematics. Such things as relations, functions, graphs, strings, languages, boolean logic, proof by construction / contradiction / induction, etc are reviewed at the beginning and accompanied with ample practice problems (with solutions!) such that you can strengthen your foundation if needed before moving onto the meat of the book. 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 logic course in Undecidability & Incompleteness, so take my review with 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. As such, I supplemented my reading with another textbook called What Can Be Computed? (my review here) which gives a more *hands-on*, practical approach to the theory of computing with lots of exercises in Python.
Two other books I was 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, see this YouTube video by Veritaseum). 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 this YouTube series by Easy Theory 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!) Hopefully all that linked material proves helpful on your learning journey :)
Content This book is broken up into 3 main parts: Automata & Languages, Computability Theory, and Complexity Theory. Again, each section contains lots of worked out examples with solutions, accompanied with helpful commentary.
The first part was my favorite and the main reason for why I was taking this course. In it the author covers the theory of regular languages, going over finite automata, non-determinism, regular expressions, and non-regular languages, while introducing you to a new and useful proof technique called the Pumping Lemma, which allows you to disprove the regularity of a language. For those coming from a linguistics background, you might find the intersection of this material and the Chomsky hierarchy of languages incredibly fascinating. The author then follows this up with material about context-free languages, discussing context-free grammars, pushdown automata, non-context free languages, and deterministic context-free languages. This material is highly relevant to those who are interested in the more practical problems of parsing natural languages, or maybe designing your own programming language, or even how a compiler works, etc. 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 I discuss in my blog series here).
In the second part of this book, the content shifts focus towards arguably more historical and philosophical content going under the header of 'Computability Theory'. Here we are introduced to the famous Church-Turing Thesis, Turing machines and a few of their variants (for an interesting article on "time-traveling Turing machines" and closed-timelike curves in computation, see this neat post by quantum computing theorist, Scott Aaronson). This section also covers the famous Halting/Decidability problem, as well as important proof techniques like diagonalization and reducibility. Some advanced topics are also covered with a small introduction to information theory and minimal length description, the compressibility of strings, randomness, etc. Although we didn't officially cover it in my course, I found this latter section quite interesting! (and especially relevant to biology!)
This last section of the book switches gears to what arguably makes up the bulk of most theoretical computer science research today. It deals with something called 'Complexity Theory'. Whereas the former second section of the book dealt with the question of whether some problems were even possible to solve to begin with, this latter third section of the book deals with how efficient can a problem be solved given a certain amount of time, space, memory, etc, ranking problems according to certain complexity classes. In here we first are introduced to how we measure complexity using Big-O notation, the famous P vs NP problem, NP-completeness, the Cook-Levin Theorem, SAT problems, and additional NP-complete problems like independent set, vertex cover, hamiltonian path, subset-sum, etc (which are all helpful in proof techniques like reduction used to prove NP-completeness, etc). And although we never were able to cover this far in my official course, the book does continue to go over space complexity like Savitch's theorem, NL-completeness, Intractability (hierarchy problems, relativization, and circuit complexity), as well as more advanced topics like approximation algorithms, probabilistic algorithms interactive proof systems, parallel computation, and cryptography, all of which I assume the author included in case this book is used in the graduate-level Masters or PhD setting for specific topical courses and such.
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 ample amount of worked-out examples makes this book highly recommended in my opinion (and suitable for self-study, especially if you follow along with one of the free lecture materials I linked to above).
My only comment for improvement is to include some introductory material in the first 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. And also, although it might seem a tad too advanced, I do think maybe a brief introduction to what is known as Computational Trinitarianism / Trilogy 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.
Loading...
