William Dan, University of Waterloo
A Characterization of Random, Left C.E. Reals
An immediate property of the halting probability of a prefix-free machine is that it is a left c.e. real. An easycorollary of the Kraft-Chaitin theorem is that the converse is true: any left c.e. real is the halting probability ofsome prefix-free machine. The most common example of a random real is Chaitin's omega, the haltingprobability of a universal prefix-free machine. In fact, it is a random left c.e. real. It is natural then to ask if theconverse holds in this case as well: that any random left c.e. real is the halting probability of some universalprefix-free machine. As it turns out, this is the case, and in this talk I will explain the concept used to solve thisquestion, Solovay reducibility, then prove the theorems demonstrating the converse. This talk follows sections9.1 and 9.2 of the Downey and Hirschfeldt book.
MC 5403