Speaker : Vladimir Uspensky, Moscow State University
Date: Thursday Oct 9 2003
Time: 1:30-2:30pm
Place: ASB 9705

Algorithmic Roots of G\"odel Incompleteness Theorem.

Given any proof system, there is a true statement that cannot be proven within the system. This fact is the content of G\"odel famous Incompleteness Theorem --- one of the deepest theorems in mathematics. It is amazing that G\"odel found a precise formulation and a proof of his theorem. It is no less amazing that the theorem actually is of a rather simple nature. An attempt will be made in this talk to unearth the roots of the theorem, which lie in computability theory.

V. A. Uspensky.
G\"odel's incompleteness theorem
// Theoretical Computer Science, 1994, vol.~130 (1994), no.~2, pp.~239--319