## APM 5881: Theory of Computation

#### Description

A study of what kinds of computation can, in principle, be accomplished by what kinds of computing devices, and how efficiently such computations can be done. Finite automata, pushdown automata, Turing machines, languages, grammars, undecidability, complexity theory, intractability.

#### Prerequisites

Required background: a course in discrete mathematics.

#### Textbook

John Martin, Introduction to languages and the theory of computation (third addition)
#### Course policies

For all the problems and concerns you might have you must talk to me. No makeups will
be given other then in case of documented emergencies. Cellular phones or any electronic equipment is NOT
allowed during lecture. No calculators of any kind are allowed.
Further, I do not tolerate any kind of academic dishonesty. Appropriate measures according to Oakland
University regulations will be take for any case of cheating or breaking other rules. Attendance is mandatory!

#### Detailed Syllabus

#### Software that will be used

#### Other readings

Separating words by automata
Godel's lost letter and P=NP