91Ó°ÊÓ

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

Consider the list of strings $s_1,s_2,…$ that are present in $∑*$. 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)=\mathrm{ϕ}$, then the Turing machine belongs to $\stackrel{¯}{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 $\stackrel{¯}{E_{\text{TM}}}$.

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

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

1. Repeat the following steps for $i=1,2,3,…$
2. Run the Turing machine $M$ for $i$ steps on each input string $s_1,s_2,…,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 $\stackrel{¯}{E_{\text{TM}}}$ is Turing recognizable.