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.