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.) |