Monday, March 23, 2026 1:00 pm
-
2:30 pm
EDT (GMT -04:00)
William Dan, University of Waterloo
Solovay Reducibility and Relative Randomness
Having completed our characterization of left-c.e. random reals, we return to the concept of Solovay reducibilityto study it more deeply. We will see that beyond the characterizations we have seen so far, Solovay reducibilitycan be viewed as a measure of relative randomness, and connect this perspective back to the Kucera-Slamantheorem. We will also relate it to the reducibilities we have studied previously, and give a final, possiblysimplest, characterization of Solovay reducibility. This seminar follows sections 9.1 and 9.2 from the Downeyand Hirschfeldt book.
MC 5403