Monday 28 November 2005, 11h00, M 320
Abstract
In this talk we report some results, jointly obtained with H. Juergensen,
regarding Chaitin's heuristic principle: 'the theorems of a
finitely-specified theory cannot be significantly more complex than the
theory itself'. We show that this principle is valid for an appropriate
measure of complexity. We show that the measure is invariant under the
change of the Goedel numbering. For this measure, the theorems of a
finitely-specified, sound, consistent theory strong enough to formalize
arithmetic which is arithmetically sound (like Zermelo-Fraenkel set theory
with choice or Peano Arithmetic) have bounded complexity, hence every
sentence of the theory which is significantly more complex than the theory
is unprovable. Previous results showing that incompleteness is not
accidental, but ubiquitous are here reinforced in probabilistic terms: the
probability that a true sentence of length n is provable in the theory
tends to zero when n tends to infinity, while the probability that a
sentence of length n is true is strictly positive. The talk will conclude
with a few open problems.
© 2005 Vasco Brattka