Course Description

Mathematical models for algorithmic processes, such as finite automata and Turing machines. Limitations of such models.

Course Syllabus

1. Finite-state machines
   1. Various models for finite-state machines
   2. Applications to neural nets
   3. Limitations of such models
2. Infinite machines
   1. Turing machines
   2. Variations of the Turing machine model
   3. Universal Turing machines
   4. Unsolvability of the halting problem
   5. Reducing one unsolvable problem to another
3. Other models of computation
   1. Primitive-recursive, total-recursive, and partial-recursive functions
   2. Enumeration of partial-recursive functions
   3. Other models as time permits
   4. Equivalence of the models of computation

Course Requirements