<p>I strongly recommend the book <a href="http://www.cs.princeton.edu/theory/complexity/" rel="noreferrer">Computational Complexity: A Modern Approach</a> by Arora and Barak. When I took computational complexity at my Master level, the main textbook is <a href="http://rads.stackoverflow.com/amzn/click/0201530821" rel="noreferrer">Computational Complexity</a> by Papadimitriou. But, maybe due to my background in Software Engineering, I found the writing in Papadimitriou challenging at times. Whenever I had problem understanding Papadimitriou's book, I simply went back to Sipser, or read the draft of Arora and Barak. </p>

<p>In retrospect, I really like Papadimitriou's book, and I often find myself looking up from this book. His book has plenty of exercises that are quite effective at connecting readers to research-level questions and open problems.</p>

<p>In any case, you should have a look at both Papadimitriou and Arora-Barak. People also suggest <a href="http://rads.stackoverflow.com/amzn/click/052188473X" rel="noreferrer">Oded Goldreich's textbook</a>, but I really prefer the organization of Arora-Barak.</p>

CC BY-SA 4.0
2021-10-21T01:42:58.830Z
I've heard Sipser is good for the core topics as taught in a typical intro algorithms class, and Arora-Barak is better for more advanced topics.
Neal Young
CC BY-SA 2.5
2010-12-04T14:06:42.853Z
2010-12-06T03:35:11.330Z
2010-12-06T03:35:11.330Z
Dai Le
<p>In my personal opinion, the Sipser book is still great. It's by far the most readable book on the subject.</p>

<p>The Sipser book also is an introduction, so coming back to it after some time isn't too trying on your memory.</p>

<p>That said, Papadimitrou's book is a good book for getting around the more advanced topics.</p>

CC BY-SA 2.5
2011-03-05T13:59:23.587Z
2011-03-05T13:59:23.587Z
Liam O'Connor
<p>I recommend <a href="https://www.math.ias.edu/avi/book" rel="nofollow noreferrer">Math and Computation</a> by Avi Wigderson if you're mainly interested in complexity theory. This is probably best supplemented by other books mentioned in this thread, as it's less rigorous. However the writing is excellent, and would be my go-to for a quick reference or enjoyable read.</p>

CC BY-SA 4.0
2020-07-02T14:02:09.187Z
2020-07-02T14:02:09.187Z
harwiltz
<p>It is very hard to define what <em>best</em> means! Anyway, <strong><a href="http://www.nature-of-computation.org/" rel="nofollow noreferrer">The nature of computation</a></strong> by Cris Moore and Stephen Mertens is very good. The book is nice to either get an introduction to the big ideas of the theory of computation if one is not interested too much in mastering the techniques, or to lift one's head of the track after learning many technicalities. It serves to my mind a quite different purpose than Arora &amp; Barack's book for instance.</p>

CC BY-SA 4.0
2020-07-02T15:31:10.823Z
2020-07-02T15:31:10.823Z
Bruno
<p>I recommend <a href="https://www.cambridge.org/core/books/computability-and-logic/440B4178B7CBF1C241694233716AB271" rel="nofollow noreferrer">&quot;Computability and Logic&quot;</a> by George S. Boolos and John P. Burgess. It's formal, rigorous and fairly thorough. It's a book on computability only, not covering computational complexity.</p>
<p>Notice that some other answers suggested books that focus on computational complexity instead of computability. For instance, (i) &quot;Computational Complexity: A Modern Approach&quot; by Arora and Barak; (ii) &quot;Computational Complexity&quot; by Christos H. Papadimitriou; and (iii) &quot;Computational Complexity: A Conceptual Perspective&quot; by Oded Goldreich.</p>

CC BY-SA 4.0
2020-07-01T23:12:24.327Z
2020-07-01T23:12:24.327Z
Alessander Botti Benevides
<p>See <a href="https://www.springer.com/gp/book/9781848824966" rel="nofollow noreferrer">Elements of Computation Theory</a> by Arindama Singh.</p>

CC BY-SA 4.0
2018-06-26T05:02:22.247Z
Is it possible to provide some more information about this book and why you recommend it?  Thank you!
Michael Wehar
CC BY-SA 4.0
2018-07-02T06:04:29.777Z
For any topic, it starts with the requirements informally, and then goes for a formalization very methodically. It includes lots of examples, exercises, and problems. Its notation is very intuitive. It does not sacrifices rigor. It discusses almost all of ToC results which are considered fundamental.
Sunita
CC BY-SA 4.0
2018-06-20T05:04:22.927Z
2021-10-20T18:46:43.600Z
2021-10-20T18:46:43.600Z
Sunita
<p>For Automata Theory, get the 1979 edition of &quot;Automata Theory, Languages and Computation&quot;. Unlike the 3rd edition, it is not an introductory book, but goes into lots of detail about all the specifics of automata theory. It covers things like trios, cones, abstract families of languages, etc. that most undergrad books skip.</p>

