5
$\begingroup$

I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most interesting to me and I'm finally at the point where I can understand some of it. So my question is, where do I really begin to dive into his work? I have yet to take an official theory course, but I'm determined enough to go through important works that will help me get where I need. I'm currently reading his 1936 thesis and I find it mostly understandable, but I want to go deeper into the mathematics behind it all.

On a similar note, I think what I overall am interested in is complexity theory. I have some experience with basic abstract algebra, and some mathematical maturity. Can anyone list some books/papers to read, some introductions and some deeper, that can help me fully understand the implications of some topics, i.e. P=NP? How T.M.s were and are currently being used as foundational tools to prove and disprove ideas? I realize these are vague questions, but I want people to suggest books/papers that have been most influential to them that are related to these topics (or any other influential reads that one might have).

If I said anything incorrectly please feel free to correct me!

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ This is two completely separate questions and should be asked as such. Also, reading the original papers usually isn't the best way to learn a subject. Treatment of a subject improves over time as experience teaches us what's important and how to explain things well; in a field where textbooks exist, it's almost always best to learn the general material by reading a textbook. Papers are great if you need to know how a tiny thing works in full detail but not for giving overviews of whole fields. $\endgroup$
    – David Richerby
    May 19, 2015 at 7:48
  • $\begingroup$ agreed w DR about splitting this. fyi a neat crosscutting book (as you ask for) is the Turing Omnibus by Dewdney. the best book on P/ NP for beginners is now by Fortnow, "The golden ticket"... also drop by Computer Science Chat for this type of wondering... $\endgroup$
    – vzn
    May 19, 2015 at 17:53
  • $\begingroup$ @vzn "The golden ticket" is a popular science book. $\endgroup$
    – Yuval Filmus
    May 20, 2015 at 1:24
  • $\begingroup$ @yuval and, so what? (am anticipating your answer already & my counter response...) $\endgroup$
    – vzn
    May 20, 2015 at 1:41
  • $\begingroup$ @vzn Its target audience is people not willing to make the effort to actually study the area. $\endgroup$
    – Yuval Filmus
    May 20, 2015 at 2:28

1 Answer 1

Reset to default
7
$\begingroup$

Some popular books are Computational Complexity by Papadimitriou and Introduction to the Theory of Computation by Sipser. If you are very ambitious, you can also try Computational Complexity: A Modern Approach by Arora and Barak, which is an advanced textbook.

I would recommend against the historical approach of reading old papers. While some old papers are a good read (some of Turing's papers, Shannon's 1948 paper), old papers tend not to follow modern conventions, have a somewhat different focus, are less streamlined than modern treatments, could contain weaker results, and (in some cases) wrong results or at least wrong proofs. A good textbook is much preferable.

Regarding Turing machines, while they have some theoretical advantages in some circumstances, they are poor models of actual computers. Indeed, even in the theoretical computer science community, algorithms are usually described in the so-called RAM machine model which conforms much more closely to actual computers. Even historically speaking, Turing's model wasn't the first universal computation model, though (if I remember correctly) it was the first one that Gödel found convincing (Gödel's own general recursive functions, for example, predates it).

On your way to complexity theory, don't forget to stop at recursion theory (sometimes called computability theory), which had been practiced for a few decades before modern complexity theory started in the early 1970s. The usual course sequence indeed starts at (very basic) recursion theory and progresses to complexity theory.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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