On the computational power of random strings

Annals of Pure and Applied Logic 160 (2):214-228 (2009)
  Copy   BIBTEX


There are two fundamental computably enumerable sets associated with any Kolmogorov complexity measure. These are the set of non-random strings and the overgraph. This paper investigates the computational power of these sets. It follows work done by Kummer, Muchnik and Positselsky, and Allender and co-authors. Muchnik and Positselsky asked whether there exists an optimal monotone machine whose overgraph is not tt-complete. This paper answers this question in the negative by proving that the overgraph of any optimal monotone machine, or any optimal process machine, is tt-complete. The monotone results are shown for both descriptional complexity Km and KM, the complexity measure derived from algorithmic probability. A distinction is drawn between two definitions of process machines that exist in the literature. For one class of process machines, designated strict process machines, it is shown that there is a universal machine whose set of non-random strings is not tt-complete



    Upload a copy of this work     Papers currently archived: 74,509

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

Computing Mechanisms.Gualtiero Piccinini - 2007 - Philosophy of Science 74 (4):501-526.
Recursive Events in Random Sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.
On the Topological Size of Sets of Random Strings.M. Zimand - 1986 - Mathematical Logic Quarterly 32 (6):81-88.
An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
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.
Random Closed Sets Viewed as Random Recursions.R. Daniel Mauldin & Alexander P. McLinden - 2009 - Archive for Mathematical Logic 48 (3-4):257-263.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.


Added to PP

12 (#797,852)

6 months
9 (#87,382)

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

Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.

Add more references