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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.