Watching a Turing machine run, why can you never conclude from the run alone that it will never halt?

## Halting is a property of the run A Turing machine halts when it reaches a configuration for which the transition table has no entry (equivalently, an explicit halting state). Until that happens the run continues, one configuration yielding the next by exactly one entry. A **configuration** is the whole snapshot — current state, tape contents, head position — and for a deterministic machine it fixes everything that comes after it. An observer, however carefully instrumented, sees a finite prefix of that sequence. The prefix is consistent with two futures: the machine stops shortly, or it never does. Nothing in the prefix distinguishes them, because 'has not halted in t steps' is exactly what a machine that halts at step t+1 looks like at time t. ## Two ways a run fails to halt | non-halting behaviour | what the configurations do | caught by remembering configurations? | |---|---|---| | exact cycle | one configuration recurs, so the block of steps between the two occurrences repeats forever | yes, the moment the repeat is seen | | unbounded divergence | the head keeps reaching fresh blank cells and writing, so every configuration is new | no, there is never a repeat to see | The first row is a genuine proof technique, with two conditions attached: - the machine must be **deterministic**, so that the same snapshot always yields the same successor; - what recurs must be the whole **configuration**. A repeated *state* proves nothing at all — states recur constantly while the head walks along a block of symbols. The second row is why the technique is not a general test. A machine that marches right, writing as it goes, has a different tape and a different head position at every step; there is no repeat, and the search for one runs forever while consuming ever more memory to store what it has seen. ## The bounded-region special case There is one setting in which the cyclic case is the *only* case. If a run never leaves a region of `m` cells, then with `|Q|` states and an alphabet of size `a` there are at most `|Q| x m x a^m` distinct configurations available to it. A confined run that takes more steps than that must, by counting, have revisited one — and therefore loops. That bound is correct and also useless at any realistic size: it grows exponentially in the width of the region, so the step count it licenses is far beyond anything that could be watched. It is a reasoning tool, not a monitoring strategy. ## Why this matters outside the model The asymmetry is not an artefact of the abstraction; it is the shape of every runaway computation an engineer meets. - 'Still running' and 'will never finish' produce the same observation at every finite moment, so a system must **decide** at some point rather than **discover**. - The decision is bought with a budget, and the budget should be something intrinsic to the computation — a count of steps — rather than wall-clock time, so that the same input gives the same verdict on a faster or slower machine. - What is reported back matters. 'Exceeded the budget' is a true statement; 'this computation is an infinite loop' is not, and a system that says the second is asserting more than it observed. - Recording the configuration at the moment of the kill — the state, the head position, a window of tape around it — is what turns an unhelpful timeout into a diagnosis, because it shows the author where the machine was circling. ## Three statements, only two of which you can make 1. **This run has not halted in t steps.** Always available, always true, and much weaker than it sounds. 2. **This deterministic run will never halt.** Available only when a configuration has recurred, and only then. 3. **This run will halt eventually.** Never available from watching: the observation that would establish it is the machine halting. Most reporting bugs in this area are statement 1 dressed up as statement 2, and the dressing is usually the word *detected*. A final distinction worth keeping straight: whether some general procedure could settle the question by *analysing* a machine rather than watching it run is a different question, with an answer of its own in a different corner of the theory. Everything above concerns what an observer of a run can conclude, and from the run alone the honest conclusion is always the weaker one.