Effective packing dimension and traceability (Q985010)

From MaRDI portal





scientific article; zbMATH DE number 5758442
Language Label Description Also known as
default for all languages
No label defined
    English
    Effective packing dimension and traceability
    scientific article; zbMATH DE number 5758442

      Statements

      Effective packing dimension and traceability (English)
      0 references
      0 references
      0 references
      20 July 2010
      0 references
      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 [\textit{R. Downey} and \textit{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: {\parindent5mm \begin{itemize}\item[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; \item[2)] There is a non-c.e. traceable real below \(0'\) (Turing-) below which every real has effective packing dimenstion 0. \end{itemize}}
      0 references
      0 references
      effective dimension
      0 references
      Turing degrees
      0 references

      Identifiers