Readme, Course Information, Course Description, Dates, Photos Fun, Your Marks, Forum, Class

Topics	Slides	Steps	Notes	Questions	Start Class	# Classes
Quantifiers					1.5	1
Models of Computability					2.5	10
Digitization & Uncomputability					13	5
Reductions For Uncomputability					18	3
No Proof System for Number Theory					?	1
NP-completeness					?	2
Computability Classes					?	2
Other Possibilities					?	0

(Class = 1.5 hrs, we have 24 classes)

Texts:

Course Description
About Turing: Article
Steve Cook: Computability and Recursive and Recursively Enumerable Sets
Russell Impagliazzo Notes
Jeff Edmonds' "How to Think about Algorithms"   Amazon   Cambridge House Press   Desk Copies   reviews
Michael Sipser, Introduction to the Theory of Computation, (second edition) PWS Publishing Company, 2006.
Lewis and Papadimitriou, Elements of the Theory of Computation (second edition) 1998.
Hopcroft, J.E. and Ullman, J.D., Introduction to Automata, Languages and Programming, Addison Wesley, 1979.
Gems of Theoretical Computer Science (Many thanks to U. Schoning and R. Pruim)
Other References

Introduction: (ppt)

Quantifiers: (Steps, ppt, Questions)

Existential and Universal quantifiers

Models of Computability: (ppt, Cook, Questions)

History & Overview
Goto vs Loop Models
Turing Machines
Java to TM
Constant vs Finite vs Infinite
Primitive Recursive
TM to Primitive Recursive?
Primitive Recursive << TM
TM to Recursive
Register Machine
And/Or/Not Circuits
Computer Circuits
Circuits Depth
Arithmetic Circuits
Neural Nets
Poly-Time
Non-Deterministic Machines
Quantum Machine
Context Free Grammars
Java to Machine Code (Compiling/Parsing) (pdf, Java)
Context Sensitive Grammars
TM to Grammar
Decide vs Accept
Humans
Complexity Classes
Finite Automata (pdf, Rudich.ppt)

Diagonization & Uncomputability: (ppt, Cook, Questions)

Uncountable Infinity & Diagonalization
Diagonal Uncomputable
Halting Problem
Time Hierarchy

Reductions For Uncomputability: (ppt, Cook, Questions) (3*1.5hrs)

Reductions
Simple Reductions
Rice's Theorem
Reverse Reduction
Acceptable
The Post Correspondence Problem
Tiling (Impagliazzo)
CFG G Generates I
CFG G Generates Every String
CFG G Generates Some String
CFG L(G)=L(G')
Game of Life
Hilbert's Tenth Problem (Gems)

No Proof System for Number Theory: (ppt)

Gödel's Incompleteness Theorem
Halting << Math Truth

NP-completeness: (ppt, pdf, Questions)

History
Course vs Schedule
Circuit vs Airplane
Circuit vs 3-Colouring
Non-Deterministic Poly-Time
Reductions
K-Clique vs K-Independent Set
12 Steps
Any P <= Sat
3-Col <= 3-Sat
Sat <= 3-Col
More Problems
12 Steps in More Depth
Making Change scan
Embedding points with distortion pdf

Computability Classes: (ppt, Questions)

Computable using Halting as an oracle
Acceptable, Witness, Enumerable
Computable
Ackermann's Time
Double Exponential Time
E: Exponential Time
Exp Time
PSpace
PH: Poly-Time Hierarchy
NP & Co-NP
Poly-Time
NC: Poly-log depth Circuits
NC2
NL: Non-Det Log Space
L: Log-Space
AC0, Thres0, Arith0: Constant Depth
NC0: Constant Fan-out

Kolmogorove Complexity
Time/Space Trade offs Pebbles (pdf)
Cryptography: RSA (Josh, ppt)
Distributed Systems: mud on forehead & common knowledge
# of prime numbers
Intro to Quantum: Shor's factoring
Rudich's course

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.