This course introduces students to some of the fundamental ideas in theoretical computer science: functions and relations, formal languages, finite automata, regular languages, context-free grammars, context-free languages, push-down automata, pumping lemmas, Turing machines, the Church-Turing thesis, recursive and recursively enumerable languages, the Chomsky hierarchy, the halting problem and other unsolvable decision problems, problem reducibility, and fundamental computational complexity classes.