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 2017 Syllabus
Other Offerings Theory/offerings


Reading List

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.


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