0
$\begingroup$

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: enter image description here

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?

$\endgroup$

marked as duplicate by Raphael Mar 18 '18 at 15:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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! $\endgroup$ – Raphael Mar 18 '18 at 15:47
  • $\begingroup$ "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? $\endgroup$ – Raphael Mar 18 '18 at 15:47
  • $\begingroup$ @Raphael all the solution I did not understand ..... this is why I asked the question another time. $\endgroup$ – Idonotknow Mar 18 '18 at 16:24
  • $\begingroup$ @Raphael how can I change images into words on this site ..... could you please tell me? $\endgroup$ – Idonotknow Mar 18 '18 at 16:25
  • $\begingroup$ 1) People won't be able to give you another answer unless you say what you didn't understand. 2) You type the words. $\endgroup$ – Raphael Mar 18 '18 at 17:03
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Do you mean the pumping lemma? $\endgroup$ – Idonotknow Mar 18 '18 at 14:32
  • $\begingroup$ @Idonotknow No, I mean the padding lemma, as in math.uni-hamburg.de/home/khomskii/recursion/notes3.pdf $\endgroup$ – chi Mar 18 '18 at 14:57
  • $\begingroup$ Is this a proof of the equivalence only ? $\endgroup$ – Idonotknow Mar 18 '18 at 18:27
  • 1
    $\begingroup$ @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." $\endgroup$ – chi Mar 18 '18 at 18:29

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