Relativizing chaitin's halting probability

Journal of Mathematical Logic 5 (02):167-192 (2005)
  Copy   BIBTEX

Abstract

As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let [Formula: see text] be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory and this Omega operator. But unlike the jump, which is invariant under the choice of an effective enumeration of the partial computable functions, [Formula: see text] can be vastly different for different choices of U. Even for a fixed U, there are oracles A =* B such that [Formula: see text] and [Formula: see text] are 1-random relative to each other. We prove this and many other interesting properties of Omega operators. We investigate these operators from the perspective of analysis, computability theory, and of course, algorithmic randomness.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,667

External links

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

Through your library

Similar books and articles

New jump operators on equivalence relations.John D. Clemens & Samuel Coskey - 2022 - Journal of Mathematical Logic 22 (3).
Independence in randomizations.Uri Andrews, Isaac Goldbring & H. Jerome Keisler - 2019 - Journal of Mathematical Logic 19 (1):1950005.
Computable aspects of the Bachmann–Howard principle.Anton Freund - 2019 - Journal of Mathematical Logic 20 (2):2050006.

Analytics

Added to PP
2012-09-02

Downloads
50 (#441,015)

6 months
9 (#504,609)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Lowness properties and approximations of the jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.

View all 17 citations / Add more citations

References found in this work

Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Creative sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.
Creative sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.

View all 9 references / Add more references