Universality probability of a prefix-free machine
George Barmpalias and David L. Dowe
We study the notion of universality probability
of a universal prefix-free machine, as introduced by C.S. Wallace.
We show that it is random relative to the fourth iterate of the
halting problem and determine its Turing degree
and its place in the arithmetical hierarchy of complexity.
Furthermore, we give a computational characterization of the real numbers
which are universality probabilities of universal prefix-free machines.