2012/06/18 by George Barmpalias, David L. Dowe · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Benford’s Law and Fraud Detection #semigroups and automata theory
paper · pdf · doi:10.1098/rsta.2011.0319
openalex publication_date 2012/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
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 third 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 that are universality probabilities of universal prefix-free machines.