David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 71 (4):1327 - 1341 (2006)
Levin and Schnorr (independently) introduced the monotone complexity, Km(α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α ↾ n) ≤ Km(β ↾ n) + c for all n. The monotone degree of α is the set of all β such that α ≤Km β and β ≤Km α. We show the monotone degrees contain an antichain of size 2N0, a countable dense linear ordering (of degrees of cardinality 2N0), and a minimal pair. Downey, Hirschfeldt, LaForte, Nies and others have studied a similar structure, the K -degrees, where K is the prefix-free Kolmogorov complexity. A minimal pair of K -degrees was constructed by Csima and Montalbán. Of particular interest are the noncomputable trivial reals, first constructed by Solovay. We define a real to be (Km, K)-trivial if for some constant c, Km(α ↾ n) ≤ K(n)+c for all n. It is not known whether there is a Km-minimal real, but we show that any such real must be (Km, K)-trivial. Finally, we consider the monotone degrees of the computably enumerable (c.e.) and strongly computably enumerable (s.c.e.) reals. We show there is no minimal c.e. monotone degree and that Solovay reducibility does not imply monotone reducibility on the c.e. reals. We also show the s.c.e. monotone degrees contain an infinite antichain and a countable dense linear ordering
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Adam R. Day (2009). On the Computational Power of Random Strings. Annals of Pure and Applied Logic 160 (2):214-228.
Similar books and articles
Douglas Cenzer (1984). Monotone Reducibility and the Family of Infinite Sets. Journal of Symbolic Logic 49 (3):774-782.
Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. Journal of Symbolic Logic 69 (2):533 - 554.
Shamil Ishmukhametov (2003). On a Problem of Cooper and Epstein. Journal of Symbolic Logic 68 (1):52-64.
Peter Cholak, Rod Downey & Stephen Walk (2002). Maximal Contiguous Degrees. Journal of Symbolic Logic 67 (1):409-437.
Angsheng Li & Dongping Yang (1998). Bounding Minimal Degrees by Computably Enumerable Degrees. Journal of Symbolic Logic 63 (4):1319-1347.
André Nies, Frank Stephan & Sebastiaan A. Terwijn (2005). Randomness, Relativization and Turing Degrees. Journal of Symbolic Logic 70 (2):515 - 535.
Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
Alexander Raichev (2005). Relative Randomness and Real Closed Fields. Journal of Symbolic Logic 70 (1):319 - 330.
Jari Talja (1983). On the Complexity-Relativized Strong Reducibilites. Studia Logica 42 (2-3):259 - 267.
Theodore A. Slaman (1986). On the Kleene Degrees of Π11 Sets. Journal of Symbolic Logic 51 (2):352 - 359.
Joseph S. Miller (2004). Degrees of Unsolvability of Continuous Functions. Journal of Symbolic Logic 69 (2):555 - 584.
Robert S. Lubarsky (1988). Definability and Initial Segments of C-Degrees. Journal of Symbolic Logic 53 (4):1070-1081.
Philip Welch (1987). Minimality in the ▵13-Degrees. Journal of Symbolic Logic 52 (4):908 - 915.
Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore (2003). Decomposition and Infima in the Computably Enumerable Degrees. Journal of Symbolic Logic 68 (2):551-579.
Verónica Becher & Serge Grigorieff (2005). Random Reals and Possibly Infinite Computations Part I: Randomness in ∅'. Journal of Symbolic Logic 70 (3):891-913.
Sorry, there are not enough data points to plot this chart.
Added to index2010-08-24
Total downloads4 ( #294,703 of 1,679,360 )
Recent downloads (6 months)2 ( #112,124 of 1,679,360 )
How can I increase my downloads?