Unified characterizations of lowness properties via Kolmogorov complexity

Archive for Mathematical Logic 54 (3-4):329-358 (2015)
  Copy   BIBTEX

Abstract

Consider a randomness notion C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. A uniform test in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} is a total computable procedure that each oracle X produces a test relative to X in the sense of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}. We say that a binary sequence Y is C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}-random uniformly relative to X if Y passes all uniform C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} tests relative to X. Suppose now we have a pair of randomness notions C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document} and D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{D}}$$\end{document} where C⊆D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C} \subseteq \mathcal{D}}$$\end{document}, for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low which consist of the oracles X that are so feeble that C⊆DX\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C} \subseteq \mathcal{D}^X}$$\end{document}. Our goal is to do the same when the randomness notion D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{D}}$$\end{document} is relativized uniformly: denote by Low \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\star}$$\end{document} the class of oracles X such that every C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{C}}$$\end{document}-random is uniformly D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{D}}$$\end{document}-random relative to X. We show that X∈Low⋆\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X\in Low ^\star}$$\end{document} if and only if X is c.e. tt-traceable if and only if X is anticomplex if and only if X is Martin-Löf packing measure zero with respect to all computable dimension functions. We also show that X∈Low⋆\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X\in Low^\star}$$\end{document} if and only if X is computably i.o. tt-traceable if and only if X is not totally complex if and only if X is Schnorr Hausdorff measure zero with respect to all computable dimension functions.

Links

PhilArchive



    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

Lowness Properties and Approximations of the Jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Kolmogorov Complexity and Noncomputability.George Davie - 2002 - Mathematical Logic Quarterly 48 (4):574-581.
Relative Kolmogorov Complexity and Geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.
On the Kolmogorov Complexity of Continuous Real Functions.Amin Farjudian - 2013 - Annals of Pure and Applied Logic 164 (5):566-576.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.

Analytics

Added to PP
2015-03-22

Downloads
17 (#634,531)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press.
Computational Randomness and Lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Lowness and Π₂⁰ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.

View all 28 references / Add more references