Computability Learning Seminar

Michael Gregory  University of Waterloo,

Computability Relative to Random Sets (2)

Now that we have covered the required background, we begin discussion on 1-random sets and how randomness interacts with computable reducibility. Several fundamental results are discussed including Kučera's Theorem which states that if a 1 random set is Turing reducible to a c.e. Set, then that set is Turing Equivalent to 0'. We then cover the Space Lemma which is used in the proof of Kučera Gác's Theorem which establishes that every set is weak truth-table reducible to a 1-random set.

MC 5403