EECS2001
EECS 2001:
Introduction to the Theory of Computation
Jeff's Syllabus
Passion: Thank you for working with me. I do love teaching.
I have been tightening up this material by
replacing harder proofs
with more casual chats .
This term, we will chat some more .
Please let me know if you think I should get future students to
watch a different version than I have indicated.
The plan for the extra time is to do more Machine Learning this
term.
.
Jeff,
Readme,
*
Course Info
*,
Times,
Dates,
Course Description,
Notes,
Mental
Health,
EClass,
Zoom,
Forum,
Partner,
Old
Videos Zip,
New
Videos
About Course:
This course is useful for a student interested in the
theoretical aspects of computer science.
Request:
Jeff tends to talk too fast. Please help him go
pole pole slowly.
0 Intro:
(ppt)
00
1:35
Administrative Details
01
30
Summary of Course
WATCH ABOVE BY WED SEPT 8 4pm.
1 Predicate Logic:
(ppt)
(Math1090
)
(Before a student can understand or prove anything in mathematics, it
is essential to first be able to represent it in first order logic.)
Logic Questions &
Solutions
2 Models of Computability:
(ppt)
(Historic and mathematical ways of modeling machines for computing.)
01
1:03
History & Overview
01
Church's Thesis
01
Goto vs Loop Models
02
35
Table Look Up and TM
03
36
Turing Machines
04
1:48
Levels of Abstraction
WATCH ABOVE BY MONDAY SEPT 13 4pm.
05
1:03
Sum mod 100 Example
06
17
Compile Time vs Run Time
06
17
Steps for writing a TM from Java code
07
48
3:23
Shifting Example
07
80
30
Insertion Sort
08
16
Adding Example (single tape)
08
Adding Example (multi tape)
08
Table Lookup Example
09
4
Single vs Multi Tape TMs
09
5
Java to TM
09
5
Constant vs Finite vs Infinite
10
14
Universal TM
11
20
Other Models of Computation
12
4
Languages, Machines, and Classes
WATCH ABOVE by Monday Sept 20 4pm.
TEST 1: Thur Sept 23 8:00am- Fri 11:00am, with partner
3 Deterministic Finite Automata - Machine:
(ppt)
(Useful for modeling simple machines eg coke machine.)
01
14
Read-Once and Bounded Memory
02
Constant Memory
03
6
Loop Invariants
04
4
Code with Simple Loop
05
10
Deterministic Finite Automata
06
Path Through Graph
07
19
Focus on States
08
10
DFA: Formal Definition
09
6
10
DFA "knowing" and distinguishable strings
10
25
(Extended) Regular Expressions
11
16
Parsing with Regular Expressions
12
Examples:
1
27
Simple examples
2
11
0*1* vs 0n1n
3
30
Mod Counting
4
4
Any Finite Language
5
5
Adding two Integers
6
7
Calculator
7
5
Syntax Processor
**** REARANGED *** WATCH ABOVE by Monday Sept 27 4pm.
14
Nondeterministic Finite Automata:
1
24
Fairy God Mother Story
2
13
Contains 0101
3
73
Restaurant
4
24
Middle Third
15
Proofs:
1
15
L(M)=L
2
11
L(M)=L Method 2
3
44
Proof L(M)=L Eg 2
90
1:20
DFA Review
WATCH ABOVE by Monday Oct 4 4pm.
TEST 2: Thur Oct 7 8:00am- Fri 11:00am, with partner
4 Deterministic Finite Automata and Regular Languages
Classes:
(ppt,
longer)
(We classify computational problems based on the amount of resources
used to compute them.)
01
19
37
70
Closure Properties
02
10
Complexity Classes
03
11
8
NFA to DFA
04
19
19
Extended Regular to DFA (short/Eg)
05
1
23
20
NFA to Regular Expression (short/long)
06
7
Complex Conversion Example
07
39
74
50
1:08
The Bumping Lemma
90
36
Review
WATCH ABOVE by Monday Oct 18 4pm.
5 Context Free Grammars:
(ppt)
(Useful for modeling and parsing languages.)
01
29
Context Free Grammars
Chomsky Hierarchy
Ambiguity
Java Like Example
Human Languages
02
22
Union, Concat, Spew, & Plop
03
13
Recursion
04
8
28
Parsing/Compiling (short/long)
05
36
Not Closed under Complement
06
11
24
Closure and Proof Big Enough (short/long)
07
3
NFA to Context Free Grammar
08
4
18
Push Down Automata (short/long)
09
5
14
Parsing using Dynamic Programming (short/long)
10
12
41
TM to Context Sensitive Grammars (short/long)
WATCH ABOVE by Monday Oct 25 4pm.
TEST 3: Thur Oct 28 8:00am- Fri 11:00am, with partner
Computing (Math 1090)
(ppt):
Computational problems, machines, and inputs
67
Computing
∃ Alg A, ∀ Inputs I, A(I)=P(I)
39
57
7
- Coding Phase vs Execution Phase
∃ Alg A, ∃ # k, ∀ Inputs I, ∃ time t,
A(I)=P(I) & Lines(A,I)=k & Time(A,I)=t
27
58
- Compiling Java to TM
∀ Java Programs J, ∃ TM M, ∀ input I,
J(I)=M(I)
Computable vs Uncomputable
∃M∀I M(I)=P(I)
vs ∃P∀M∃I M(I)≠P(I)
54
Time Complexity
∃M∃c∀I M(I)=P(I) and Time(M,I)≤
|I|^{c}
44
Classifying Functions
f(n)∈O(g(n)) ≡
∃c∃n_{0}∀n≥n_{0}
f(n) ≤ cg(n)
Coding Phase vs Execution Phase
Before input is chosen vs after
6
Table Look Up vs TM
∀k∃M_{table}∀x,y≤k M_{table}(x,y)=x×y
vs
∃M∀x,y M(x,y)=x×y
26
Probabilistic Algorithms
∃M∀I Pr_{R}[M(I,R)≠P(I)]
≤ 2^{-|R|}
5
Universal TM
∃ TM M_{U}, ∀ TM M, ∀ input I,
M_{U}(M,I) = M(I)
63
Hugely Expressive
There is a first order logic sentence Compute(J,I,y)
that states computer program J on input I outputs y.
Complexity (Math 1090)
(ppt):
Classifying Computational Problems, NP, & Computable
12
Computing vs Accepting
Halt(M,I,t) is computable
and
Halt(M,I) ≡ ∃t Halt(M,I,t) is not
1
Poly vs NP
Sat(C,I) is in poly
and Sat(C) ≡ ∃I Sat(C,I) is likely not
56
50
NP
Clause-Sat(I) ≡ ∃S ∀C ∃x
"Assignment S satisfies variable x in clause C"
Reductions
[∀I [Sat(I) iff P(InstanceMap(I))]]
⇒ [Sat≤P]
24
Uncomputable Problems
∃P ∀M ∃I M(I)≠P(I)
Halting & MathTruth
Knowing whether a TM M halts or a first order sentence α is
valid
are both uncomputable.
7
Gödel's Incompleteness
No formal proof system is capable of proving all valid
and no
invalid formulas about the integer.
To guarantee a proof, α needs to also be true in every
nonstandard model.
6.0 Countable and Uncountable Infinite:
(ppt)
(There are more real numbers than fractions and the same number of
fractions as integers.)
20
Shorter Description vs Finite Description vs Infinite Description
68
35
Description Length and Carnality
53
Countable
Countable via a List
Countable via Finite Descriptions
Uncountable
Hierarchy of Infinities
Some Uncomputable Problem
6.1 Halting Problem is Uncomputable:
(ppt)
(Some computational problems are solved by NO algorithms.)
46
Halting is Undecidable
One page proof
History of Computability
The Halting Problem
Understanding Quantifiers
Some Uncomputable Problem
Halting Problem is Uncomputable
Review
Questions
6.2 Reductions For Uncomputability:
(ppt)
(Knowing that some computational problems are hard, we prove that
others are.)
1
84
37
Simple Reductions
2
30
Is Regular
3
11
Not Halt
4
36
Rice's Theorem
5
20
Harder Examples Quick
6
40
30
Recognizable
WATCH ABOVE by Monday Nov 1 4pm.
6.3 No Proof System for Number Theory:
(ppt)
(Godel proved that there is no mechanical way of proving everything in
mathematics.)
33
Gödel's Incompleteness Theorem
Halting << Math Truth
7 NP-completeness:
(ppt)
(Reductions involve writing an algorithm for one problem from that for
another. NP-Completeness give strong evidence that most search
problems that industry cares about are believed to not have poly-time
algorithms.)
00
84
NP-Reductions (Quick)
00
56
50 Card Reduction (Logic)
01
31
History & Overview
02
7
Course vs Schedule
03
14
More about Reductions
04
10
Circuit vs Airplane
05
24
Circuit vs 3-Colouring
06
31
Definition Review
WATCH ABOVE by Monday Nov 8 4pm.
TEST 4: Thur Nov 11 8:00am- Fri 11:00am, with partner
99 Machine Learning Made Easy:
description,
(The basic math needed to understand machine learning)
Invited 1.5hr Talk on Youtube
Magic, Overview, Training Data, Machine, Error Surface, Learning,
Gradient Descent, Generalizing, Singularity
EECS2001 Topics
00
94
88
01
32
Overview
02
33
Generalizing from Training Data
03
16
Linear Regression, Neural Networks 1
04
14
Neural Networks 2
05
30
Matrix Multiplication
06
16
Error
07
3
Compression Example
08
14
Gradient Descent, Steepest Direction
09
1:40
Review
WATCH ABOVE by Monday Nov 15 4pm.
30 hr course in Cameroon: (videos)
Ethics: (slides)
What is machine learning and why care?
Positive effects on the average person?
Negative effects on the average person?
Will AI machines be replacing humans any time soon?
How capable is AI as a judge?
What are your thoughts on social media?
Loosing our jobs to machines?
How is the ``software'' of a neural net produced.
More Advanced Topics
Practical Considerations
Back Propagation
Convolutional, Recurrent
Generative Adversarial Networks
Reinforcement Learning Markoff Chains
Bayesian Inference
Decision Trees, Clustering
Maximum Likelihood
Dimension Reduction
Generalizing from Training Data
VC-Dimension, Sigmoid, Singularity
TEST 5: Thur Nov 25 8:00am- Fri 11:00am, with partner
TEST 6: Wed Dec 8 8:00am- Thur 11:00am, with partner
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.