Skip to main content
Computer Science

Return to Question

Formatting, language tweaks
Source Link
dkaeae
dkaeae
  • 5k
  • 1
  • 16
  • 31

So i'mI'm working on a problem that says:

$"$Is the following language Turing recognizable (recursively enumerable) ?problem:

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

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 is that suppose: 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?

Thanks.

So i'm working on a problem that says:

$"$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 is that 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?

Thanks.

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?

edited title
Link
Da Mike
Da Mike
  • 243
  • 1
  • 3
  • 12

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

Source Link
Da Mike
Da Mike
  • 243
  • 1
  • 3
  • 12

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

So i'm working on a problem that says:

$"$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 is that 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?

Thanks.