Concepts and definitions:

• What do we mean by computation? The algorithmic approach.
• The Halting Problem - the first uncomputable problem
• The 3 branches of theory of computation
• Alphabet, string, language
• Set operations (union, intersection, difference)

Skills:

• Know and understand the concepts and definitions listed above
• Know and understand all definitions in Chapter 0.
• How is {e} different from the empty language?
• How can languages be infinite if alphabets and strings are finite?

Assignment (for Mon, 1/23):

• Read textbook preface, "To the Student".
• Read textbook chapter 0.
• Read contents of CSE 237 web site.
• Do homework 0 (questionnaire).

Notes:

• In our class, everything will be based on definitions; all theorems will have proofs.
• e is a string of length 0