Right-infinite tapes as finite-support functions

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 tape content for $M$ is a function $t:\mathbb{N}\to \mathrm{\Gamma }$ (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, The natural numbers $\mathbb{N}$ (von Neumann)) such that the support $\mathrm{supp}(t):=\{n\in \mathbb{N}:t(n)\mathrm{\ne }\bigsqcup \}$ is finite.

Thus the tape is indexed by the natural numbers, extends infinitely to the right, and is blank except at finitely many cells. If the head is instructed to move left from cell $0$, it remains at cell $0$.

For an input word $w=a_0{a}_1\cdots a_{m-1}\in {\mathrm{\Sigma }}^{\ast }$, the initial tape $t_w:\mathbb{N}\to \mathrm{\Gamma }$ is defined by $t_w(i):=\{\begin{array}{ll}{a}_i,& 0\le i<m,\\ \bigsqcup ,& i\ge m\mathrm{.}\end{array}$ Its support is contained in $\{0,\dots ,m-1\}$ and is therefore finite.

• This finite-support convention is a clean way to formalize the usual picture "the tape is blank except on a finite used segment."

• The head position is not part of the tape content; it is a separate natural number in the configuration definition.