<p>If a set <span class="math-container">$A$</span> is Turing reducible to a set <span class="math-container">$B$</span> then we say that <span class="math-container">$B$</span> computes <span class="math-container">$A$</span>.</p>

<p>Every noncomputable set <span class="math-container">$A$</span> computes an immune set, namely <span class="math-container">$\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$</span>.</p>

<p>(If <span class="math-container">$A$</span> 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 before applying the hat operation.)</p>

<p>For instance if <span class="math-container">$A$</span> is the set of prime numbers then we may write
<span class="math-container">$$A=A(0)A(1)A(2)\dots=00110101000101000101\dots$$</span>
and then <span class="math-container">$\sigma=0011010$</span> is a prefix of <span class="math-container">$A$</span> whereas <span class="math-container">$010011$</span> is not.</p>

<p>Therefore the complexity class of <strong>sets that compute only non-immune sets</strong> is just the computable sets <span class="math-container">$\mathsf{R}$</span>.</p>

CC BY-SA 4.0
2019-11-23T18:33:59.463Z
(i) What do you mean by "a set computes another set" (used twice above)?  (ii) What does it mean for a string $\sigma$ to be a prefix of a set $A$?  Do you mean, we concatenate all of the strings in $A$, to get an infinite string, and then let $\sigma$ be any prefix of that string?  (But with this interpretation your construction doesn't have to give an immune set.  Let $A$ contain the unary encodings of TMs that halt on blank tape.  Then $A$ is not computable, but $\hat A = 1^*$, which is surely not immune.)
Neal Young
CC BY-SA 4.0
2019-11-23T19:36:24.783Z
@NealYoung if $A$ is a set of strings then we first turn it onto a set of integers or equivalently an infinite binary sequence before applying the hat operation.
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-11-23T23:02:38.310Z
I don't understand your correction.  For example, I can encode the halting problem by a set $$A = \{f(M) : M \text{ halts on blank tape}\}$$ where $f(M)$ is computed as follows: encode $M$ in binary by a standard encoding, let $i(M)$ be the integer representing $M$ in that encoding, then take $f(M) = 2^{i(M)}-1$.  Then $A$ is an undecidable set of integers (encoded in binary), but all its integers, in binary, contain only 1's, so again $\hat A = 1^*$.  What am I missing?
Neal Young
CC BY-SA 4.0
2019-11-23T23:37:59.897Z
I see, you are assuming that the strings in $A$ are encoded in something like a set of prefix-free codewords, so from each prefix $\sigma$ I can uniquely determine the corresponding strings in $A$.  Given this, if $\hat A$ is not immune, I can recursively enumerate arbitrarily long strings in $\hat A$, so can recursively enumerate $A$.  So if $A$ is not r.e., then $\hat A$ is not immune.
Neal Young
CC BY-SA 4.0
2019-11-23T23:40:33.833Z
@NealYoung yes, in fact it works with recursive in place of r.e.
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-11-25T01:39:55.427Z
Wow, I didn't expect this. I had assumed R and not immune would be distinct. Thanks! And sorry for the late response, I had been busy this weekend and didn't get a notification.
Matthew Ferland
CC BY-SA 4.0
2019-11-22T06:52:09.887Z
2019-11-23T19:44:45.177Z
2019-11-23T19:44:45.177Z
Bjørn Kjos-Hanssen
<p>At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and co-RE. However, something else defined through computability theory is the concept of an immune set. Immune sets are ones where you are unable to enumerate even an infinite subset.</p>

<p>My question is this: is there a complexity class of decision problems where an infinite subset of "yes" instances can be enumerated, and is there a "better" name for it than "not immune"? I ask this because complexity classes are typically named for what they are, but "immune" describes what the decision problem is not.</p>

CC BY-SA 4.0
2019-11-22T02:26:23.340Z
I doubt it. "Not immune" is precisely the concept you're going for - I don't know of any theorem saying that "not immune" is equivalent to "yes [something]". I'm not sure I'd call "not immune" a complexity class though - it's more like the complement of one. If a set is immune then any set which reduces to it with infinite image must also be immune. So immunity is almost downward closed under reductions (a property we generally like complexity classes to have). Calling this a complexity class would be like calling "not in NP" a complexity class. Just feels strange.
Joshua Grochow
<complexity-classes><fl.formal-languages>
Term for a set that is not immune
Matthew Ferland
# Term for a set that is not immune

(Asked by: username_0 on 2019-11-22)

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and co-RE. However, something else defined through computability theory is the concept of an immune set. Immune sets are ones where you are unable to enumerate even an infinite subset.

My question is this: is there a complexity class of decision problems where an infinite subset of "yes" instances can be enumerated, and is there a "better" name for it than "not immune"? I ask this because complexity classes are typically named for what they are, but "immune" describes what the decision problem is not.

**Tags:** complexity-classes, fl.formal-languages

> **Comments:**
> **username_1**: I doubt it. "Not immune" is precisely the concept you're going for - I don't know of any theorem saying that "not immune" is equivalent to "yes [something]". I'm not sure I'd call "not immune" a complexity class though - it's more like the complement of one. If a set is immune then any set which reduces to it with infinite image must also be immune. So immunity is almost downward closed under reductions (a property we generally like complexity classes to have). Calling this a complexity class would be like calling "not in NP" a complexity class. Just feels strange.  

---

## 1 answers

### Answer by username_2 on 2019-11-22. Score: 4 | Accepted answer

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 before applying the hat operation.)

For instance if $A$ is the set of prime numbers then we may write
$$A=A(0)A(1)A(2)\dots=00110101000101000101\dots$$
and then $\sigma=0011010$ is a prefix of $A$ whereas $010011$ is not.

Therefore the complexity class of **sets that compute only non-immune sets** is just the computable sets $\mathsf{R}$.

> **Comments:**
> **username_3**: (i) What do you mean by "a set computes another set" (used twice above)?  (ii) What does it mean for a string $\sigma$ to be a prefix of a set $A$?  Do you mean, we concatenate all of the strings in $A$, to get an infinite string, and then let $\sigma$ be any prefix of that string?  (But with this interpretation your construction doesn't have to give an immune set.  Let $A$ contain the unary encodings of TMs that halt on blank tape.  Then $A$ is not computable, but $\hat A = 1^*$, which is surely not immune.)  
> **username_2**: @NealYoung if $A$ is a set of strings then we first turn it onto a set of integers or equivalently an infinite binary sequence before applying the hat operation.  
> **username_3**: I don't understand your correction.  For example, I can encode the halting problem by a set $$A = \{f(M) : M \text{ halts on blank tape}\}$$ where $f(M)$ is computed as follows: encode $M$ in binary by a standard encoding, let $i(M)$ be the integer representing $M$ in that encoding, then take $f(M) = 2^{i(M)}-1$.  Then $A$ is an undecidable set of integers (encoded in binary), but all its integers, in binary, contain only 1's, so again $\hat A = 1^*$.  What am I missing?  
> **username_3**: I see, you are assuming that the strings in $A$ are encoded in something like a set of prefix-free codewords, so from each prefix $\sigma$ I can uniquely determine the corresponding strings in $A$.  Given this, if $\hat A$ is not immune, I can recursively enumerate arbitrarily long strings in $\hat A$, so can recursively enumerate $A$.  So if $A$ is not r.e., then $\hat A$ is not immune.  
> **username_2**: @NealYoung yes, in fact it works with recursive in place of r.e.  
> **username_0**: Wow, I didn't expect this. I had assumed R and not immune would be distinct. Thanks! And sorry for the late response, I had been busy this weekend and didn't get a notification.  

---

