6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This question is not a good fit for this site, because it it is too heavily dependent on opinion (and because "best" is ill-defined). Please read the faq and cs.stackexchange.com/help/dont-ask. $\endgroup$ – D.W. Jun 8 '14 at 21:32
  • $\begingroup$ Meta discussion about this question $\endgroup$ – Gilles 'SO- stop being evil' Jun 8 '14 at 23:43
  • 4
    $\begingroup$ If you don't want your question to be closed, don't post a question that should be closed! Book collections do not work on Stack Exchange — they fall into “what's your favorite book?” trap which is a type of question we do not want. I've edited your question into something that could fit here. It would help if you gave some information as to your background: what have you already studied? $\endgroup$ – Gilles 'SO- stop being evil' Jun 8 '14 at 23:46
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Sipser's book was first published in the late 1990s. That's nearly 20 years ago, which is not "relatively recent" in a field that's less than 80 years old! $\endgroup$ – David Richerby Jun 13 '14 at 5:46
  • $\begingroup$ The most recent edition (third) was published in only 2012. But yes, I did not realize the original edition was that old, so thank you for pointing that out. $\endgroup$ – gardenhead Jun 13 '14 at 6:26
7
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Concerning the 2nd edition of the H&U-book I happily quote Shallit in his book on formal languages: "In 2001, however, Hopcroft and Ullman released a second edition of their text that, in the words of one professor, “removed all the good parts.” In other words, their second edition is geared toward second- and third-year students, and omits nearly all the advanced topics suitable for fourth-year students and beginning graduate students." $\endgroup$ – Hendrik Jan Jun 9 '14 at 22:29
0
$\begingroup$

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:

  • Theory of Computation, first edition (Michael Sipser)

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:

  • Formal Languages, Automata, and Complexity (Brookshear)
  • Automata Theory, Languages, and Computation (first and second editions) from Hopcroft
  • Formal Language: A Practical Introduction (Adam Brooks Webber)

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.