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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.