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)|
References found in this work BETA
Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.
Citations of this work BETA
On the Computational Power of Random Strings.Adam R. Day - 2009 - Annals of Pure and Applied Logic 160 (2):214-228.
Similar books and articles
Monotone Reducibility and the Family of Infinite Sets.Douglas Cenzer - 1984 - Journal of Symbolic Logic 49 (3):774-782.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
On a Problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Bounding Minimal Degrees by Computably Enumerable Degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
Randomness, Relativization and Turing Degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515 - 535.
Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Relative Randomness and Real Closed Fields.Alexander Raichev - 2005 - Journal of Symbolic Logic 70 (1):319 - 330.
On the Complexity-Relativized Strong Reducibilites.Jari Talja - 1983 - Studia Logica 42 (2-3):259 - 267.
On the Kleene Degrees of Π11 Sets.Theodore A. Slaman - 1986 - Journal of Symbolic Logic 51 (2):352 - 359.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Definability and Initial Segments of C-Degrees.Robert S. Lubarsky - 1988 - Journal of Symbolic Logic 53 (4):1070-1081.
Decomposition and Infima in the Computably Enumerable Degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
Random Reals and Possibly Infinite Computations Part I: Randomness in ∅'.Verónica Becher & Serge Grigorieff - 2005 - Journal of Symbolic Logic 70 (3):891-913.
Added to index2010-08-24
Total downloads11 ( #404,810 of 2,172,696 )
Recent downloads (6 months)2 ( #172,670 of 2,172,696 )
How can I increase my downloads?