CSC381 - Theory of Computation
|Name||Theory of Computation|
|Offered||Fall of every odd numbered year. (2015, 2017, etc.)|
|Catalog Description||A study of theoretical models of computing, including finite state machines, pushdown automata, context-free grammars, and Turing machines. The concepts of decidability, complexity theory, and NP-Completeness will be studied in depth.|
|Syllabus||Fall 2017 Syllabus|
- Problem Set 1 - Cantor
- Problem Set 2 - Hilbert
- Probelm Set 3 - Gödel 1
- Problem Set 4 - Gödel 2
- Problem Set 5 - Church 1
- Paper Submission Guidelines
- On a Property of the Set of Real Algebraic Numbers. Georg Cantor 1874. Translated by William Ewald.
- On an Elementary Question in the Theory of Manifolds. Georg Cantor 1891. Translated by William Ewald.
- The New Grounding of Mathematics. First Report. David Hilbert 1922. Translated by William Ewald.
- The Logical Foundations of Mathematics. David Hilbert 1923. Translated by William Ewald.
- On Formally Undecidable Propositions of Principia Mathematica. Kurt Godel 1931. Translated by Meltzer.
- Alternate translation of Sections 1 and 2. Kurt Godel 1931. Translated by Martin Hirzel.
- An Unsolvable Problem of Elementary Number Theory. Alonzo Church April 1936
- On Computable Numbers With an Application to the Entscheidungsproblem. Alan Turing. November 1936
- Three Models for the Descritpion of Language. Noam Chomsky 1956
- On Certain Formal Properties of Grammars. Noam Chomsky 1959
- The complexity of Theorem-Proving Procedures. Stephen Cook 1971
- Universal Sequential Search Problems. Leonid Levin 1972
- The P Versus NP Problem. Stephen Cook
Suggestions and Advice
The hardest part of this class will be figuring out a way to attack a problem. This is, unfortunately, not a trivial task! I've found that what helps me do this sort of work is to relax a little before attempting. You may even consider taking up meditation. My general bullet-point style advice for proof writing is:
- Work in a place where you can concentrate. For some people this requires silence, for others you basically need an all out rave. Figure out which is you and pursue that option.
- Give yourself lots of lead time. It will likely take a few hours for you to make meaningful progress, so make sure your study and work sessions allow for this.
- Set a timer to make sure you don't get trapped in math land. Math land is a wonderful place filled with many wonderful objects and ideas. Unfortunately, when you are in a state of deep contemplation it can mess with your sense of time. Having an objective outside device will help to make sure that you don't look up to discover that 15 hours have passed.
- If you get stuck, don't force the issue. If you cannot get unstuck within 20 minutes, that means your math writing session has come to an end. Some things you can try to get yourself unstuck include:
- Read more related papers. Sometimes your new ideas are lurking between the lines of your textbook.
- Read unrelated papers. Overstimulation may be the culpret.
- Solvitur ambulando. Many interesting proofs live in the Maryville College Woods. Go out there and find them.
- Don't sweat it if you can't get unstuck. Just go do something else. Your brain will work on your problems in the background and when you return, you'll find an answer.
Suggested Additional Reading and/or Viewing
Further exploration of this kind of mathematics is a lot of fun! Here are some ideas to give you some further information.
- Godel's Proof by Ernest Nagel and James Newman.
- This is an analysis and commentary on Godel's incompleteness theorems based on the paper which we read in class. This is a great read, and it gives a lot of insight into Godel's logic as well as the importance of this work.
- The Annotated Turing by Charles Petzold
- This is a step by step treatment of Turing's most famous paper. The text of the paper is woven throughout the explanation of it's implications.
- One Two Three ... Infinity by George Gamow
- This is a classic book on the subject of infinity. It was written in the 1940's, and was the book which popularized David Hilbert's grand hotel paradox.
- The Godelian Puzzle Book by Raymond M. Smullyan.
- A wonderful puzzle book with problems that relate to the foundations of mathematics. This one is a fun way to spend a few weekends.
- What is the Name of this Book by Raymond M. SMullyan
- Another excellent puzzle collection. Really, just read all of Smullyan's books.
- Alan Turing: The Enigma by Andrew Hodges
- This is a biography of Allan Turing. It is widely considered to be a very accurate account of Turing's life, and it was the inspiration behind two movies. One movie 'Breaking the Code' was excellent, the other one, The Immitation Game leaves much to be desired.
- Breaking the Code
- A television adaptation of a play by the same name. Derek Jacobi gives an amazing performance as Turing. There's a great exchange in this one that pertains to the first few weeks of our class. Also, it is available on Hulu.
- A Madman Dreams of Turing Machines by Janna Levin
- This is a fictional telling of the lives of Turing and Godel. A must read for any student of mathematics!
- Cryptonomicon by Neal Stephenson
- This is a cyberpunk-style novel which features Alan Turing as a fictional character. The characterization is true to life, but all of the events are pretty much fictional. Cryptonomicon alternates between World War II scenes and modern scenes. It is a lot of fun!
- This is a charming little romantic comedy from 1994. Kurt Godel is among the scientists who help Albert Einstein in uniting Meg Ryan and Tim Robbins. (Of course, this is completely fictional.)