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$.