Universality  (Un)computability  (In)tractability  

The Question (start of Lec 1719) 
What is a generalpurpose computer?  What can a computer do?  What can a computer do with limited resources? 
Examples of:  universal models of computation: Turing Machines; any single Universal Turing Machine; programming languages; random access machines; quantum computers; lambda calculus 
undecidable problems: the halting problem; Hilbert's 10th problem (Diophantine equations); virus identification; program equivalence; dead code elimination; integration; Entscheidungsproblem (firstorder logic) 
NP problems believed to be intractable: NPcomplete: ILP, SAT, TSP, protein folding, Tetris, etc. Not known to be NPcomplete: factoring. (None of these yet proven intractable!!) 
Big Idea/ Practical Consequences 



Vocab & People (suggestions below*)  David Hilbert, Alonzo Church, Alan Turing, ChurchTuring thesis, simulation, TM, UTM  Alan Turing, Kurt Gödel, (un)computable, incompleteness, liar paradox, reduction, proof by contradiction  Stephen Cook, Richard Karp, extended ChurchTuring thesis, (in)efficient, polynomialtime, bruteforce search, reduction, nondeterminism, P, NP, NPcomplete, RSA 