3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 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 '13 at 9:18
  • $\begingroup$ Indeed. In a way, $\Sigma^*$ satisfies this. $\endgroup$ – Shaull Sep 30 '13 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 '17 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 '17 at 8:55
  • $\begingroup$ @Ayrat file not found. $\endgroup$ – Idonotknow Mar 18 '18 at 10:08
2
+50
$\begingroup$

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

Hint

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

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.

$\endgroup$
  • $\begingroup$ Thank u so much for your answer...... could you please see this question also cs.stackexchange.com/questions/89151/… $\endgroup$ – Idonotknow Mar 11 '18 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 '18 at 10:16
  • $\begingroup$ @Idonotknow The hint part is the intuition. $\endgroup$ – xskxzr Mar 18 '18 at 10:33
  • $\begingroup$ Could you please look at this question if you have time? ...... Many thanks! $\endgroup$ – Idonotknow Mar 18 '18 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 '18 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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