Series: Penn State Logic Seminar

Date: Tuesday, October 29, 2002

Time: 2:30 - 3:45 PM

Place: 312 Boucke Building

Speaker: Carl Mummert, Mathematics, Penn State

Title: Kolmogorov Complexity and 1-Random Reals, part 1

Abstract: 

Martin-Lof suggested that a typical, or "random," real number should
not have any effectively testable property shared by only a few other
reals.  Formalizing this idea, we call a real number 1-random if it
does not lie in any effective measure zero set.  Several alternative
definitions of randomness produce the same class of random real
numbers, affirming Martin-Lof's principle as the right
characterization of randomness.  The field of Kolmogorov Complexity
lies between probablity theory and recursion theory.  The Kolmogov
Complexity of a finite string is essentially the length of the
shortest program that, when run with no input, produces that string as
output.  This talk will begin with a brief introduction to Kolmogorov
complexity.  This talk will then cover the result, due to Chaitin and
Schnorr, that a real is 1-random iff the asymptotic Kolmogorov
complexity of its initial segments grows quickly enough.  If time
allows, other equivalent definitions of the random reals will be
dicussed.