(preliminary version)
Introduction to Theoretical Computer Science
Austin Melton
The lectures on theoretical computer science will cover the
classical areas of automata theory and complexity theory.
On the first day we will introduce and work problems involving
Turing machines and equivalent computational models. We will
end the first day with the essence and statement of Church's
Thesis. On the second day we will continue working with primitive
computational models and introduce noncomputability via examples.
On the third day, beginning again with a primitive computational
model, we will introduce complexity theory. Concepts in complexity
theory will be examined using a programming-like language, and on
the fourth day NP-completeness will be introduced and explained via
examples.