2
$\begingroup$

I am having trouble solving the following task:

Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$

Prove that $D$ is not decidable by reducing $$A_{\mathrm{TM}}=\{\langle T, w \rangle \mid \text{$T$ is a Turing machine and $T$ accepts $w$}\}$$ to $D$.

My solution and proof idea

(I am not sure if they are correct.) Assume that $D$ is decidable. Let $R$ be a decider for $D$ and $S$ for $A_{\mathrm{TM}}$. We know that $A_{\mathrm{TM}}$ is not decidable. However, if we manage to show it is decidable using $R$ as subroutine, we derive a contradiction and have therefore shown that $R$ is not decidable either.

Now I have got to a point where I do not know further because I have problems finding ways of showig the contradiction since I cannot see a connection between entering all states and accepting input $w$. If the TM enters all states, it is still unclear if the input is also accepted.

I guess I have to run R on a modification of $T$ so that I can derive a contradiction.

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – dkaeae May 31 '19 at 7:06
  • $\begingroup$ Thank you very much for your feedback. I have edited my post accordingly, I hope it now fits the criteria. Initially, I was not planning to write a please-say-if-my-proof-is-correct question, but I thought some people would complain that I did not even bother to provide a solution and make them do the work. $\endgroup$ – user105975 May 31 '19 at 8:44
1
$\begingroup$

Given a TM $T$, consider the machine $T'$ which, on input $w$, simulates $T$ on $w$ and enters a special state $q$ if and only if has determined that $T$ accepts $w$. Note you can easily guarantee $T'$ never enters $q$ prior to $T$ accepting $w$. Moreover, you can make sure that, once $T'$ enters $q$, it starts to cycle between all its states indefinitely. (For instance, have $T'$ write a special tape symbol so it knows it is supposed to do so.)

For an arbitrary $T$, producing the description of $T'$ is computable. I'll leave it to you to fill in the gaps so this is a full-fledged reduction.


As a rule of thumb, these exercises can usually be solved by producing description of machines (in this case, $T'$) which encode the answer to the original problem ($A_{\mathrm{TM}}$) in their own behavior. In this particular case, the idea is to establish the equivalence between $T'$ entering all its states and $T$ accepting $w$.

$\endgroup$
0
$\begingroup$

GENERAL HINT: we know that $A_{TM}$ is undecidable. So we know that a TM $V$ that can decide $A_{TM}$ does not exist by definition. Now suppose that you have a TM $V_{2}$ that can decide the language $D$. You need to find a way (and this is the hard part of the exercise which i leave to you) for produce the machine $V$ starting with $V_{2}$. Now if you can do it, since $V$ does not exist, you can conclude that $V_{2}$ cant exist neither because otherwise there would be a contradiction.

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