Let S_TM = { | M is a Turing Machine and M accepts some string from ?*}.

a) Explain why the following proof that S_TM is Turing recognizable is incorrect.

Proof: Let (w₁,w₂,w₃,...} be the list of all strings in ?* in short lexicographic order. Then, the following Turing Machine R is a recognizer for S.

On input :

1. Set i = 1

2. Simulate the execution of M on w_i. If M accepts, accept.

3. Increment i and repeat step 2.

b. Modify this incorrect proof to give a correct proof that S_TM is recognizable. (HINT: Consider the proof that a language is Turing recognizable if and only if some enumerator enumerates it.)

c)Now, show that E_TM = { | M is a Turing Machine and L(M) = } is not Turing recognizable.