Speaker : Vladimir Uspensky,
Moscow State University

Date: Thursday Oct 9 2003

Time: 1:30-2:30pm

Place: ASB 9705

Title:

Algorithmic Roots of G\"odel Incompleteness Theorem.

Abstract

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.

Reference:

V. A. Uspensky.

G\"odel's incompleteness theorem

// Theoretical Computer Science, 1994, vol.~130 (1994), no.~2, pp.~239--319