I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem *3.17 (p.161) which I can not solve. Any hints (not answers) from which side to attack it?

Let $B=\{M_1, M_2, ...\}$ 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.

  • $\begingroup$ note: the answer by Shaull is wrong and should be deleted. $\endgroup$
    – xdavidliu
    Aug 22, 2020 at 15:08
  • $\begingroup$ Indeed, I seemed to have missed the "and vice versa" in the question. Since the answer is accepted, I cannot delete it. If the user is still around, then please un-accept, so I can delete. $\endgroup$
    – Shaull
    Aug 22, 2020 at 15:14

3 Answers 3


Technical hint: assume that every string is a legal encoding of a TM. Can you solve this now?

Intuitive hint: the language $C$ can contain many other encodings as well as those that are equivalent to the machines in $B$. Perhaps so many that $C$ becomes decidable.

  • 1
    $\begingroup$ either your technical hint or the fact that "TM-rec language has an enumerator that prints all $M_i$ one by one" helped to solve it!) i put the answer (hope correct) here $\endgroup$
    – Ayrat
    Sep 30, 2013 at 9:18
  • $\begingroup$ Indeed. In a way, $\Sigma^*$ satisfies this. $\endgroup$
    – Shaull
    Sep 30, 2013 at 14:23
  • 1
    $\begingroup$ @Shaull this would not work, as you need also that for any TM description in $C$ there would exist an equivalent TM description in $B$. $\endgroup$
    – user44551
    Nov 16, 2017 at 8:49
  • 2
    $\begingroup$ @user44551 - you're right, of course. I don't know what I was thinking back then. $\endgroup$
    – Shaull
    Nov 16, 2017 at 8:55
  • $\begingroup$ @Ayrat file not found. $\endgroup$
    – Idonotknow
    Mar 18, 2018 at 10:08

Let $M$ be the Turing machine recognizing $B$.


For a Turing machine, try to encode the running time required for $M$ to accept it into itself, so that one can simulate $M$ on it without going into infinite loop.

Complete Answer

Let $f$ be a computable bijection from $\mathbb{N}_0^2$ to $\mathbb{N}_0$, where $\mathbb{N}_0$ is the set of non-negative integers.

Define a state of a Turing machine to be isolated if no state can be transitioned to it and it cannot be transitioned to any state. Obviously adding or deleting isolated states does not affect the function of a Turing machine.

Define $M_d$ to be a decidable Turing machine, which works as follows on input <$M_w$> where $M_w$ is a Turing machine.

  1. Compute the number $n$ of isolated states in $M_w$.
  2. Let $(n_1,n_2)=f^{-1}(n)$.
  3. Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states.
  4. Simulate $M$ on <$M_w'$> with at most $n_2$ steps.
  5. If $M$ accepts, accept; otherwise, reject.

Consider $M_i$ (recall $M$ accepts <$M_i$>). Suppose $M$ runs in total $n_2$ steps on <$M_i$> and $M_i$ has $n_1$ isolated states. Let $M_i'$ be the Turing machine that is almost the same as $M_i$ except it has $f(n_1, n_2)$ isolated states. Now $M_i'$ and $M_i$ are functionally equivalent, and easy to see <$M_i'$> is accepted by $M_d$.

On the other hand, suppose <$M_w$> is accepted by $M_d$ and $M_w$ has $n=f(n_1,n_2)$ isolated states. Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states. Now $M_w'$ and $M_w$ are functionally equivalent, and easy to see <$M_w'$> is accepted by $M$.

So the language deciding by $M_d$ is what we want.

  • $\begingroup$ Thank u so much for your answer...... could you please see this question also cs.stackexchange.com/questions/89151/… $\endgroup$
    – Idonotknow
    Mar 11, 2018 at 8:21
  • $\begingroup$ It is not clear for me why you put your solution in this form ...... what is the intuition behind your solution, could you clarify this please? $\endgroup$
    – Idonotknow
    Mar 18, 2018 at 10:16
  • $\begingroup$ @Idonotknow The hint part is the intuition. $\endgroup$
    – xskxzr
    Mar 18, 2018 at 10:33
  • $\begingroup$ Could you please look at this question if you have time? ...... Many thanks! $\endgroup$
    – Idonotknow
    Mar 18, 2018 at 10:45
  • 1
    $\begingroup$ @Idonotknow $f$ is used to make the number of isolated states of a TM be able to represent two numbers (the number of isolated states of the original TM and the required steps for $M$ to run on the original TM). $\endgroup$
    – xskxzr
    Mar 19, 2018 at 4:58

Here's a much simpler answer that uses the same idea as @xskxzr's answer. I found the bijection used in that answer not really necessary: it's much simpler to just directly store the number of steps itself in the description.


For each description accepted by the original recognizer, construct a modified equivalent description that also stores the number of steps required by the recognizer to accept. A decider can then read this number and then simulate the original recognizer for this many steps.


As in the answer by @xskxzr, define an isolated state to be a state with no transitions to and from it. Hence, for any description, we are free to choose the number of isolated states to be any arbitrary integer, without changing the functionality of the description. Hence, this becomes a mechanism to store an arbitrary non-negative integer in a description.

Now suppose we have a machine that recognizes $\{X_1, X_2, X_3, \ldots\}$, where each description $X_i$ is accepted by the recognizer in $n_i$ steps.

Now define descriptions $Y_i$ which are functionally equivalent to $X_i$ except with $n_i$ isolated states. We can now easily construct a decider that decides $\{Y_1, Y_2, Y_3, \ldots\}$ by first counting the number $n$ of isolated states in the input string $Y$, and then simulating the original recognizer with $n$ steps. Clearly, there's a one-to-one correspondence between $X_i$ and $Y_i$, and the decider will always terminate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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