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

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 $\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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1164060463
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,949
Through your library

References found in this work BETA

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

Add more references

Citations of this work BETA

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.

Analytics

Added to PP index
2010-08-24

Total views
23 ( #461,942 of 2,433,244 )

Recent downloads (6 months)
1 ( #462,722 of 2,433,244 )

How can I increase my downloads?

Downloads

My notes