# A second question on “Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs” [duplicate]

Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.

I saw a hint on solving this question which is given in the following picture: But I have a difficulty in constructing such enumerator $E_{0}$, Also how will I show that every machine described in $B$ has an equivalent machine in $C$ and vice versa, could anyone help me in doing so?

Also it is worth to say that the solution of this problem is found here:

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

But I could not understand it. could anyone explain the solution for me in a simple way ? and in a way depending on the above hints?

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – Raphael Mar 18 '18 at 15:47
• "But I could not understand it. could anyone explain the solution for me in a simple way ? and in a way depending on the above hints? " -- you need to be more specific. What exactly didn't you understand? – Raphael Mar 18 '18 at 15:47
• @Raphael all the solution I did not understand ..... this is why I asked the question another time. – Idonotknow Mar 18 '18 at 16:24
• @Raphael how can I change images into words on this site ..... could you please tell me? – Idonotknow Mar 18 '18 at 16:25
• 1) People won't be able to give you another answer unless you say what you didn't understand. 2) You type the words. – Raphael Mar 18 '18 at 17:03

Recall the padding lemma: given $\langle M \rangle$ we can compute $\langle N \rangle$ where $N$ is equivalent to $M$, but has a longer representation. (Essentially, we can always add more irrelevant states to a TM, effectively.)

Then, define $E_0$ to do the following:

• Run $E$ until $M_1$ is produced.
• Let $N_1 = M_1$
• Output $N_1$
• Continue running $E$ until $M_2$ is produced.
• Let $N_2$ be $M_2$, after as many paddings as needed to make its representation larger than $N_1$.
• Output $N_2$
• Continue running $E$ until $M_3$ is produced.
• Let $N_3$ be $M_3$, after as many paddings as needed to make its representation larger than $N_2$.
• Output $N_3$
• And so on.

By construction, $E_0$ prints larger and larger strings, hence its enumerated language is decidable: this is the wanted language C.

We now need to check the quivalence. For any $N_i$ in the language enumerated by $E_0$, we find an equivalent $M_i$ enumerated by $E$. Vice versa, for any $M_i$ in the language enumerated by $E$, we find an equivalent $N_i$ enumerated by $E_0$.

• Do you mean the pumping lemma? – Idonotknow Mar 18 '18 at 14:32
• @Idonotknow No, I mean the padding lemma, as in math.uni-hamburg.de/home/khomskii/recursion/notes3.pdf – chi Mar 18 '18 at 14:57
• Is this a proof of the equivalence only ? – Idonotknow Mar 18 '18 at 18:27
• @Idonotknow No, this proves the full question: "Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa." – chi Mar 18 '18 at 18:29