×

zbMATH — the first resource for mathematics

Effective packing dimension and traceability. (English) Zbl 1204.03042
The first author of the paper under review, jointly with Noam Greenberg, proved that a c.e. degree contains a real with positive effective packing dimension if and only if it is array noncomputable [R. Downey and N. Greenberg, Inf. Process. Lett. 108, No. 5, 298–303 (2008; Zbl 1191.68304)]. The result is not true for general degrees. So it is natural to ask whether Downey-Greenberg’s result remains true if one replaces “arrary noncomputable” with “not c.e. traceable” for general reals. The authors in the paper under review refute this by showing that: 5mm
1)
There is a hyperimmune-free and non-c.e. traceable real \(x\) below \(0''\) (Turing-) below which every real has effective packing dimension 0;
2)
There is a non-c.e. traceable real below \(0'\) (Turing-) below which every real has effective packing dimenstion 0.
Reviewer: Liang Yu (Nanjing)

MSC:
03D32 Algorithmic randomness and dimension
03D28 Other Turing degree structures
PDF BibTeX XML Cite
Full Text: DOI