William Dan, University of Waterloo
Random Left C.E. Reals and Solovay Reducibility
In the last seminar we discussed how the halting probability of a universal prefix-free machine is left c.e. andrandom, and asked if the converse would hold. We then studied Solovay reducibility and the resulting concept ofSolovay completeness, which turns out to be key in proving the converse. In this seminar, we will use thisconcept to prove the two theorems giving the converse, a theorem from Calude et al. and the Kucera-Slamantheorem. Then, we will go back to expand further on the properties of Solovay reducibility and how it connectsto relative randomness, and relate this connection back to the theorems we proved. This seminar follows sections9.1 and 9.2 from the Downey and Hirschfeldt book.
MC 5403