-3
$\begingroup$

Let L ⸦ {0, 1}* be the language {(M, x) | Turing Machine M on input x enters every state of M at least once}. How can I show that membership in L is undecidable?

$\endgroup$
1
  • $\begingroup$ Not a research-level question. There are trivial reductions from the halting problem for Turing machines to this language. For an overview of the purpose of this site, see e.g. cstheory.stackexchange.com/help/on-topic The Computer Science Stack Exchange might be more suitable: cs.stackexchange.com $\endgroup$
    – gdmclellan
    Commented Apr 24, 2020 at 2:52

1 Answer 1

1
$\begingroup$

Pick M to be a universal Turing machine plus two states called A and B. If you enter state A, you stay in state A forever. If you enter state B, you go through some sequence that goes through all the states, ending in A. More detailed construction is left as an exercise to the reader, but this should be fairly straightforward.

Now you can diagonalize. Make D(X) that analyzes whether X(X) enters each state at least once. If it does, then go to state A; if it does not, then go to state B. You can see that D(X) enters each state iff X(X) does not enter each state. But then D = X leads to a contradiction.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.