Series: Penn State Logic Seminar

Date: Tuesday, November 9, 2004

Time: 2:30 - 3:45 PM

Place: 307 Boucke Building

Speaker: Stephen G. Simpson, Penn State, Mathematics

Title: Randomness Relative to a Turing Oracle, part 1

Abstract:

Let \$A\$ be an infinite sequence of 0's and 1's.  I shall review
Martin-L{\o}f's concept of what it means for \$A\$ to be random.
(This concept can also be defined in terms of the asymptotic
behavior of the Kolmogorov complexity of the finite initial segment
of \$A\$ of length \$n\$, as \$n\$ goes to infinity.)  After that, I shall
consider the relativization of randomness to a Turing oracle.  I
shall prove two theorems.  Theorem 1, due to Michiel van Lambalgen,
1987: If \$A\$ is random, and if \$B\$ is random relative to \$A\$, then
\$A \oplus B\$ is random.  Theorem 2, due to Joseph Miller, 2004: If
\$A\$ is random, \$A\$ is Turing reducible to \$B\$, and \$B\$ is random
relative to \$C\$, then \$A\$ is random relative to \$C\$.