# Computability - The language of all strings of even length

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.

• Note that the title doesn't match your question at all. Maybe that's not important, or maybe it shows that you need to think more about what the language $L$ actually is. – David Richerby Apr 22 '19 at 9:27

$$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.
• 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.