CIT 596 Theory of Computation

Spring 2012, David Matuszek

The first half of this course was taught by Dr. Donna Dietz; here is her course web site, in HTML and on Blackboard.

The second half is being taught by me, Dave Matuszek.

**Office hours: **1 pm to 4 pm Mondays, 6:30 pm to 8 pm Tuesdays, 2 pm to 4 pm Wednesdays. However, the general rule is, if my door is open, I'm available.

Programming languages come and go, but the underlying theory has remained constant since I taught similar courses, back in in 1996 and 1999. At that time I wrote up an extensive set of course notes, which I expect to rely on. To some extent, I will also use the slides for an RPI course, at http://www.cs.rpi.edu/~moorthy/Courses/modcomp/.

More material may be added **here** and on Piazza as the semester progresses.

- Definitions of a Turing Machine
- A Turing Machine simulator (Python 2.6 or 2.7)
- Another Turing Machine simulator (Python 3) by Charles Milner (Thanks, Charlie!)
- Turing Machine assignment
- Turing Machine example (started in class)
- Exercises from 3/30 recitation
- Exercises from 4/6 recitation
- A proof that the Halting Problem is undecidable
- Diagonalization slides (PowerPoint)

- PCP simulation of Turing Machines
- PCP simulation of unrestricted grammars
- PCP assignment
- Exercises from 4/13 recitation
- PowerPoint lecture on Backtracking (from CIT 594)
- Backtracking article (in more detail)

- Analysis of Algorithms (PowerPoint)
- Converting a Turing Machine to an Unrestricted Grammar
- Exercises from 4/20 recitation
- PowerPoint lecture on NP-complete problems (assembled from various sources)

**Final exam: Monday, May 7, 9am-11am, in Moore 216.**