# Is it decidable whether a Turing Machine will visit every non-end state from input x?

L = {w#x | w,x ∈{0,1}∗ and Turing Machine Mw with input x visits every non-end state at least once}

I believe this problem is undecidable.

My proof would consist of me reducing L to a Halting Problem; however, the structure of these proofs seem incosistent and inconclusive. I would appreciate if I could have some constructive feedback.

My understanding of the proof:

1. Create R which decides L
2. Construct algorithm S, which decides Atm (which we reduce to L)
3. Contradiction because Atm is undecidable

This is the skeleton to most Turing Machine dicidibility related proofs I have read on the internet.

• I suggest reviewing other similar proofs that were given in class. – Yuval Filmus Jun 26 '17 at 15:32
• unfortunately as i said the structure of these proofs seem incosistent and inconclusive – Peter Bangert Jun 26 '17 at 15:53
• You need to reduce the halting problem to $L$: you're saying that, if I could decide $L$, I could decide the halting problem for Turing machines. You seem to know what you need to do, so go ahead and do it: figure out a way of deciding the halting problem using a supposed ability to decide $L$. – David Richerby Jun 26 '17 at 17:44
• "reducing L to a Halting Problem" does not allow you to state anything about the decidability of $L$. You need to reduce in the opposite direction. – chi Jun 26 '17 at 18:04
• @chi, reduction to Halting problem leads to undecibility of initial problem, which is needed to be shown. – rus9384 Jun 26 '17 at 20:47

Because the number of states in a Turing machine is finite you can enumerate all $2^n$ combinations of possible non-end states. Run the algorithm against all of them.