Universality (Un)computability (In)tractability
The Question
(start of Lec 17-19)		 What is a general-purpose 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 (first-order logic) 		NP problems believed to be intractable:
NP-complete: ILP, SAT, TSP, protein folding, Tetris, etc. Not known to be NP-complete: factoring. (None of these yet proven intractable!!)
Big Idea/
Practical
Consequences
  • A universal Turing machine can simulate any other Turing machine.
  • If you can simulate Turing machines, you can do any computable task.
  • Many equally powerful models of computation.
  • You can't automatically tell whether a program has a bug, contains a virus, or is as short as possible.
  • Not all tasks can be automated.
  • If a problem is reduced to an NP-complete one, don't hope to find fast algorithm that works in all cases.
  • NP-complete problems all "equal"
  • Intractability can work to your advantage (cryptography).
  • Appreciation = creativity? (P=NP?)
Vocab & People (suggestions below*) David Hilbert, Alonzo Church, Alan Turing, Church-Turing thesis, simulation, TM, UTM Alan Turing, Kurt Gödel, (un)computable, incompleteness, liar paradox, reduction, proof by contradiction Stephen Cook, Richard Karp, extended Church-Turing thesis, (in)efficient, polynomial-time, brute-force search, reduction, nondeterminism, P, NP, NP-complete, RSA
*: brute-force search, Alonzo Church, Church-Turing thesis, Stephen Cook, extended C.-T. thesis, Kurt Gödel, David Hilbert, incompleteness, (in)efficient, reduction, Richard Karp, liar paradox, nondeterminism, NP, NP-complete, polynomial-time, proof by contradiction, P, RSA, simulation, TM, Alan Turing, UTM