New answers tagged

4

If a set $A$ is Turing reducible to a set $B$ then we say that $B$ computes $A$. Every noncomputable set $A$ computes an immune set, namely $\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$. (If $A$ is a set of strings then we first turn it onto a [i.e. replace it by a Turing equivalent] set of integers or equivalently an infinite binary sequence ...


Top 50 recent answers are included