Computability Learning Seminar

Michael Gregory, University of Waterloo

Computability Relative to Random Sets

This presentation explores the interaction between algorithmic randomness and Turing degrees. We focus on 1-random sets and how randomness interacts with computable reducibility. Several fundamental results are discussed that illuminate the placement of random sets within the Turing degrees and the constraints that randomness imposes on computable reductions. In particular, the Kucera-Gacs Theorem is presented, which establishes that every set is weak truth-table reducible to a 1-random set.

MC 5403