"The Chaitin's Constant"
Leo Ducas
UCSD
Monday, September 30th, 2013, 2:00 pm
EBU3B, Room 4217
Abstract:
A real x is said to be normal in base b, if any sequence appears with the same frequency in its decimals in base b; if it is normal in every bases, it is said absolutely normal. It is relatively easy to prove that there exist a lot of them, in either in the sense of Borel or Lebesgue. Yet, it is not trivial to explicitly give such a real.
The first construction is due to Chaitin, and surprisingly, the answer came from computability and information theory. The construction and proof are related to the undecidability of the halting problem, but with a information-theoretic component. Intuitively Turing undecidability results follows from a Russell-paradox-like statement (the barber shaves everyone who doesn't shave themselves...), while Chaitin constructions uses Berry-paradox-like statement ("let x be the smallest integer not definable in less than twenty words").
Technically, the construction and proof are quite simple, but offers a review of a some basic CS notions: Shannon and Kolmogorov entropy, diagonal arguments, and why not a bit of topology.