Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
In University we used the Sipser text 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.
I strongly recommend the book Computational Complexity: A Modern Approach by Arora and Barak. When I took computational complexity at my Master level, the main textbook is Computational Complexity 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, but I really prefer the organization of Arora-Barak.
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.
I recommend Math and Computation 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.
I recommend "Computability and Logic" 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.
It is very hard to define what best means! Anyway, The nature of computation 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.
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.