# I want to know where there is the flaw in my argument

I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.

$$L: \{\langle M\rangle: M\space is\space a\space TM\space and\space |L(M)| \ge3\}$$

Now thinking intuitively I conjectured that this language is semi-decidable. We can say yes when the input does belong to $$L$$. But, we can not say no when the input does not belong to $$L$$.

Now, I formulated following reduction from complement of halting problem $$\overline{HP}$$ which is not semi-decidable (non $$RE$$).

$$\overline{HP}: \{\langle M, w\rangle : M\space is\space TM\space and\space it\space does\space not\space halt\space on\space string\space w.\}$$

$$\tau(\langle M,x\rangle) = \langle M'\rangle$$.

$$M'$$ on input $$w$$ works as follows. It erases w, puts $$M$$ and $$x$$ on its tape, and runs $$M$$ on $$x$$ and accepts if $$M$$ doesn't halt on x. Otherwise it rejects.

Proof of validity of reduction:

$$\langle M,x\rangle \in \overline{HP} \implies M\space does\space not\space halt\space on\space x \implies M'\space accepts\space all\space inputs\space \implies|L(M')| \ge 3\implies M' \in L$$

$$\langle M,x\rangle \notin \overline{HP} \implies M\space does\space halt\space on\space x \implies M'\space rejects\space all\space inputs\space \implies|L(M')| < 3\implies M' \notin L$$

According to above reduction $$\overline{HP}$$ should be recursively enumerable$$(RE)$$ which it is not. So, $$L$$ should not be $$RE$$ but it indeed is $$RE$$. So, my reduction must be flawed.

Please point out where I messed up.

## 1 Answer

accepts if $$M$$ doesn't halt on $$x$$

That's not something a Turing machine can do in general: informally, keep in mind that accepting has to happen at some finite stage while we can't in general tell that a program isn't going to halt in finite time (which is why HP is undecidable).

Your $$M'$$ is implicitly treating a co-r.e. event (non-halting) as r.e. (so that it can wait for it to occur and, when it does, halt and accept).

It's worth noting that we can do this with $$HP$$ as an oracle, and this shows (correctly) that $$L$$ is r.e. over $$HP$$. But we have to be careful about what exactly that means. At first glance we might think that "r.e. over $$HP$$" implies r.e., since $$HP$$ itself is r.e., but when a set is presented as an oracle we get both positive and negative information about it. So r.e. over $$HP$$ - that is, the domain of some $$HP$$-computable partial function - is not the same as r.e.: for example, $$\overline{HP}$$ is r.e. over $$HP$$.

This is a good example of how we have to keep track of the various different reducibilities we might be using, with the relevant ones here being Turing versus many-one: in the context of this question we're interested in many-one reductions but oracles correspond to Turing reducibility.