Kolmogorov complexity and computably enumerable sets

&
Annals of Pure and Applied Logic 164 (12):1187-1200 (2013)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2013.06.007

Links

PhilArchive



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

External links

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

Through your library

My notes

Similar books and articles

On the filter of computably enumerable supersets of an r-maximal set.Steffen Lempp, André Nies & D. Reed Solomon - 2001 - Archive for Mathematical Logic 40 (6):415-423.
Codable sets and orbits of computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Journal of Symbolic Logic 63 (1):1-28.
Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
Implicit measurements of dynamic complexity properties and splittings of speedable sets.Michael A. Jahn - 1999 - Journal of Symbolic Logic 64 (3):1037-1064.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.
The ibT degrees of computably enumerable sets are not dense.George Barmpalias & Andrew E. M. Lewis - 2006 - Annals of Pure and Applied Logic 141 (1-2):51-60.
The computably enumerable degrees are locally non-cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.
Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
Definability, automorphisms, and dynamic properties of computably enumerable sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
Bounding cappable degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
A random set which only computes strongly jump-traceable C.e. Sets.Noam Greenberg - 2011 - Journal of Symbolic Logic 76 (2):700 - 718.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Every incomplete computably enumerable truth-table degree is branching.Peter A. Fejer & Richard A. Shore - 2001 - Archive for Mathematical Logic 40 (2):113-123.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.

Analytics

Added to PP
2014-01-16

Downloads
27 (#593,400)

6 months
10 (#277,276)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
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 23 references / Add more references