1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – nir shahar
    Mar 12, 2021 at 16:46
  • $\begingroup$ @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 $\endgroup$
    – user777
    Mar 12, 2021 at 16:50
  • $\begingroup$ @user777 what are you asking here? $\endgroup$
    – nir shahar
    Mar 12, 2021 at 16:51
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Mar 12, 2021 at 16:51
  • $\begingroup$ @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. $\endgroup$
    – user777
    Mar 12, 2021 at 16:57

1 Answer 1

Reset to default
2
$\begingroup$

The Turing machine M is running the Turing machine E as its subroutine. In the other words, you can think of E's printer tape as another tape for Turing machine M. Although we don't know what is going on E, E's computation is part of (inside) M's computation. And of course, as nir shahr said in the comment, comparing is part of M's computation too.

I drew something maybe it can help to have some intuition.

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.