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$
  • $\begingroup$ note: the answer by Shaull is wrong and should be deleted. $\endgroup$ – xdavidliu Aug 22 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 at 15:14
1
$\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.

| cite | improve this answer | |
$\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
4
+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$, 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.

| cite | improve this answer | |
$\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
0
$\begingroup$

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.

Hint

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.

Solution

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.

| cite | improve this answer | |
$\endgroup$

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.