×

Beyond strong jump traceability. (English) Zbl 1220.03044

Summary: Strong jump traceability has been studied by various authors. In this paper we study a variant of strong jump traceability by looking at a partial relativization of strong jump traceability. We discover a new subclass \(\mathcal H\) of the computably enumerable (c.e.) \(K\)-trivials with some interesting properties. These sets are computationally very weak, but yet contain a cuppable member. Surprisingly they cannot be constructed directly using cost functions, and this is the first known example of a subclass of the \(K\)-trivials which does not contain any promptly simple member. Furthermore, there is a single c.e. set which caps every member of \({\mathcal H}\), demonstrating that they are in fact very far away from being promptly simple.

MSC:

03D32 Algorithmic randomness and dimension
03D25 Recursively (computably) enumerable sets and degrees
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI