# Regarding a theorem that says a language that is Turing-Recognizable iff some enumerator enumerates it

I am reading the proof of Theorem 3.21 in Sipser's textbook.

Theorem 3.21 A language is a Turing Recognizable iff some enumerator enumerates it.

First direction (<==). Given an Enumerator E that enumerates language B, then we want to construct a TM M s. t. M that recognize language B. In order to do that, we do the following:

M="On input string x

1. Run E and compare each printed string with x
2. If x ever appears in the output of E, accept."

Given the following fact:

A TM M accepts input w if a sequence of configurations $$C_1, C_2, ..., C_k$$ exists s. t. $$C_1$$ is the starting configuration, $$C_2$$ to $$C_{k-1}$$ is the process configuration and $$C_k$$ is the accepting configuration.

My question: It is not clear how E accepts? e.g. What it does from my point of view is: It runs E without any input, if ever E printed out an arbitrary string, let's call it r, then if r==x, then we accept. I thought that we should do some processing like with given input x, then we should do some computation (moving from configuration to another) until we get to some arbitrary string that should be the output of the accepting state.

Note that I read all related answers to this question, but it didn't cover my question. For example: this and this.

• E is an enumerator. It doesn't accept. It simply prints all of the values in $L$ one after another. Also, comparing $r$ to $x$ is "some computation", so I didn't really understand what you are asking here. – nir shahar Mar 12 at 16:46
• @PålGD Yes E doesn't accept anything. So, we just want to construct M from E (since E is given) to show that language B is recognizable in M. You said that if x is ever produced by E, then M goes to an accepting state. But x is the input, it is not the accepting state – user777 Mar 12 at 16:50
• @user777 what are you asking here? – nir shahar Mar 12 at 16:51
• Are you asking how can we construct such an $M$? Because for this - you have answered yourself: run $E$ and for every string $r$ it outputs, if $r==x$ then accept. – nir shahar Mar 12 at 16:51
• @nirshahar My question is: Why if r == x then accept? for example, there is no computation here. All what it does is comparing the input string with the one that E produced, if they equal, then accept. But it should be something like suppose M runs with input x, then it ends up at some string, let's call it s. Then E should check that string s if it is in the accepting state or not. If so, then accept. Is the question clear now. – user777 Mar 12 at 16:57 