Randomness and Halting Probabilities

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

JOURNAL OF SYMBOLIC LOGIC, THE

Association for Symbolic Logic

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

0022-4812

   Abstract. 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 Σ^0_n -complete or Π^0_n -complete for some n ≥ 2.However, for n ≥ 2, Omega_U [X] is not n-random when X is Σ^0_n or Π^0_n.   Nevertheless, there exists ∆^0_n+1 sets such that Omega_U [X] is n-random.There are ∆^0_2 sets X such that Omega_U [X] is rational. Also, for every n ≥ 1, there exists   a set X which is ∆^0_n+1 and Σ^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 ⊆ 2^