Finite computation histories, halting computations, and divergence

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ and an input word $w\in {\mathrm{\Sigma }}^{\ast }$.

A finite computation history of $M$ on input $w$ is a finite list of configurations $C_0,C_1,\dots ,C_n$ such that $C_0=I_M(w)$ and $C_i{⊢}_M{C}_{i+1}(0\le i<n)\mathrm{.}$

Such a history is:

• accepting if $C_n$ is an accepting configuration,
• rejecting if $C_n$ is a rejecting configuration,
• halting if it is accepting or rejecting.

We say that $M$ halts on $w$ if there exists a halting computation history of $M$ on $w$.

We say that $M$ diverges on $w$ if there is no halting computation history of $M$ on $w$.

For a halting configuration $C=(q,h,t)$ and a word $u=a_0\cdots a_{m-1}$ over $\mathrm{\Gamma }\setminus \{\bigsqcup \}$, we say that $C$ outputs $u$ when $t(i)=\{\begin{array}{ll}{a}_i,& 0\le i<m,\\ \bigsqcup ,& i\ge m\mathrm{.}\end{array}$ So the tape contains exactly $u$ followed by blanks.

• On a deterministic machine there is at most one possible next configuration from a nonhalting configuration, but the definition of divergence here is simply "no halting computation history exists."

• The output convention is intentionally strict: the final nonblank tape segment must be exactly the displayed word, with no later nonblank cells.