0
$\begingroup$

I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ordering of inputs) for all words $w \in L$ (with $L \in \mathcal{L}_{RE}$) to be printed by $E$.

Now suppose $E$ lists down all words $w \in L$ by taking as input the computation history of a word $w$. The computation history is derived using transitions of a Turing Machine $TM$ that recognizes $L$. $E$ operates by checking if all segments of the computation history are valid given transitions of $TM$. To print $w$, $E$ uses a homomorphism, i.e. by printing the first segment of the computation history. In this case, the set of all words that enumerated by $E$ is equal to $L$.

But if the enumerator $E$ is a Turing Machine itself, call it $TM^E$, is it accurate to say that $TM^E$ recognizes $L$? If true, there seems to be a contradiction since $E$ does not loop - since it can check whether or not a computation history input from a lexicographic ordering follows the transitions of $TM$ and results in $w$.

$\endgroup$
  • $\begingroup$ I'm not sure I follow your definition of enumeration. However, a language can be enumerated in lexicographic order iff it is decidable; if the language is RE but not decidable, you can enumerate it, but not in lex order. $\endgroup$ – David Richerby Apr 3 at 16:32
2
$\begingroup$

An enumerator has no input. It works as follows:

  1. Generate the next computation history.
  2. Check if the computation history is valid.
  3. If the computation history is valid, print the corresponding string.
  4. Go to Step 1.

I'm unclear how your $\mathrm{TM}^E$ works. I can image the following possibilities:

  1. On input $w$, $\mathrm{TM}^E$ enumerates all computation histories and see if $w$ matches some computation history. In this sense, there is no contradiction. $\mathrm{TM}^E$ has to endlessly enumerate computation histories if $w$ matches no computation history (i.e. $w\notin L$), so it may loop.

  2. On input $w$, $\mathrm{TM}^E$ firstly constructs the computation history corresponding to $w$... but wait, how do you construct such a computation history while it may not even exist (i.e. $w\notin L$)?

  3. On input $w$, $\mathrm{TM}^E$ checks whether $w$ is a valid computation history, and accepts if it is valid. In this sense, $\mathrm{TM}^E$ does not accept $L$. Instead, it accepts the language of valid computation histories. This language is different from $L$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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