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 1/8
Introduction
Regular expressions
Sec 1.3 (Read)
Slides
Annotated (LecA), Annotated (LecB)
1/9
Discussion:
Lecture review
1/10
DFA
Sec 1.1 (Read)
Slides
Annotated (LecA), Annotated (LecB)
1/11
Discussion:
Chapter 0 review
1/12
DFA design
Sec 1.1 (Read)
Slides
Annotated (LecA), Annotated (LecB)
HW Indiv0
Due 1/13 11pm
Pre-requisites
PDF, source, style
[Small typo fixed 1/8]
Pre-class survey
1/14
Review Quiz

Link
2 1/15
No lecture
MLK Day
HW Indiv1
Due 1/16 11pm
RegExp, DFA
PDF, source,
hw1.png, hw1.jff, style
Discussion:
Lecture review
1/17
Closure
Sec 1.1 (Read)
Slides
Annotated (LecA), Annotated (LecB)
1/18
Discussion:
RegExp, DFA
1/19
NFA
Sec 1.2 (Read)
Slides
Annotated (LecA), Annotated (LecB)
Group HW1
Due 1/20 11pm
RegExp, DFA
PDF, source, style
[Additional Hints added 1/17]
1/21
Review Quiz

Link
3 1/22
NFA to DFA
Sec 1.2 (Read)
Slides
Annotated (LecA), Annotated (LecB)
HW Indiv2
Due 1/23 11pm
Closure, NFA
PDF, source,
hw2_1.png, hw2_2.png, hw2_3.png, hw2_4.png, hw2_1.jff,
hw2_2.jff, hw2_3.jff, hw2_4.jff,
style
Discussion:
Lecture review
1/24
Equivalence
with RegExp
Sec 1.3 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
1/25
Discussion:
Closure, NFA
1/26
Non-regular sets
Sec 1.4 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
Group HW2
Due 1/27 11pm
Closure, NFA
PDF, source, style
hw2_5.png, hw2_5.jff,
1/28
Review Quiz

Link
4 1/29
Pumping Lemma
Sec 1.4 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
HW Indiv3
Due 1/30 11pm
Regular languages, PL
PDF, source,
hw3_1.png, hw3_2.png, hw3_3.png, hw3_4.png, hw3_1.jff,
hw3_2.jff, hw3_3.jff, hw3_4.jff,
style
Discussion:
Lecture review
1/31
PDA
Sec 2.2 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
2/1
Discussion:
Regular languages, PL
2/2
PDA Design
Sec 2.2 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
Group HW3
Due 2/3 11pm
Regular languages, PL
PDF, source,
(No new jff or png files), style
2/4
Review Quiz

Link
5 2/5
CFG
Sec 2.1 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
2/6
Discussion:
Lecture review
2/7
Exam 1
Practice questions
Discussion:
PDA, CFG
2/9
CFL
Sec 2.1 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
2/11
Review Quiz

Link
6 2/12
TMs: Formal def
Sec 3.1 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
HW Indiv4
Due 2/13 11pm
PDA, CFG
PDF, source, style
2/13
Discussion:
Lecture review
2/14
TMs: Implementation
Sec 3.1 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
2/15
Discussion:
Turing machines
2/16
TMs: High-level
Sec 3.1 (Read)
Slides,
Annotated (LecA), Annotated (LecB)
Group HW4
Due 2/17 11pm
PDA, CFG, CFL
PDF, source,
hw4_1.png, hw4_2.png, hw4_3.png, hw4_1.jff,
hw4_2.jff, hw4_3.jff
style
2/18
Review Quiz

Link
7 2/19
No lecture
Presidents' Day
HW Indiv5
Due 2/20 11pm
TM: formal, implementation
PDF, source, style
Discussion:
Lecture review
2/21
Church-Turing thesis
Sec 3.2 (Read)
Slides
2/22
Discussion:
Decidability, closure
2/23
Algorithms
Sec 3.3 (Read)
Slides
Group HW5
Due 2/24 11pm
TM: formal, implementation
PDF, source,
hw5TM.png, hw5TM.jff, style
2/25
Review Quiz

Link
8 2/26
Decidable langs
Sec 4.1 (Read)
Slides
2/27
Discussion:
Lecture review
2/28
Undecidability
Sec 4.2 (Read)
Slides
3/1
Discussion:
Lecture review
3/2
Exam 2
3/4
Review Quiz

Link
9 3/5
Reductions
Sec 5.1 (Read)
Slides
HW Indiv6
Due 3/6 11pm
High-level descriptions, decidability
PDF, source, style
Discussion:
Lecture review
3/7
Reductions
Sec 5.1 (Read)
Slides
3/8
Discussion:
Indiv6 review
3/9
Reductions
Sec 5.1 (Read)
Slides
Group HW6
Due 3/10 11pm
High-level descriptions, decidability
PDF, source, style
3/11
Review Quiz

Link
10 3/12
Time complexity
Sec 7.1 (Read)
Slides
HW Indiv7
Due 3/6 11pm
Undecidability, reductions
PDF, source, style
Discussion:
Lecture review
3/14
P vs. NP
Sec 7.1, 7.2 (Read)
Slides
Group HW7
Due 3/15 11pm
Undecidability, reductions
PDF, source, style
Discussion:
Review
3/16
Review
Sec 5.1 (Read)
Slides
Optional HW Indiv8
PDF, source, style
Final exam
Saturday 3/17
11:30am-2:29pm

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.

CSE 105 instructional team

We are looking forward to working with you this quarter.

Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/winter2018/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

Sipser, Michael   Introduction to the Theory of Computation, Third Edition (international)


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 operations (Wednesday)
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 (Friday)
Reading Page 48 (Figure 1.27 and description below it), Example 1.35 on page 52.
Optional extra practice Chapter 1 Exercise # 7, 9

Week 3

NFA to DFA (Monday)
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

NFA to RegExp (Wednesday)
Reading Example 1.56 on page 68.
Optional extra practice Chapter 1 Exercise # 7, 17

Nonregular sets (Friday)
Reading Page 77.
Optional extra practice Chapter 1 Exercise # 30

Week 4

Pumping Lemma (Monday)
Reading Example 1.75 (page 81) and Example 1.77 (page 82)
Optional extra practice Chapter 1 Exercise # 29, 30

PDA (Wednesday)
Reading Informal description of PDA on pages 111-112.

PDA Design (Friday)
Reading Example 2.16 (page 115) and Example 2.18 (page 116)
Optional extra practice Chapter 2 Exercise # 5

Week 5

Context-free grammars> (Monday)
Reading Intro to section 2.1 (pp. 102-103)
Optional extra practice Chapter 2 Exercise # 2,4

Context-free languages (Friday)
Reading Designing CFGs (pp. 106-107), Ambiguity Definition 2.7 (p. 108)
Optional extra practice Chapter 2 Exercise # 15

Week 6

Turing Machines (Monday)
Reading Pages 166-167 on differences between finite automata and Turing machines.

Turing machines (Wednesday)
Reading Example 3.7 on page 171, Example 3.9 page 173.<
Optional extra practice Chapter 3 Exercise # 2

Turing machines (Friday)
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 (Wednesday)
Reading Section 3.2, especially "Equivalence with other models" on page 181.
Optional extra practice Chapter 3 Exercise # 18

Computational problems (Friday)
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 (Monday)
Reading Section 4.1, Theorem 4.5 (page 197) and Theorem 4.8 (page 199)
Optional extra practice Chapter 4 Exercise # 3,5

Undecidability (Wednesday)
Reading Section 4.2 page 207-209
Optional extra practice Chapter 4 Exercise # 7,8