# 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