Randomness and halting probabilities

VERÓNICA BECHER; SANTIAGO FIGUEIRA; SERGE GRIGORIEFF; JOSEPH S. MILLER

JOURNAL OF SYMBOLIC LOGIC, THE

UIUC Press

Año: 2006 vol. 71 p. 1411 - 1430

0022-4812

We consider the question of randomness of the probability $Omega_U[X]$ that an optimal Turing machine $U$ halts and outputs a string in a fixed set $X$. The main results are as follows: $Omega_U[X]$ is random whenever $X$ is $Sigma^0_n$-complete or $Pi^0_n$-complete for some $ngeq2$. However, for $n geq 2$, $Omega_U[X]$ is not $n$-random when $X$ is $Sigma^0_n$ or $Pi^0_n$. Nevertheless, there exists $Delta^0_{n+1}$ sets such that $Omega_U[X]$ is $n$-random. There are $Delta^0_2$ sets $X$ such that $Omega_U[X]$ is rational. Also, for every $n geq 1$, there exists a set $X$ which is $Delta^0_{n+1}$ and $Sigma^0_n$-hard such that $Omega_U[X]$ is not random. We also look at the range of $Omega_U$ as an operator. We prove that the set ${Omega_U[X] : X subseteq {0,1}^*}$ is a finite union of closed intervals. It follows that for any optimal machine $U$ and any sufficiently small real $r$, there is a set $X subseteq {0,1}^*$ recursive in $emptyset´oplus r$, such that $Omega_U[X]=r$.