Universality probability of a prefix-free machine


George Barmpalias and David L. Dowe

Summary


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.