Deterministic one-tape Turing machines with designated accept and reject states

A deterministic one-tape Turing machine with designated accept and reject states is a tuple $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ such that:

• $Q$ is a finite set of states.
• $\mathrm{\Sigma }$ is a finite input alphabet.
• $\mathrm{\Gamma }$ is a finite tape alphabet with $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$.
• $\bigsqcup \in \mathrm{\Gamma }$ is the blank symbol.
• $q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\in Q$ are pairwise distinct.
• $\delta$ is a function $\delta :(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}\mathrm{.}$

Thus whenever the machine is in a nonhalting state $q$ and scans a symbol $a\in \mathrm{\Gamma }$, the value $\delta (q,a)=(q^{\mathrm{\prime }},b,D)$ specifies exactly one next state $q^{\mathrm{\prime }}$, exactly one symbol $b$ to write in the currently scanned cell, and exactly one head move $D\in \{L,R\}$.

The intended tape is right-infinite and indexed by the natural numbers (Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$, 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 tape contents, configurations, and one-step dynamics are fixed in the next items.

• The transition function is total on the nonhalting state-symbol pairs. The machine halts by entering one of the distinguished states $q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ or $q_{\mathrm{r}\mathrm{e}\mathrm{j}}$, not by leaving $\delta$ undefined.

• This item fixes only the base deterministic one-tape model. Multitape and nondeterministic variants are introduced later on the same page.