Series: Penn State Logic Seminar

 Date: Tuesday, April 11, 2006

 Time: 2:30 - 3:45 PM

 Place: 106 McAllister Building

 Speaker: Esteban Gomez-Riviere, Penn State, Mathematics

 Title: Introduction to $K$-Trivial Reals, part 2

 Abstract:

   In a previous talk we introduced $K$-trivial reals.  In this talk
   we shall apply the Kraft-Chaitin theorem to prove Chaitin's 1975
   result that all $K$-trivial reals are $\Delta^0_2$.  Along the way
   we shall prove the following result of Zambella 1990: The number of
   strings of length $n$ of complexity at most $c$ plus the complexity
   of $n$ is $O(2^c)$.  If time permits, we shall consider further
   properties of $K$-trivial reals, e.g., closure under join, and
   closure under Turing reducibility.