CSE 105: Introduction to Theory of Computability
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.
Syllabus
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
Textbook and supplies
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.