prove that language is not deciable by reduction

510 Views Asked by At

I show you my approach to one problem, and try to assess it.
Show that following language is not decidable:
$L=\{\langle M\rangle|\text{M is Turing Machine and M has one or more unreachable state} \}$

And I try to reduct $E_{TM}$ (which is not decidable) to $L$.
$E_{TM}=\{\langle M\rangle|\text{M is Turing Machine and L(M)=}\emptyset\}$ So let $R$ will be decider for $L$.
Now, we construct $TM\ S$ for $E_{TM}$

$$S: \text{on input } \langle M \rangle:$$ $$\text{(1) Consider every subset of states of $\langle M \rangle$ }$$ $$\text{(2) Delete chosen subset of states - new machine}$$

$$\text{is called $M'$. Now, check if $M'$ has unreachable states (using R)}$$

$$\text{If it has, jump into step 2. else jump into step 3. } $$

$$\text{(3) If $M'$ has accept states reject, else accept}$$

What about this solution ?

1

There are 1 best solutions below

0
On BEST ANSWER

The reduction seems fine if you can tell how to "delete" states from a TM (especially if they are reachable).

You can make this rigorous by redefining the transition function. If $\delta_M(s)$ is a deleted state, return a new, special state $s_0$. Define $\delta_{M'}(s_0) = s_0$ and make it a rejecting state.