What is a good introduction to turing machines, complexity classes, P=NP etc from a purely mathematical viewpoint? I want to know how computation relates to provability in mathematics, I need the details of how one relates arithemtical statements to turing machines. I am not interested in practical computing or programming. Also I want to know how to prove that some system is turing complete.
Mathematics of computation
-
0Maybe this question is too broad, in which caase eliminate comple$x$it$y$ classes and P=np from above. But I would like a general overview of mathematics of computation aswell. – 2012-06-05
4 Answers
You might try Michael Sipser's Introduction to the Theory of Computation.
-
2Sipser's book is an excellent read if you ever plan on writing a textbook; it is the best mathematics textbook I have ever read, and I would maintain this even if you convinced me that it isn't a mathematics textbook. – 2012-06-05
Try Computational Complexity by Papadimitriou.
A good place to start for the relationship between computability and provability is Computability and Logic by Boolos, Burgess, and Jeffrey. But it's not for the faint of heart - the content is dense, and the book has a lot more content than its thickness suggests.
For something more CS focused that will discuss Turing completeness and complexity, another great text is Introduction to Automata Theory, Languages, and Computation by Hopcroft and Ullman. Just skip chapters 2-7 which cover regular and context-free languages. Again, this book has a lot of content and is very well regarded.
-
0+1 I'm reading Hopcroft's book right now and it's extremely clear. – 2012-06-05
Another very good book is Computational Complexity: A Modern Approach, by Sanjeev Arora. See http://www.cs.princeton.edu/theory/complexity/. It is a very good book and not very expensive compared to Sipser's and Papadimitriou's book. The topics of the book cover a variety of topics in complexity theory. Also, there is a draft online, so you can check that if you want to see how the book is like.