Multitape and nondeterministic Turing machine variants

Fix finite alphabets $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$ with $\bigsqcup \in \mathrm{\Gamma }$, and a finite state set $Q$ with distinct states $q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\in Q$.

For an integer $k\ge 1$, a deterministic $k$-tape Turing machine has the same finite control data as the one-tape model, but carries $k$ right-infinite tapes and $k$ head positions. Its transition function has the form ${\delta }_k:(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times {\mathrm{\Gamma }}^k\to Q\times {\mathrm{\Gamma }}^k\times \{L,R{\}}^k\mathrm{.}$ So one step reads one symbol from each tape, writes one symbol on each tape, and moves each head left or right.

A nondeterministic one-tape Turing machine has the same data $(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}})$ as the deterministic model, but replaces the transition function by a finite-valued transition map $\mathrm{\Delta }:(Q\setminus \{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\})\times \mathrm{\Gamma }\to {\mathcal{P}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(Q\times \mathrm{\Gamma }\times \{L,R\}),$ where each $\mathrm{\Delta }(q,a)$ is a finite set of allowed next instructions.

• This page only fixes the variant models themselves. The equivalence and simulation theorems relating them to the basic one-tape model come later.

• In the nondeterministic case, more than one next instruction may be available from the same state-symbol pair; acceptance is therefore defined by existence of an accepting branch.