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.