In his book "Shadows of the Mind", Roger Penrose details an argument based on Godel's Incompleteness theorem to prove that the mathematical capabilities of human mathematicians are non-computable. Godel's Incompleteness Theorem Here is a brief description and proof of Godel's Incompleteness Theorem. - Let X and Y be members of a data language D whose members can be used to represent executable programs that act on elements of D
- A program X applied to input data Y is written X(Y), and may or may not terminate in a finite number of steps.
- Let pair
- Let F be a function with the following property - if F (X,Y) terminates, then X(Y) does not terminate. Such an F is to be called consistent
- If the converse holds for such an F, i.e.
for all X and Y, X(Y) does not terminate => F(X,Y) does terminate,
then we call F complete. - Godel's theorem tells us that there is no F which is both consistent and complete. Proof -
- Let F be consistent, and define G such that G(X)=F(X,X).
- Then G(G) = F (G,G), and if G(G) terminates then this implies G(G) does not terminate.
- Which is a contradiction, so we conclude that G(G) does not terminate.
| |
|
