Superhighness

DOI10.1215/00294527-2009-020MaRDI QIDQ987937zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen, André Nies

Publication date 2 September 2010

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2845

zbMATH Keywords

jump traceabilitysuperhighness

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Abstract: We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class superhigh${}^{D}iamond$, and show that it contains some, but not all, of the noncomputable $K$-trivial sets.

Review text

In the paper under review, the authors prove that: {\parindent5mm \begin{itemize}\item[1)] There is a superhigh jump-traceable set; \item[2)] The class of c.e. sets Turing-below all Martin-Löf random superhigh sets is a proper subclass of the c.e. \(K\)-trivials. \end{itemize}}

Recommendations

• Superhighness and Strong Jump Traceability
• Characterizing the strongly jump-traceable sets via randomness
• A random set which only computes strongly jump-traceable c.e. sets
• Strong jump-traceability. II: K-triviality
• Strong jump-traceability. I: The computably enumerable case

Cited in

(5)

• Unified characterizations of lowness properties via Kolmogorov complexity
• Superhighness and Strong Jump Traceability
• Characterizing the strongly jump-traceable sets via randomness
• On arithmetical level of the class of superhigh sets
• Reals which compute little

This page was built for publication: Superhighness

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