CC BY-SA 4.0
2021-10-21T18:10:11.790Z
2021-10-21T18:10:11.790Z
Joey Eremondi
<p>In University we used the <a href="https://en.wikipedia.org/wiki/Introduction_to_the_Theory_of_Computation" rel="nofollow noreferrer">Sipser text</a> and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression.  I borrowed that book and don't have one in my collection, so I need one.  So to the question, are there are any other books which could be seen as better and possibly more complete?</p>
<p>I didn't see a community wiki section here, so I couldn't note it as such.</p>

CC BY-SA 4.0
2021-10-26T06:57:23.357Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/130857/discussion-on-question-by-recursion-what-is-the-best-text-of-computation-theory).
Bjørn Kjos-Hanssen
<reference-request><soft-question><computability><books>
What is the best text of computation theory/theory of computation?
Recursion
# What is the best text of computation theory/theory of computation?

(Asked by: username_0 on 2010-12-04)

In University we used the [Sipser text](https://en.wikipedia.org/wiki/Introduction_to_the_Theory_of_Computation) and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and don't have one in my collection, so I need one. So to the question, are there are any other books which could be seen as better and possibly more complete?

I didn't see a community wiki section here, so I couldn't note it as such.

**Tags:** reference-request, soft-question, computability, books

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/130857/discussion-on-question-by-recursion-what-is-the-best-text-of-computation-theory).  

---

## 7 answers

### Answer by username_2 on 2010-12-04. Score: 14

I strongly recommend the book [Computational Complexity: A Modern Approach](http://www.cs.princeton.edu/theory/complexity/) by Arora and Barak. When I took computational complexity at my Master level, the main textbook is [Computational Complexity](http://rads.stackoverflow.com/amzn/click/0201530821) by Papadimitriou. But, maybe due to my background in Software Engineering, I found the writing in Papadimitriou challenging at times. Whenever I had problem understanding Papadimitriou's book, I simply went back to Sipser, or read the draft of Arora and Barak.

In retrospect, I really like Papadimitriou's book, and I often find myself looking up from this book. His book has plenty of exercises that are quite effective at connecting readers to research-level questions and open problems.

In any case, you should have a look at both Papadimitriou and Arora-Barak. People also suggest [Oded Goldreich's textbook](http://rads.stackoverflow.com/amzn/click/052188473X), but I really prefer the organization of Arora-Barak.

> **Comments:**
> **username_3**: I've heard Sipser is good for the core topics as taught in a typical intro algorithms class, and Arora-Barak is better for more advanced topics.  

---

### Answer by username_4 on 2011-03-05. Score: 8

In my personal opinion, the Sipser book is still great. It's by far the most readable book on the subject.

The Sipser book also is an introduction, so coming back to it after some time isn't too trying on your memory.

That said, Papadimitrou's book is a good book for getting around the more advanced topics.


---

### Answer by username_5 on 2020-07-02. Score: 3

I recommend [Math and Computation](https://www.math.ias.edu/avi/book) by Avi Wigderson if you're mainly interested in complexity theory. This is probably best supplemented by other books mentioned in this thread, as it's less rigorous. However the writing is excellent, and would be my go-to for a quick reference or enjoyable read.


---

### Answer by username_6 on 2020-07-02. Score: 1

It is very hard to define what *best* means! Anyway, **[The nature of computation](http://www.nature-of-computation.org/)** by Cris Moore and Stephen Mertens is very good. The book is nice to either get an introduction to the big ideas of the theory of computation if one is not interested too much in mastering the techniques, or to lift one's head of the track after learning many technicalities. It serves to my mind a quite different purpose than Arora & Barack's book for instance.


---

### Answer by username_7 on 2020-07-01. Score: 1

I recommend ["Computability and Logic"](https://www.cambridge.org/core/books/computability-and-logic/440B4178B7CBF1C241694233716AB271) by George S. Boolos and John P. Burgess. It's formal, rigorous and fairly thorough. It's a book on computability only, not covering computational complexity.

Notice that some other answers suggested books that focus on computational complexity instead of computability. For instance, (i) "Computational Complexity: A Modern Approach" by Arora and Barak; (ii) "Computational Complexity" by Christos H. Papadimitriou; and (iii) "Computational Complexity: A Conceptual Perspective" by Oded Goldreich.


---

### Answer by username_8 on 2018-06-20. Score: 1

See [Elements of Computation Theory](https://www.springer.com/gp/book/9781848824966) by Arindama Singh.

> **Comments:**
> **username_9**: Is it possible to provide some more information about this book and why you recommend it?  Thank you!  
> **username_8**: For any topic, it starts with the requirements informally, and then goes for a formalization very methodically. It includes lots of examples, exercises, and problems. Its notation is very intuitive. It does not sacrifices rigor. It discusses almost all of ToC results which are considered fundamental.  

---

### Answer by username_10 on 2021-10-21. Score: 0

For Automata Theory, get the 1979 edition of "Automata Theory, Languages and Computation". Unlike the 3rd edition, it is not an introductory book, but goes into lots of detail about all the specifics of automata theory. It covers things like trios, cones, abstract families of languages, etc. that most undergrad books skip.


---

