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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,873

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

Analytics

Added to PP
2012-09-02

Downloads
36 (#455,696)

6 months
16 (#171,907)

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.
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.
[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.

View all 10 references / Add more references