APM 5881: Theory of Computation
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.
Required background: a course in discrete mathematics.
John Martin, Introduction to languages and the theory of computation (third addition)
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!
Software that will be used
Separating words by automata
Godel's lost letter and P=NP