The most important new concept in this lecture is the idea of recognizing languages. This idea is initially cumbersome to many students. If you do not become comfortable with this idea, you may find many of the later topics difficult.
The second most important concept is the idea that decision problems are as general as (the usual) input/output problems.
Reading: Ch 0
Exercises: Problems 0.1, 0.10-0.13 in Edition 3, 0.1, 0.10-0.12 in Edition 2 (Problem 0.11 in Edition 3 is not in Edition 2).
The most important concept in this class was the equivalence of the three forms of writing a function.
It is also good to remember why we are doing all this. We would like to make claims of the form "Model A can compute function every function B can, and further it can compute a function f, but model B cannot", which would imply model A is strictly more powerful than B. To simplify the math, what we will (typically) prove is "Model A accepts every language model B accepts and in addition a language L that model B cannot accept".
We saw several different types of proofs today. We also saw the Pigeonhole principle that we use quite a bit in this course. We then covered recursive definitions of sets.
We covered the (informal) definition of deterministic finite automata today. Please remember three crucial aspects -- finite alphabet, finite number of states and all possible edges drawn.