Configurations of a deterministic one-tape Turing machine

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 )$. A configuration of $M$ is a triple $C=(q,h,t)$ where $q\in Q$ is the current state, $h\in \mathbb{N}$ is the current head position, and $t:\mathbb{N}\to \mathrm{\Gamma }$ is a tape content in the sense of Right-infinite tapes as finite-support functions.

The symbol currently scanned in $C$ is $t(h)$. The configuration is nonhalting when $q\mathrm{\notin }\{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$.

For later encoding arguments it is convenient to write a configuration as a finite word over the alphabet $Q\cup \mathrm{\Gamma }$: if $r=\max (\{h\}\cup \mathrm{supp}(t))$, and $a_i:=t(i)$ for $0\le i\le r$, then the associated configuration word is $a_0{a}_1\cdots a_{h-1}q{a}_h\cdots a_r\mathrm{.}$ The state symbol is inserted immediately before the scanned tape symbol, and the word is long enough to include the head position even when the scanned cell is blank.

• This is the modern full-configuration convention: state, head position, and whole finite tape data are all part of the object.

• Turing's original narrower word "configuration" for the pair "state plus scanned symbol" is not the convention used on this page.