Computing from projections of random points

Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We study the sets that are computable from both halves of some (Martin-L"of) random sequence, which we call emph{

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 characterise

1 / 2

-bases as the sets computable from both halves of Chaitin's

O m e g a

, and as the sets that obey the cost function

m a t h b f c (x, s) = s q r t O m e g a_{s} - O m e g a_{x}

. Generalising these results yields a dense hierarchy of subideals in the

K

-trivial degrees: For

k < n

, let

B_{k / 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

O m e g a

. Furthermore, the corresponding cost function characterisation reveals that

B_{k / n}

is independent of the particular representation of the rational

k / n

, and that

B_{p}

is properly contained in

B_{q}

for rational numbers

p < q

. These results are proved using a generalisation 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 analyse 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

B_{p}

it characterises. We finish by showing that the the union of

B_{p}

for

p < 1

is the collection of sets which are robustly computable from a random, a class previously studied by Hirschfeldt, Jockusch, Kuyper, and Schupp.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Computing from projections of random points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114804)