Randomness Relative to a Turing Oracle, part 2

Series: Penn State Logic Seminar

Date: Tuesday, November 16, 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 2

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