Computability Learning Seminar

Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo

“The Decanter Method”

We have previously introduced several different notions of lowness related to complexity which a real number can possess. Amongst these notions were lowness for K, lowness for Martin-Lof randomness, and being a base for Martin-Lof randomness. We showed that these notions are all equivalent, and introduced a fourth notion, K-triviality. We saw that the three equivalent notions each imply K-triviality.

Our main goal is now to prove that all four of the notions are equivalent, which we will achieve by showing that every K-trivial set is low for K. This requires the use of the decanter method, as well as the golden run construction.

The semimar will focus on introducing the ideas needed for the decanter method. We will do so incrementally, giving proofs of increasingly strong results as we do so. In our first proof, we will only show that a K-trivial set cannot be wtt-complete, and in our second, that it cannot be Turing complete either.

In future seminars, we will refine the method further by introducing the golden run con- struction.

MC 5403