Is there a problem that NO computer can ever solve?

What resources are needed to solve a problem?

Are some problems harder than others?

In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after
Alan Turing,
who formalized the notion of "algorithm" *even before there were any physical computers*. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.

Upon successful completion of this course, you will be able to:

- Classify the computational complexity of a set of strings by determining whether it is regular, context-free, decidable, or undecidable.
- Give examples of sets in each of these classes (and prove them).
- Classify the computational complexity of a decision problem by translating it to a set of strings coding the problem.
- Use and design automata both formally and informally, including DFA, NFA, PDA.
- Deduce the language recognized by a machine or other formal description, including DFA, NFA, RegExp, PDA, CFG, TM.
- Prove invariants of computational classes, e.g. the class of regular languages is closed under ....
- Prove that certain models of computation are equivalent and translate between them algorithmically.
- Apply classical techniques including pumping lemma, determinization, diagonalization, and reduction to analyze the complexity of languages and problems.

Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/winter2019/cse105).

Our office hours and locations can be found in the calendar above.

For private questions to Prof. Minnes, you can reach me at minnes@eng.ucsd.edu

The **required** textbook for this course is

This book is available at the Bookstore for under $20 and is also on reserve in the library. You will need the book to complete pre-class reading before each lecture period.

To brush up on proofs, use: Richard Hammack, * Book of Proof, 2nd ed.* (available for download here)

An iClicker2 is also required, and is available for purchase at the bookstore. Register your iClicker here.