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.
Weekly Schedule (Lec A and Lec B)
| Week | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday |
|---|---|---|---|---|---|---|---|
| 1 | 4/2 Introduction Regular expressions Sec 1.3 (Read) Slides Annotated (LecA), Annotated (LecB) |
4/3 | 4/4 DFA Sec 1.1 (Read) Slides Annotated (LecA), Annotated (LecB) |
4/5 | 4/6 DFA design Sec 1.1 (Read) Slides Annotated (LecA), Annotated (LecB) |
HW Indiv0 Due 4/7 11pm Pre-requisites PDF, source, style Pre-class survey |
Review Quiz Due 4/8 11pm Review Quiz Link (Stays available for practice) |
| 2 | 4/9 Closure Sec 1.1 (Read) Slides Annotated (LecA), Annotated (LecB) |
HW Indiv1 Due 4/10 11pm RegExp, DFA PDF, source, DFA_HW1.png, DFA_HW1.jff, style |
4/11 NFA Sec 1.2 (Read) Slides Annotated (LecA), Annotated (LecB) |
4/12 | 4/13 NFA to DFA Sec 1.2 (Read) Slides Annotated (LecA), Annotated (LecB) |
Group HW1 Due 4/14 11pm RegExp, DFA PDF, source, DFA_HW1.png, DFA_HW1.jff, style (Updated 4/5/18) |
Review Quiz Due 4/15 11pm Link (Stays available for practice) |
| 3 | 4/16 Equivalence with RegExp Sec 1.3 (Read) Slides, Annotated (LecA), Annotated (LecB) |
HW Indiv2 Due 4/17 11pm Closure, NFA PDF, source, closure_HW2_1.jff, closure_HW2_1.png, closure_HW2_1.jff, closure_HW2_1.png, closure_HW2_1.jff, closure_HW2_1.png, closure_HW2_1.jff, closure_HW2_1.png, closure_HW2_1.jff, closure_HW2_1.png, closure_HW2_1.jff, closure_HW2_1.png, style |
4/18 Non-regular sets Sec 1.4 (Read) Slides, Annotated (LecA), Annotated (LecB) |
4/19 | 4/20 Pumping Lemma Sec 1.4 (Read) Slides, Annotated (LecA), Annotated (LecB) |
Group HW2 Due 4/21 11pm Closure, NFA PDF, source, style |
Review Quiz Due 4/22 11pm Review Quiz Link (Stays available for practice) |
| 4 | 4/23 Review Chapter 1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
4/24 | 4/25 Exam 1 Practice questions |
4/26 | 4/27 PDA Sec 2.2 (Read) Slides, Annotated (LecA), Annotated (LecB) |
4/28 | Review Quiz Due 4/29 11pm Review Quiz Link (Stays available for practice) |
| 5 | 4/30 PDA Design Sec 2.2 (Read) Slides, Annotated (LecA), Annotated (LecB) |
HW Indiv3 Due 5/1 11pm Nonregular languages, PDA PDF, source, PDA_HW3.jff, PDA_HW3.png,style |
5/2 CFG Sec 2.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
5/3 | 5/4 CFL Sec 2.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
Group HW3 Due 5/5 11pm Nonregular languages, PDA PDF, source, style |
Review Quiz Due 5/6 11pm Review Quiz Link (Stays available for practice) |
| 6 | 5/7 TMs: Formal def Sec 3.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
HW Indiv4 Due 5/8 11pm CFG, CFL PDF, source, DFA_HW4.jff, DFA_HW4.png,style |
5/9 TMs: Implementation Sec 3.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
5/10 | 5/11 TMs: High-level Sec 3.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
Group HW4 Due 5/12 11pm CFG, CFL PDF, source, PDA2_HW4.jff, PDA2_HW4.png,style |
Review Quiz Due 5/13 11pm Review Quiz Link (Stays available for practice) |
| 7 | 5/14 Church-Turing thesis Sec 3.2,3.3 (Read) Slides, Annotated (LecA), Annotated (LecB) |
HW Indiv5 Due 5/15 11pm TM: formal, implementation PDF, source, TMex1_HW5.jff, TMex1_HW5.png, TMex2_HW5.jff, TMex2_HW5.png, TMex3_HW5.jff, TMex3_HW5.png, TMex4_HW5.jff, TMex4_HW5.png, TMex5_HW5.jff, TMex5_HW5.png,style |
5/16 Decidable problems Sec 3.3,4.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
5/17 | 5/18 Decidable problems Sec 4.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
Group HW5 Due 5/19 11pm TM: formal, implementation PDF, source, TM_HW5.jff, TM_HW5.png, TM2_HW5.jff, TM2_HW5.png, TM3_HW5.jff, TM3_HW5.png, style |
Review Quiz Due 5/20 11pm Review Quiz Link (Stays available for practice) |
| 8 | 5/21 Decidable langs Sec 4.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
5/22 | 5/23 Exam 2 Practice questions |
5/24 | 5/25 Undecidability Sec 4.2 (Read) Slides, Annotated (LecA), Annotated (LecB) |
Review Quiz Due 5/27 11pm Review Quiz Link (Stays available for practice) |
|
| 9 | 5/28 No class Memorial Day |
HW Indiv6 Due 5/29 11pm High-level descriptions, decidability PDF, source, style |
5/30 Mapping reductions Sec 5.3 (Read) Slides, Annotated (LecA), Annotated (LecB) |
5/31 | 6/1 Mapping reductions Sec 5.3 (Read) Slides, Annotated (LecA), Annotated (LecB) Last slide fixed 6/6/18 |
Group HW6 Due 6/2 11pm High-level descriptions, decidability PDF, source, style Q3b not for credit |
Review Quiz Due 6/3 11pm Review Quiz Link (Stays available for practice) |
| 10 | 6/4 Time complexity Sec 7.1 (Read) Slides, Annotated (LecA), Annotated (LecB) |
Group HW7 Due 6/5 11pm Undecidability, reductions PDF, source, style |
6/6 P vs. NP Sec 7.1, 7.2 (Read) Slides, Annotated (LecA), Annotated (LecB) |
6/8 Review Sec 5.1 (Read) Slides, Annotated (LecA), Annotated (LecB) Optional HW Indiv8 PDF, source, style Due 6/16 11pm Review Quiz Link |
Final exam Saturday 6/9 8:00am-11:00am Practice questions |
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.
.JPG)
Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/spring2018/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
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.
Pre-class reading and post-class practice questions
Week 1
Pre-requisites
Reading Sec 0.2, 0.3, 0.4: In particular, review the definitions of set, element, subset,
infinite set, proper subset, natural numbers, integers, empty set, union, intersection, complement, sequence,
Cartesian product, function, domain, range, graph, self-loop, alphabet, symbol, string over an alphabet,
length, empty string, substring, concatenation, lexicographic order, shortlex/string order, prefix,
proof by contradiction.
Optional extra practice: Chapter 0 Exercise # 1, 2, 3, 4, 5, 6.
Regular expressions
Reading Sec 1.3: Def 1.52 of regular expressions (p. 64), example 1.53 (p. 65)
Optional extra practice: Chapter 1 Exercise # 20
DFA
Reading Sec 1.1: Figure 1.4 (p. 34), Definition 1.5 (p. 35)
Optional extra practice: Chapter 1 Exercise # 1, 2, 3
Week 2
Closure
Reading Pages 45-47 (paragraph before Theorem 1.25 and Theorem 1.25 and its proof).
Optional extra practice Chapter 1 Exercise # 4, 5
Nondeterminism
Reading Page 48 (Figure 1.27 and description below it), Example 1.35 on page 52.
Optional extra practice Chapter 1 Exercise # 7, 9
NFA to DFA
Reading Pages 55 paragraph that starts "Recall the "reader as automaton"..." and Example 1.41 on pages 56-58..
Optional extra practice Chapter 1 Exercise # 13, 14, 16
Week 3
NFA to RegExp
Reading Example 1.56 on page 68.
Optional extra practice Chapter 1 Exercise # 7, 17
Nonregular sets
Reading Page 77.
Optional extra practice Chapter 1 Exercise # 30
Pumping Lemma
Reading Example 1.75 (page 81) and Example 1.77 (page 82)
Optional extra practice Chapter 1 Exercise # 29, 30
Week 4
PDA
Reading Informal description of PDA on pages 111-112.
Week 5
PDA Design
Reading Example 2.16 (page 115) and Example 2.18 (page 116)
Optional extra practice Chapter 2 Exercise # 5
Context-free grammars>
Reading Intro to section 2.1 (pp. 102-103)
Optional extra practice Chapter 2 Exercise # 2,4
Context-free languages
Reading Designing CFGs (pp. 106-107), Ambiguity Definition 2.7 (p. 108)
Optional extra practice Chapter 2 Exercise # 15
Week 6
Turing machines: formal definition
Reading Pages 166-167 on differences between finite automata and Turing machines.
Turing machines: implementation
Reading Example 3.7 on page 171, Example 3.9 page 173.<
Optional extra practice Chapter 3 Exercise # 2
Turing machines: high-level
Reading Bottom of page 166 and top of page 167 (high-level and implementation level definitions of M1),
then terminology for describing Turing machines pages 184-185
Optional extra practice Chapter 3 Exercise # 7,8
Week 7
Variants of Turing machines
Reading Section 3.2, especially "Equivalence with other models" on page 181.
Optional extra practice Chapter 3 Exercise # 18
Computational problems
Reading Format and notation for describing Turing machines, middle of page 185
Optional extra practice Chapter 3 Exercise # 15, 16; Chapter 4 Exercise # 1
Week 8
Decidable problems
Reading Section 4.1, Theorem 4.5 (page 197) and Theorem 4.8 (page 199)
Optional extra practice Chapter 4 Exercise # 3,5
Undecidability
Reading Section 4.2 page 207-209
Optional extra practice Chapter 4 Exercise # 7,8
Week 9
Mapping reductions: definitions
Reading Section 5.3 Definition 5.17, Definition 5.20
Mapping reductions: examples
Reading Section 5.3 Example 5.24, Theorem 5.22
Optional extra practice Chapter 5 Exercise # 18a,b (without Rice's theorem)
Week 10
Complexity: P and NP
Reading Section 7.1 example at the top of page 279, Theorem 7.8, Theorem 7.11; Section 7.2 Definition 7.12, Theorem 7.14;
Section 7.3 Theorem 7.24
Optional extra practice Chapter 7 Exercise # 6, 7, 8, 10
NP-completeness
Reading Section 7.1 example at the top of page 279, Theorem 7.8, Theorem 7.11; Section 7.2 Definition 7.12, Theorem 7.14;
Section 7.3 Theorem 7.24
Optional extra practice Chapter 7 Exercise # 5, read through sample solution of 28