1
$\begingroup$

The normal argument for a decidable language to build an enumerating machine is given as follows:

Let $M$ be a Turing machine which decides a language $L$, and let $s_1,s_2,\ldots$ be a list of all strings in $\Sigma^{*}$.

Consider the following enumerating machine:

  • Ignore the input
  • Repeat the following for $i = 1,2,3,\ldots$:
    1. Run $M$ on $s_i$
    2. If it accepts, print out $s_i$

This is what I see as a standard way of building an enumerating machine in case of decidable Turing machine.

I have few doubts about it:

  1. How are we going to run $M$ on $s_i$? Are we going to write $s_1, s_2,\ldots$ one by one on enumerating machine working tape?

  2. Is an enumerating machine made to run on all words in $\Sigma^{*}$ one by one?

If yes, then consider the enumerating machine constructed for a general Turing machine. The standard way is:

  • Ignore the input
  • Repeat the following for $i=1,2,3,\dots$:
  • Run $M$ for $i$ steps on each input $s_1,s_2,s_3,\dots$
  • If any computations accept, print out the corresponding $s_j$

The above is a standard way also mentioned in the Sipser book.

Now here how are we making $M$ on $s_1,s_2,s_3$, say in step 3?

Will this go to enumerating machine working tape?

Will the working tape be generated by the enumerating machine or fed as in in the case of a Turing machine?

  1. If enumerating machine is not made to run on all words in $\Sigma^{*}$ one by one, then in the above construction of our enumerating machine, how are we going to get the words $s_1,s_2,\ldots$ on its working tape?

I am confused about the way enumerating machine works.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.