Randomness and Halting Probabilities

Journal of Symbolic Logic 71 (4):1411 - 1430 (2006)


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 $\Sigma _{n}^{0}$-complete or $\Pi _{n}^{0}$-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is $\Sigma _{n}^{0}$ or $\Pi _{n}^{0}$ Nevertheless, there exists $\Delta _{n+1}^{0}$ sets such that ΩU[X] is n-random. There are $\Delta _{2}^{0}$ sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is $\Delta _{n+1}^{0}$ and $\Sigma _{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

Download options


    Upload a copy of this work     Papers currently archived: 72,722

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

23 (#497,862)

6 months
1 (#388,319)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Algorithmic Information Theory.Peter Gacs - 1989 - Journal of Symbolic Logic 54 (2):624-627.

Add more references

Citations of this work

Randomness and Computability: Open Questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.

Add more citations

Similar books and articles

Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
On the Construction of Effectively Random Sets.Wolfgang Merkle & Nenad Mihailović - 2004 - Journal of Symbolic Logic 69 (3):862-878.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Relative Randomness and Real Closed Fields.Alexander Raichev - 2005 - Journal of Symbolic Logic 70 (1):319 - 330.