Journal of Mathematical Logic 14 (2):1450011 (2014)

Authors
Abstract
We examine the sequences A that are low for dimension, i.e. those for which the effective dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension 1 relative to A, and lowishness for K, namely, that the limit of KA/K is 1. We show that there is a perfect [Formula: see text]-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order nε, for any ε > 0.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1142/s0219061314500111
Options
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: 57,138
Through your library

References found in this work BETA

Almost Everywhere Domination and Superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
A Perfect Set of Reals with Finite Self-Information.Ian Herbert - 2013 - Journal of Symbolic Logic 78 (4):1229-1246.
Computability and Randomness.André Nies - 2008 - Oxford University Press UK.

Add more references

Citations of this work BETA

A Perfect Set of Reals with Finite Self-Information.Ian Herbert - 2013 - Journal of Symbolic Logic 78 (4):1229-1246.

Add more citations

Similar books and articles

Analytics

Added to PP index
2015-09-02

Total views
16 ( #618,202 of 2,411,686 )

Recent downloads (6 months)
1 ( #539,172 of 2,411,686 )

How can I increase my downloads?

Downloads

My notes