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.)