**CSE 237 Lecture 1, 8/28/17
(introduction)**

**Concepts and definitions**:

- What do we mean by computation?
- The 3 branches of theory of computation
- The Halting Problem - the first uncomputable
problem, whether the program has infinite loops
- P = NP? it is not known if these two sets of problems
are equal
- History of the Theory of Computation Turing and the Entscheidungsprobleme
*Set, list, tuples**Alphabet, string, language*- An alphabet is a set of
characters
- A string is a list of
characters, i.e. apple is a shorthand for (a, p, p, l, e)
- A language is a set of
strings
- Character notation
*: a vs a vs. a* *Size of set, length of list.*- The
*empty string**ɛ*(i.e. a string of length 0) and the*empty set*(set of size 0) - Finite vs. infinite: alphabets and strings are always
finite, languages can be infinite
*Set operations: union, intersection, difference, cross-product*

**Skills**:

- Understand the concepts listed above
- Know definitions of terms (in italics) 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?
- Given two languages, what is their union? Intersection?
Difference? cross-product?

**Assignment (for Wed, 8/30):**

- Get the text book (Sipser, edition 3)
- Read textbook preface, "To the Student".
- Read textbook chapter 0.

**Notes**:

- In our class, everything will be based on definitions;
all theorems will have proofs.
- Please talk to me if you are not comfortable with any
of the material in Chapter 0.