0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 22 at 9:27
1
$\begingroup$

$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.
$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – FrankieYin Apr 23 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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