Series: Penn State Logic Seminar

Date: Tuesday, February 22, 2005

Time: 2:30 - 3:45 PM

Place: 103 Pond Laboratory

Speaker: Stephen G. Simpson, Penn State, Mathematics

Title: A Dichotomy for Martin-Lof Randomness

Abstract: 

  Let $A$ be an infinite sequence of 0's and 1's.  We say that $A$ is
  Turing complete if $A$ computes the Halting Problem.  We say that
  $A$ is PA-complete if $A$ computes a completion of Peano Arithmetic,
  or equivalently, $A$ computes a separating set for any recursively
  inseparable pair of recursively enumerable sets.  It is known that
  Turing completeness implies PA-completeness but, in general, the
  converse fails badly.  I shall prove the following recent result due
  to Frank Stephan.  If $A$ is random in the sense of Martin-L{\o}f,
  then $A$ is either Turing complete or PA-incomplete.  There are old
  results of Ku\v{c}era showing that both possibilities occur.