2
$\begingroup$

Can someone help me to determine and prove if the following language is decidable or not?

I tried to think on some reductions but I can't figure it out...

$$A=\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\}$$

my try:

I built mapping reduce $E_{TM}\le_{m} B$:

$<M>\rightarrow <M>$

so I need to prove: $$<M>\in E_{TM}\iff <M>\in B$$

First direction:

$<M>\in E_{TM}\rightarrow L(M)=\emptyset \rightarrow M \text{ never visits } q_{accept} \rightarrow <M>\in B $

The problem is in the second direction. How can I promiss that if the language is empty $M$ visits all the states?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Hint: $q$ could be the accepting state. Translate the problem and see if you can apply Rice's Theorem. $\endgroup$ – A.Schulz May 7 '16 at 18:52
  • 1
    $\begingroup$ Or a direct reduction from the halting problem. $\endgroup$ – David Richerby May 7 '16 at 19:43
  • $\begingroup$ @A.Schulz are you trying to say that I can see the language as $E_{TM}=\{\text{$M$ is $TM$ and $L(M) =\emptyset$}\}$? If so, I don't know how to write it correctly... It is confusing me. $\endgroup$ – user9 May 7 '16 at 20:09
  • $\begingroup$ @user9: I wanted to say, if you can deicide $A$ then you can decide $E_\text{TM}$. (Not quite sure how $q$ is quantified in your question.) $\endgroup$ – A.Schulz May 8 '16 at 8:17
  • $\begingroup$ @A.Schulz I edited my question, Can you help me in the second direction? $\endgroup$ – user9 May 8 '16 at 17:50
1
$\begingroup$

I will assume that you're using $E_{TM}$ to mean the language $HALT=\{\langle M\rangle|\text{$M$ does not halt}\}$ and $B=A=\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\}$. Also, you should state what your mapping is because if it is just the identity (which it seems to be here) then this won't work. This is because we can have a turing machine that halts right away but also happens to have an extra state that it never reaches, so it is not the case that $B\subset E_{TM}$.

Instead, it may help to think about this more informally. If have the ability to tell whether or not a turing machine visits all of its states, how might we use this superpower to decide the halting problem? The simplest, most direct approach is to see if we can answer the question of whether $M$ visits a specific state $q\in Q$ using knowledge of $B$. Then we can reduce to the halting problem by simply asking if a given TM $M$ visits any of its accepting states.

To do this, let's see what "subsets" of $M$ are still in $B$. By this I mean that we will choose a subset $P\subset Q$ and then on any transition that goes from a state in $P$ to one in $Q\setminus P$ we will instead reroute it to a halting state. Let's call the new machine with the new accepting state along with $P$ as its states as $N_P$.

Now, we start off by looking asking if $N_P\in B$ for $P$ being the set containing just the starting state. If this TM is in $B$ then we know $M$ never visits any state other than its initial state. If it is not in $B$ then we continue by adding a new state to $P$ and asking if the new TM is in $B$, continuing until we get to a TM which is in $B$. The $P$ we end on will have to be the set of states the TM visits, and all other states are unvisited. Thus, we can tell whether a $M$ visits a certain state $Q$ by simply checking if $q$ is in the final version of $P$.

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