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
5
$\begingroup$
reference-request
computer-science
-
0Maybe 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