Movatterモバイル変換

We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.

Direct download(6 more)   Export citation   Bookmark   5 citations  

Direct download(4 more)   Export citation   Bookmark   4 citations  

A classical theorem in computability is that every promptly simple set can be cupped in the Turing degrees to some complete set by a low c.e. set. A related question due to A. Nies is whether every promptly simple set can be cupped by a superlow c.e. set, i. e. one whose Turing jump is truth-table reducible to the halting problem θ'. A negative answer to this question is provided by giving an explicit construction of a promptly simple set that (...) is not superlow cuppable. This problem relates to effective randomness and various lowness notions. (shrink)

Direct download(6 more)   Export citation   Bookmark   4 citations  

Direct download(6 more)   Export citation   Bookmark   1 citation  

Direct download(3 more)   Export citation   Bookmark   1 citation  

We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤ wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very (...) close to the definition of superlow cuppability. Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set whose join with every low c.e. set is low. (shrink)

Direct download(6 more)   Export citation   Bookmark