```
THEORY OF COMPUTATION

HILBERT - There exists assumptions for all procedures s.t. conclusion
(decision problem)
||
\/
MODEL OF COMPUTATION
1935 ALAN TURING
1. *invents* Idea of Algorithm
2. Turing Machine (TM) if state [A..Z] scanning x then do y & goto
state [A..Z]
3. Universal Turing Machine (UTM)= TM w/ O/S & Tape read. Emulate
Any Algorithm

Turing Machine
Bit->Word->Stream->Program->Output
Formal System
Syntax->Lexicon->Axiom->Heuristic->Theorem
Mathematical
Semantics->Geometry->Analysis->Transform->Tautology

1980 BSS - Blum-Shub-Smale
Flowchart model of computation
space of inputs -> space of outputs ->states -> halting set (Gamma)
||
\/

1936 HALTING PROBLEM
For any turing machine program H , purporting to settle the halting or
non-halting of all turing machine programs there exists program P w/
input I s.t. program H cannot determine if P will halt when processing I

/\
||

GODEL's THEOREM
For any consistent formal system F purporting to settle, prove or disprove.
All statements of arithmetic.  There exists an arithmetical proposition
that can be neither proved nor disproved in this system therefore, the
formal system F is incomplete

1. Godel Numbering : Code scheme translate logical formula
proof into mirror of natural numbers
2. Liar Paradox    : Truth - provability "this sentence is false"
-> "This statement is not provable"
3. Godel Sentence  : "This statement unprovable"
math counterpart = godel sentence
G in all math formalizations
4. Incompleteness  : Prove godel sentence G true but unprovable
if consistent formal system
5. No Escape Clause: New systems w/ added axioms has its own
unprovable godel sentence
6. Consistency     : Math statement A, "Arithmetic is consistent"
prove this is unprovable;  arithmetic as a formal
system too weak to prove own consistency

1950 TURING TEST - Can a machine Think?
Intelligence vs Consciousness
posit only external observed behavior key- eliza

HALTING PROBABILITY
Omega = Prob ( Random program for turing machine will halt)

||
\/
P and NP
1. P Algorithms which run in polynomial time f(problem size) e.g. sort cards)
2. Exponential time algorithms (n!, 10^n, Tower of Hanoi 2^n-1)
3. NP - Nondeterministic Polynomial Time
e.g. routing problem, assignment problem,map coloring prob, bin packing.

``` Home Next ... Optimization