Article ID Journal Published Year Pages File Type
4609141 Journal of Complexity 2006 8 Pages PDF
Abstract

Say that Y has the strong random anticupping property if there is a set A such that for every Martin–Löf random set RY⩽TA⊕R⇒Y⩽TRY⩽TA⊕R⇒Y⩽TR(in this case A is an anticupping witness for Y  ). Nies has shown that every random Δ20 set has the strong random anticupping property via a promptly simple anticupping witness. We show that every Δ20 set has the random anticupping property via a promptly simple anticupping witness. Moreover, we prove the following stronger statement: for every non-computable Y⩽T∅′Y⩽T∅′ there exists a promptly simple A such thatY⩽TA⊕R⇒A⩽TRY⩽TA⊕R⇒A⩽TRfor all Martin–Löf random sets R.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Analysis
Authors
,