3
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ "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. $\endgroup$
    – Raphael ♦
    Apr 17 '16 at 5:47
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Apr 17 '16 at 16:27
  • $\begingroup$ @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. $\endgroup$
    – Spencer
    Apr 19 '16 at 4:31
  • $\begingroup$ @Spencer I think you misunderstood something. Neither the Halting problem nor its undecidability proof talk about such "circles". $\endgroup$
    – Raphael ♦
    Apr 19 '16 at 6:46
  • $\begingroup$ @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. $\endgroup$
    – Spencer
    Apr 19 '16 at 10:09
1
$\begingroup$

The only terms I have seen used with any consistency are "dead" and "unreachable".

There is also the dual, "unproductive" states. This term comes from formal grammars and means that you have a state/non-terminal from which you can not reach a final state/terminal string.

Improve this answer
$\endgroup$
1
$\begingroup$

There is no such thing as a state that no static analysis can determine is inaccessible. For any Turing machine and any state that is actually inaccessible, there exists a static analysis algorithm that can determine that the state is inaccessible.

Perhaps what you are thinking of is that there is no static analysis algorithm that can identify all inaccessible states: for any static analysis algorithm, there exists a Turing machine with a state that is actually inaccessible but that the algorithm can't tell is inaccessible. That's not the same thing. The order of the quantifiers matters.

Therefore, you're asking for the name of a thing that doesn't exist. There is no such name. I'm afraid the only way to give a satisfactory answer to the question is to un-ask the question.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ "For any Turing machine and any state that is actually inaccessible, there exists a static analysis algorithm that can determine that the state is inaccessible." -- If you are referring to the two trivial algorithms, using the verb "determine" is probably misleading. $\endgroup$
    – Raphael ♦
    Apr 18 '16 at 6:57
  • 2
    $\begingroup$ If an algorithm falls in the forest and no-one is around to choose it, is it still an algorithm? $\endgroup$
    – Spencer
    Apr 19 '16 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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