patternMinor
Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs
Viewed 0 times
showcanequivalentexpressedtmsdescriptionrecognizablelanguage
Problem
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.
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.
Solution
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 where $M_w$ is a Turing machine.
Consider $M_i$ (recall $M$ accepts ). Suppose $M$ runs in total $n_2$ steps on 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 is accepted by $M_d$.
On the other hand, suppose 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 is accepted by $M$.
So the language deciding by $M_d$ is what we want.
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 where $M_w$ is a Turing machine.
- Compute the number $n$ of isolated states in $M_w$.
- Let $(n_1,n_2)=f^{-1}(n)$.
- Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states.
- Simulate $M$ on with at most $n_2$ steps.
- If $M$ accepts, accept; otherwise, reject.
Consider $M_i$ (recall $M$ accepts ). Suppose $M$ runs in total $n_2$ steps on 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 is accepted by $M_d$.
On the other hand, suppose 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 is accepted by $M$.
So the language deciding by $M_d$ is what we want.
Context
StackExchange Computer Science Q#14680, answer score: 4
Revisions (0)
No revisions yet.