CSC445 - Models of Computation

Spring 2014


Dr. Lutz Hamel
Tyler, Rm 251
Office Hours: Tuesday 12:15-1:15pm, Wed 2-3pm


Younghun Chae
Tyler, Rm 134
Office Hours: TBA
Email Address:


Computation and algorithms seem to occur naturally in our daily lives. Consider counting change or following a recipe to make your favorite dish. The art of programming takes this to the limit by formally encoding computations and algorithms for a machine to follow. What are the limits of this algorithmic approach? Are there mathematical objects that cannot be computed by a machine via an algorithm? If we can express a computation via an algorithm how long would it take to compute? How much space would the computation consume?

In this course we will investigate many of these interesting questions. We start with simple models of computations such as the finite state machine and the push down automaton. As our main tool we will use an idealized general purpose computer invented by Alan Turing: the Turing Machine. This idealized machine allows us to study the limits of computability and the complexity of computations without having to worry too much about actual hardware.

The goals of the course are:


** Final Exam: Tuesday May 6, 8-11am in Crawford 223. Comprehensive, open book/open notes **

[4/17/14] posted assignment #8 so you can get started -- we will cover chap 18 next week.
[4/3/14] Posted assignment #7
[3/26/14] Posted assignment #6
[3/24/14] Posted assignment #5
[3/12/14] posted all solutions on the web
[2/26/14] No class Tuesday 3/4
[2/26/14] posted assignment 4.
[2/18/14] posted assignment 3.
[2/6/14] Posted assignment 2.
[1/28/14] Posted assignment 1.
[1/17/14] Welcome!

Documents of Interest:


In order to receive full credit for your assignments they have to be typewritten.  Hand drawn diagrams are acceptable. Email submissions are not acceptable.