I'm working on the following problem:

Is the following language Turing recognizable (recursively enumerable) ?

$$L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not > accept}\ 010 \} $$

The way I see it: Suppose that a machine $M$ loops forever on $010$. If a $TM$ recognizes $L$, it should accept $M$ in that case. But that means that it should know if $M$ loops forever or not, which is not possible. So, $L$ is not Turing recognizable.

Is my proof correct, and can it be more formal?

  • $\begingroup$ It's not a proof, its mostly hand waving and (your) intuition. To show $L$ does not belong in a certain class, you must show a specific TM reduction to another TM language that is known not to be in that class. $\endgroup$ – lox May 19 '19 at 16:23

You are presenting an argument which falls short of being a proof. In particular, it is not clear why a Turing machine recognizing $L$ should know whether $M$ loops forever or not; indeed, it is not so clear what do you mean by know in this context.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.

| cite | improve this answer | |
  • $\begingroup$ First of all, thank you for your answer! Now, I understand the proof you are presenting, but I don't quite get why my argument is not a proof. Could you be more elaborate on that? $\endgroup$ – Da Mike May 19 '19 at 15:02
  • $\begingroup$ Your claim "But that means that it should know if $M$ loops forever or not" is unsubstantiated. $\endgroup$ – Yuval Filmus May 19 '19 at 15:03
  • $\begingroup$ So is this specific claim false, or have I not provided a solid proof of it? $\endgroup$ – Da Mike May 19 '19 at 15:16
  • $\begingroup$ You should explain why "that means that it should know if $M$ loops forever or not", and indeed what "know" means in this context. $\endgroup$ – Yuval Filmus May 19 '19 at 15:34
  • $\begingroup$ Ok then, thank you. $\endgroup$ – Da Mike May 19 '19 at 18:19

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.