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 }$.

Configurations are triples $(q,h,t)$ as in Configurations of a deterministic one-tape Turing machine. Write $I_M(w)=(q_0,0,t_w)$, where $t_w$ is the input word followed by blanks, the initial tape of Right-infinite tapes as finite-support functions. For the empty word it is blank everywhere. A configuration is accepting when its state is $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$, rejecting when its state is $q_{\mathrm{r}\mathrm{e}\mathrm{j}}$, and halting when either condition holds. The two halting states are distinct. The relation ${⊢}_M$ is the one-step relation of The one-step configuration relation.

A finite computation history of $M$ on input $w$ is a finite list of configurations, meaning a function on $\{0,\dots ,n\}$ with values in the configuration set (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain), written $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.