CSC381 - Theory of Computation

From Maryville College CS Wiki
Jump to: navigation, search

Course Information

Code CSC3810
Name Theory of Computation
Credit(s) 3
Prerequisites CSC2310
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 2015 Syllabus
Other Offerings Theory/offerings


  • Easy Problems are problems which you are required to complete. These will be posed in class, and posted here. Each one of these problems will have a definite due date.
  • Proposed Problems are more difficult problems. These will be posted here periodically, and will never expire. You should attempt all of these problems before the end of the semester. Also, you will be proposing problems here. See the page for more details on how to post problems to get correct attribution.
  • Reading Schedule contains a schedule of readings. (It's not just a clever title.) This will be updated throughout the semester, so check back frequently.
  • Paper Submission Paper submission guidelines for the two term papers.
  • Past papers can be viewed on the MCTOC page.

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.

Non Fiction

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.
On formally undecidable propositions of Principia Mathematica and related systems I 
I came across another translation of this paper, it is more recent and uses more modern translation and so you may find it easier than the one in The Undecidable. Click Here to read it.


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.)

Subpages for this Course