The Journal of Symbolic Logic

Research Article

Randomness and halting probabilities

VeróNica Bechera1, Santiago Figueiraa2, Serge Grigorieffa3 and Joseph S. Millera4

a1 Departamento De Computación, Facultad De Ciencias Exactas Y Naturales, Universidad De Buenos Aires, Argentina and Conicet, Argentina, E-mail: vbecher@dc.uba.ar

a2 Departamento De Computación, Facultad De Ciencias Exactas Y Naturales, Universidad De Buenos Aires, Argentina, E-mail: sflgueir@dc.uba.ar

a3 Liafa, Université Paris 7 & CNRS, France, E-mail: seg@liafa.jussieu.fr

a4 Department of Mathematics, University of Connecticut, USA, E-mail: joseph.miller@math.uconn.edu

Abstract

We consider the question of randomness of the probability Ω U [X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows:

• Ω U [X] is random whenever X is Σn 0-complete or Πn 0-complete for some n ≥ 2.

• However, for n ≥ 2, Ω U [X] is not n-random when X is Σn 0 or Πn 0. Nevertheless, there exists Δn+1 0 sets such that Ω U [X] is n-random.

• There are Δ2 0 sets X such that Ω U [X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+1 0 and Σn 0-hard such that Ω U [X] is not random.

We also look at the range of ΩU as an operator. We prove that the set {Ω U [X]: X ⊆ 2ω } 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 ⊆ 2ω recursive in ∅′ ⊕ r, such that Ω U [X] = r.

The same questions are also considered in the context of infinite computations, and lead to similar results.

(Received December 13 2005)