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.