Question

Let .Show that $\overline{{\mathbf{E}}_{\mathbf{\text{TM}}}}$, the complement of ${\mathit{E}}_{\mathbf{\text{TM}}}$, is Turing-recognizable.

Short answer

The string is accepted by the Turing machine so the complement of $E_{\text{TM}}$ that is written as $\overline{E_{\text{TM}}}$ is Turing recognizable.

Step-by-step solution

Explain Turing Machine

Turing machine is the mathematical computation model that recognizes the strings given as input.

Show that   ETM¯, the complement of   ETM, is Turing-recognizable.

Consider the list of strings $s_1,s_2,\dots$ that are present in $\sum *$. Consider the Turing Machine $M$, check whether the machine accepts the strings from the list.

If the Turing Machine $M$ accepts at least one string $s$ from the list $L\left(M\right)=\varphi$, then the Turing machine belongs to $\overline{E_{\text{TM}}}$. If the Turing Machine does not accept any string $s_i$ from the list , then the Turing machine does not belongs to $\overline{E_{\text{TM}}}$.

The following Turing Machine recognizes $\overline{E_{\text{TM}}}$.

Consider the input , where $M$ is a Turing Machine:

1. Repeat the following steps for $i=1,2,3,\dots$
2. Run the Turing machine $M$ for $i$ steps on each input string $s_1,s_2,\dots ,s_i$.
3. If any of the strings are accepted by the Turing Machine $M$, accept. Otherwise repeat the steps.

Therefore, The string is accepted by the Turing machine so the complement of $E_{\text{TM}}$ that is written as $\overline{E_{\text{TM}}}$ is Turing recognizable.