New answers tagged complexity-classes
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
