Randomness and universal machines

SANTIAGO FIGUEIRA; FRANK STEPHAN; GUOHUA WU

JOURNAL OF COMPLEXITY

Elsevier

Año: 2006 vol. 22 p. 738 - 751

0885-064X

The present work investigates several questions from a recent survey of Miller and Nies related to Chaitin´s $Omega$ numbers and their dependence on the underlying universal machine. Furthermore, the notion $Omega_U[X] = sum_{p: U(p)downarrow in X} 2^{-|p|}$ is studied for various sets $X$ and universal machines $U$. A universal machine $U$ is constructed such that for all $x$, $Omega_U[{x}] = 2^{1-H(x)}$. For such a universal machine there exists a co-r.e. set $X$ such that $Omega_U[X]$ is neither left-r.e. nor Martin-Löf random. Furthermore, one of the open problems of Miller and Nies is answered completely by showing that there is a sequence $U_n$ of universal machines such that the truth-table degrees of the $Omega_{U_n}$ form an antichain. Finally it is shown that the members of hyperimmune-free Turing degree of a given $Pi^0_1$-class are not low for $Omega$ unless this class contains a recursive set.