# Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- inaccessible states in a Turing machine. These are simply defined (look at page 43 here if you need a source) as states that are never reached.

The definition I linked to is accompanied with a state graph that shows an obviously inaccessible state. Simplified:

(q0)-1->((q1))<-0,1-(q2)


If q0 is the start state, q2 is obviously inaccessible. This is analogous to the deliberately-disabled code that was the premise of the EL&U discussion.

But I'm wondering about those states that are inaccessible, but you will never know it, because they're just lost in the jungle.

These states all have a path from the start state in the machine's state graph. But no matter how long the machine runs, the particular combination of state and symbol to make the number transition into that state never appears.

For some of these states, static analysis can determine if they're inaccesssible.

For the rest, no analysis will ever be able to determine if the state is ever reached. For example, if you could determine whether every halt state is reached or not, you would have just solved the (unfortunately-named, but don't get me started) Halting Problem. Let's leave out states that machines reach serendipitously if you run them long enough.

Is there a more specific term than 'inaccessible state' for this? (It's a shame 'inaccessible states' can't mean specifically this; it would have been a nice parallel with inaccessible sets from set theory.)

• "unfortunately-named, but don't get me started" -- please do! The Halting problem has always struck me as one of the more aptly named concepts in (T)CS and mathematics. – Raphael Apr 17 '16 at 5:47
• the state transitions form a graph that can be analyzed to easily find disconnected states "for any input". however there is a more subtle aspect that some states may never be reached in any actual execution based on runtime dynamics, "for all inputs", hence this is essentially equivalent to the halting problem. (two current answers dont seem to be aware of this subtlety.) so just definining what an inaccessable state is involves some subtlety and similar definitions are not exactly equivalent and end up being different. yet another aspect is that if one restricts "legal" inputs some way. etc – vzn Apr 17 '16 at 16:27
• @Raphael I'm not sure it would get a good reception. Turing's original paper on computability does include a halting concept, but not in the context of the decidability problem that all the later literature calls the 'halting' problem. The problem that can't be solved is whether a machine is 'circle-free' or not. That can also mean churning around several states without ever printing any more digits. – Spencer Apr 19 '16 at 4:31
• @Spencer I think you misunderstood something. Neither the Halting problem nor its undecidability proof talk about such "circles". – Raphael Apr 19 '16 at 6:46
• @Raphael Here is a link to the paper: Turing 1936. The problem is there but not described in terms of 'halting'. Any way not on topic for this discussion. – Spencer Apr 19 '16 at 10:09