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!
Asked By : m1cky22
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42739
0 comments:
Post a Comment
Let us know your responses and feedback