(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.