Skip to main content
3 of 3
Formatting, language tweaks
dkaeae
  • 5k
  • 1
  • 16
  • 31

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?

Da Mike
  • 243
  • 1
  • 3
  • 12