Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I want to study theory of computation on my own, so I am looking for books.
What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation?
Please post answers that describe a complete curriculum, explaining which chapters of each book are relevant at which stage of the course or self-study.
Introduction to the Theory of Computation by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I could browse through at my leisure. I ended up reading almost the whole book, even the chapters on topics I was already very familiar with, just because the book is such a joy to read. It's written at an introductory level, which means less notation, more exposition, and more intuition. The motivation behind every idea and theorem is crystal clear. He precedes every proof with a "proof idea" section that lays out the path the proof is going to take without getting into the gory details. The book covers Automata Theory, Computability Theory, and Complexity Theory to a satisfactory depth for an undergraduate level. I've read many textbooks in computer science and math, and this is probably my favorite.
For someone just getting started in Computer Science I would recommend
Douglas Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979.
It is a philosophy book discussing the meaning of truth, proof, and computability, (and self referential music and art and ... a bunch of other stuff) aimed at people with a little bit of mathematical sophistication (say at least a semester of college calculus) and was the book that inspired me to study computer science. It walks the reader through a complete proof of Gödel's incompleteness theorem.
I know I am going to get downvotes from the theorists for this, but I actually think that the first few chapters of most books on compilers do the best job of introducing basic automata theory (regular and context free languages, finite and pushdown automata). Aho, Sethi and Ullman (the red dragon book) does a particularly good job, but Appel's Modern Compiler Implementation in ML/Java/C book is decent and Cooper and Torczon's Engineering a Compiler is also great. The mathematics won't be particularly rigorous but the point is to get you to understand how to actually use and implement these things in real life. They won't teach you about Turing Machines, computability or decidability though.
The best book, the one that should be at the core of learning automata and computability, and the classic in this field for 20 years was
John E Hopcroft and Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
Sometimes known as "the loom book" because of the strange cartoon on the cover. It is appropriate for 4th year undergraduates or 1st year graduate students in computer science. It covers automata theory and computability. (It also ends with a couple of chapters on complexity theory, but that's not really its focus.) In about 2001 Addison Wesley started to "churn" the book (releasing new editions with modifications to kill the used book market.) I haven't looked at the 2nd (2001) or 3rd (2007) editions that added Rajeev Motwani as an author, so can't tell how or if they are improved over the original 1979 edition.
The book discussed in Stephen Bly's answer
Michael Sipser, Introduction to the Theory of Computation, Thompson, 1996 (now in 3rd edition, Cenage Leraning, 2012.)
is truly excellent. It is easier to read than Hopcroft and Ullman. Sipser is a good writer and explains everything extremely well. It doesn't go into the depth and range of topics that Hopcroft and Ullman, so may not include enough for a graduate course focused on automata and computability. Sipser is about 1/2 automata and computability and the other half is complexity theory (which he covers in more depth than Hopcroft and Ullman's first edition did.)
For a student who is taking a course in computability I recommend they read the following when they need to relax:
Raymond M Smullyan, The Lady or the Tiger?: and Other Logic Puzzles, 1982 (Dover reprint, 2009)
which ends with a series of chapters that requires you to do an undecidability proof to solve the puzzle.
Once you've got a good background on computability, you might like to continue on with a deeper look into other aspects of mathematical logic (including a rigorous treatment of Gödel's completeness and incompleteness theorems.) A good book for that might be
Herbert B Enderton, A Mathematical Introduction to Logic, 2/e, Academic Press, 2001.
I know this answer is late, but it might help the next person. I am not studying CS officially, but as a hobby. For theory of Computation, I started with:
The book was for me very uninspiring, it felt like a raw collection of random math theorems and its proofs. No intuition, no overview, no inspiration, no insight, no nothing.
After this, I ordered together:
Brookshear`s book was more clear than Sipser for me on the first chapters, but then got uninspired as well.
Hopcroft and Webber books arrived at the same time, and I tried reading them all. I was amazed that reviews on Amazon.com indicates that Sipser book is more acessible than Hopcroft, but I found exactly the opposite. Anyway, the Webber book was infinitely more inspiring than all of the other books, so I just took all others out of my shelf and read Webber`s entirely.
On the end, I got "Understanding computation" (Tom Stuart) as well. I was sure my quest was over with Webber's book, but I tried it out of curiosity anyway, and it was also nice for being intuitive. But I would prefer Webber`s if I had to pick only one.
The best mix for me is Webber+Stuart for intution, and Hopcroft for the math.
There are probably no worthy books. Danny Hillis`s book comes to mind, but much theory can be introduced with very little text. Binary arthimetic (with a little philosophy of number) and minimal Turing Machines, what?
It's understanding that takes time to grok how simple it is -- that's the job of the teacher, not a textbook (at least if you want to accomplish it in one semester). Only real-time, in the classroom, can you get a read on how to proceed with such a task.
