Turing Machines

to halt

To halt is simply for the machine to stop running. A program you write that finishes and returns control to you has halted; one stuck in an infinite loop, spinning forever, has not. For a Turing machine, halting is the moment the computation comes to a definite end, with a verdict attached, rather than grinding on step after step without end.

Concretely, a Turing machine halts the instant it enters one of its two designated halting states: q_accept or q_reject. There is no 'finish reading the input and then check' as with a DFA; the machine halts immediately on entering a halting state, whatever the head happens to be doing. (Some textbook conventions also let the machine halt by reaching a configuration where the transition function gives no instruction.) Halting in q_accept means halt-and-accept; halting in q_reject means halt-and-reject. Either way, the machine has produced an answer and stopped.

Halting is the dividing line that makes the whole theory interesting. A machine that halts on a given input has given a clear yes-or-no answer; a machine that fails to halt has given no answer at all, just an endless run. The distinction between a recognizer (which is guaranteed to accept members but may fail to halt on non-members) and a decider (which is guaranteed to halt on every input) is entirely about this: does the machine always stop? Determining, in general, whether an arbitrary machine halts on an arbitrary input is precisely the famous halting problem, and it is undecidable.

A machine scanning right to find the first blank halts as soon as it does: ... a a q_find b ... eventually reaches the blank, enters q_accept, and stops. A machine whose rules send it endlessly leftward over an infinite tape of blanks never halts.

Halting = entering q_accept or q_reject; the machine stops with a verdict.

Halting and accepting are different: a machine can halt by rejecting. Also, a machine halts the moment it enters a halting state, possibly before reading all the input, unlike a DFA which always reads to the end.

Also called
haltingterminatestop停機終止