# Understanding the equivalence of a Turing machine and an enumerating machine

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.