Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite
3

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.

share|improve this question
Maybe this question is too broad, in which caase eliminate complexity classes and P=np from above. But I would like a general overview of mathematics of computation aswell. – IlDuce Jun 5 '12 at 0:58

4 Answers

up vote 6 down vote

You might try Michael Sipser's Introduction to the Theory of Computation.

share|improve this answer
Sipser's book is more focused on CS, and uses some nonstandard terminology like "mapping reducibility". It's not a bad book, but I would recommend something else for someone interested in mathematics. – Carl Mummert Jun 5 '12 at 2:11
2  
Sipser'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. – Qiaochu Yuan Jun 5 '12 at 4:13
up vote 2 down vote

Try Computational Complexity by Papadimitriou.

share|improve this answer
up vote 2 down vote

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.

share|improve this answer
+1 I'm reading Hopcroft's book right now and it's extremely clear. – becko Jun 5 '12 at 3:01
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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