GODEL'S THEOREM
- Introduction to Formal Languages and Automata
Index to slides for CS181 course at UCLA, Winter 1996.
- Hilbert's question:
Intl. Congress of Mathematics, Paris, 1900
David Hilbert: "Is every true theorem provable?"
- Incompleteness Theorem:
In any consistent theory, there must exist true (but not provable) statements.
- Godel's Proof
Suppose UTM exists which answers any question correctly.
Consider the program/circuit P of UTM. P(UTM) is finite.
G = "The machine constructed from P(UTM) will never say that this
sentence is true." = "UTM will never say G is true."
Will UTM declare G to be true?
If UTM says G true, then G is false => UTM was wrong.
Therefore, the UTM never says G is true.
This makes G a true statement.
Therefore, UTM is not universal.
Other Godel's Theorem Links
Go 
