Computability - The language of all strings of even length

Question

Define a language $L$ as follows: $$L = \{\langle M \rangle \in \{0, 1\}^* | M\text{ is a TM that halts on all strings of even length} \}$$

I can prove that $L$ is not decidable/recursive, but is it recognisable/recursively enumerable? My intuition is that $L$ is unrecognisable because suppose there exists a TM $N$ that recognises $L$, $N$ would have to test all strings of even length which is countably infinite.

I have tried reducing $HALT^-$ to $L$ but not succeeded. Is it unrecognisable or not? How would you prove it?

Thanks.

Answer 1

$L$ is not recognizable. To avoid confusion, my assumption is that by $\text{HALT}^-$ you mean the language $\{\text{code}(M) \ w \mid M \text{ does not halt on } w\}$. We know that $\text{HALT}^-$ is not recognizable, thus showing $\text{HALT}^- \leq L$ implies that $L$ is not recognizable.

For showing that $\text{HALT}^- \leq L$, we have to give a computable mapping $\text{code}(M)\ w \mapsto \text{code}(M')$ such that $M$ does not halt on w iff $M'$ halts on all input of even length. For a given $M$ and $w$, define $M'$ to be the TM that behaves as follows: It checks the length $l$ of its input. If $l$ is uneven, it does something arbitrary. If $l$ is even, $M'$ simulates $M$ for $l/2$ steps on $w$. If $M$ halts during this simulation, $M'$ goes into an infinite loop, otherwise $M'$ halts.

You can easily verify that this mapping has the desired properties. It is clearly computable and:

• If $M$ does not halt on w, then $M'$ will for any input of even length $l$ simulate $M$ for $l/2$ steps on $w$ without the simulation halting, thus by definition $M'$ will halt afterwards.
• If $M$ does halt on $w$ (after $k$ steps), then $M'$ does not halt on all inputs of even length, because for inputs of length $2k$ it will simulate $M$ on $w$ for $2k$ steps, with the simulation halting, thus by definiton of $M'$ it will go into an infinite loop.