5
$\begingroup$

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.

  • 0
    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.2012-06-05

4 Answers 4