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.


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.