# Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \}$ Turing recognizeable?

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?

• 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. – lox May 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.
• Your claim "But that means that it should know if $M$ loops forever or not" is unsubstantiated. – Yuval Filmus May 19 at 15:03
• You should explain why "that means that it should know if $M$ loops forever or not", and indeed what "know" means in this context. – Yuval Filmus May 19 at 15:34