<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2020-04-23T20:44:18.757Z
2020-04-23T20:44:18.757Z
lacker
<p>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?</p>

CC BY-SA 4.0
2020-04-24T02:52:14.813Z
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. https://cstheory.stackexchange.com/help/on-topic
The Computer Science Stack Exchange might be more suitable: https://cs.stackexchange.com/
gdmclellan
<turing-machines><undecidability>
Show that membership in L is undecidable
Kwaku
# Show that membership in L is undecidable

(Asked by: username_0 on 2020-04-23)

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?

**Tags:** turing-machines, undecidability
> **Comments:**
> **username_1**: 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. https://cstheory.stackexchange.com/help/on-topic The Computer Science Stack Exchange might be more suitable: https://cs.stackexchange.com/  

---

## 1 answers

### Answer by username_2 on 2020-04-23. Score: 1

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.


---

