Why does this algorithm not prove that a language is Turing recognisable?

Question

I saw this example in a textbook and a statement saying that this algorithm cannot be used for the forward direction of a proof that proves a language is Turing recognisable iff some enumerator enumerates it.

$s_1, s_2$ ... is a list of strings over Σ*

E = Ignore the input.

1. Repeat the following for i = 1, 2, 3, ...
2. Run M on $s_i$
3. If it accepts, print out $s_i$

I know it's to do with step 2 but I'm not sure how that changes things.

Answer 1

Your question is missing relevant details and your title doesn't seem to match. I am going to assume you mean to ask

Suppose $M$ recognizes a language. Why does the given algorithm $E$ not enumerate the language?

The recognizer $M$ could potentially do one of three things on a given input:

• Accept
• Reject
• Never halt

If $M$ never halts, then $E$ gets stuck, unable to proceed any further.

This approach to enumerating a language needs to be fixed by some multi-threading scheme that allows you to run $M$ on all inputs in parallel, so that $M$ looping forever on some input doesn't block the overall program.

Answer 2

If $M$ loops on $s_i$ in step 2 then $E$ will never print any $s_k$ where $k \gt i$ even if $s_k$ is a string in the language.

To get around this, you use "dove-tailing".

E = Ignore the input.

1. for n = 1, 2, 3, ...
2. $\quad$ for i = 1, 2,...n
3. $\quad\quad$ Run M on $s_i$ for $n$ steps
4. $\quad\quad$ If $M$ has accepted after $n$ steps, print out $s_i$

Note lines 1 and 2.
Each time through the loop in line 1, you run $M$ on an increasingly larger number of strings for an increasingly larger number of steps.
This guarantees that if a string is in the language, E will eventually print it out (perhaps more than once)