Ask HN: What is the smoothest way to study the theory of computation? For me, it is one of the most beautiful things ever in life. I read some books about it, but I never completely understood it. There are always jumps. And even after reading about the turing machine, I am like, so what? why this was revolutionary? It feels like as if most books are disconnected from the reader. |
I've read the regular languages section of Michael Sipser's "Introduction to the theory of Computation" and I really liked how it was written and how the material was presented. The first chapter is an introduction to the mathematical background you will need as well as quick primer on proofs. The following sections are "Automata and Languages" (regular/context free languages), Computability Theory (Turing machines, decidability & more) and Complexity Theory. The book flows like this: Sipser initially starts with an example or two to demonstrate an idea, and then formalises the idea with definitions or proofs. I'd recommend you have a look at it!
As for why Turing machines matter, from my understanding, this comes from the notion of Turing completeness. Essentially if it's possible to compute something, it can be done on a turning machine. Note that different computational models, such as the lambda calculus, can have the same level of power (Church-Turing thesis). An example of something that can't compute the things that a Turing machine can compute, is definite finite automata which are equivalent to regular languages/regexes. So, now we come to the most interesting bit, what are the limits of Turing machines? By understanding them, we understand what the limitations of our computational tools. This is where the halting problem comes in. It's not possible (on a Turing machine) to write a program that can figure out if a general program will terminate. This implies there are things that we can't really compute. There was a great answer of CS stack exchange regarding this: https://cs.stackexchange.com/a/32853
I hope that helps, let me know if you have any further questions.