1

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.

Community
  • 1
Y Ahmed
  • 95
  • Not sure how to do the formatting but the 1,2,i in s1, s2 and si should be subscript. – Y Ahmed Oct 24 '17 at 14:09
  • https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference tells you how to format mathematics on this site. – Arthur Oct 24 '17 at 14:12

2 Answers2

0

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.

0

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)

user137481
  • 2,605