Journal of Mathematical Logic 20 (1):1950014 (2019)

We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call 1/2-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e. elements. It is a proper subideal of the K-trivial sets. We characterize 1/2-bases as the sets computable from both halves of Chaitin’s Ω, and as the sets that obey the cost function c(x,s)=Ωs−Ωx−−−−−−−√. Generalizing these results yields a dense hierarchy of subideals in the K-trivial degrees: For k<n, let Bk/n be the collection of sets that are below any k out of n columns of some random sequence. As before, this is an ideal generated by its c.e. elements and the random sequence in the definition can always be taken to be Ω. Furthermore, the corresponding cost function characterization reveals that Bk/n is independent of the particular representation of the rational k/n, and that Bp is properly contained in Bq for rational numbers p<q. These results are proved using a generalization of the Loomis–Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyze arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the K-trivial sets; we can calculate from the family which Bp it characterizes. We finish by studying the union of Bp for p<1; we prove that this ideal consists of the sets that are robustly computable from some random sequence. This class was previously studied by Hirschfeldt [D. R. Hirschfeldt, C. G. Jockusch, R. Kuyper and P. E. Schupp, Coarse reducibility and algorithmic randomness, J. Symbolic Logic81(3) (2016) 1028–1046], who showed that it is a proper subclass of the K-trivial sets. We prove that all such sets are robustly computable from Ω, and that they form a proper subideal of the sets computable from every (weakly) LR-hard random sequence. We also show that the ideal cannot be characterized by a cost function, giving the first such example of a Σ03 subideal of the K-trivial sets.
Keywords Randomness  Cost functions  K-triviality
Categories (categorize this paper)
Reprint years 2020
DOI 10.1142/s0219061319500144
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,949
External links

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

Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Denjoy, Demuth and Density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.
Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.

View all 7 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Random Closed Sets Viewed as Random Recursions.R. Daniel Mauldin & Alexander P. McLinden - 2009 - Archive for Mathematical Logic 48 (3-4):257-263.
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Two More Characterizations of K-Triviality.Noam Greenberg, Joseph S. Miller, Benoit Monin & Daniel Turetsky - 2018 - Notre Dame Journal of Formal Logic 59 (2):189-195.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
What a Course on Philosophy of Computing is Not.Vincent C. Müller - 2008 - APA Newsletter on Philosophy and Computers 8 (1):36-38.
Random Generations of the Countable Random Graph.Su Gao & A. Vershik - 2006 - Annals of Pure and Applied Logic 143 (1-3):79-86.
The Initialization Problem in Quantum Computing.Subhash Kak - 1999 - Foundations of Physics 29 (2):267-279.


Added to PP index

Total views
3 ( #1,300,912 of 2,433,251 )

Recent downloads (6 months)
1 ( #462,722 of 2,433,251 )

How can I increase my downloads?


My notes