Accepting computations of a nondeterministic machine

Fix a nondeterministic one-tape Turing machine $N=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\mathrm{\Delta })$ and an input word $w\in {\mathrm{\Sigma }}^{\ast }$.

A configuration of $N$ is a triple $(q,h,t)$ with $q\in Q$, head position $h\in \mathbb{N}$, and finite-support tape content $t:\mathbb{N}\to \mathrm{\Gamma }$, just as in Configurations of a deterministic one-tape Turing machine. It is accepting when $q=q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ and rejecting when $q=q_{\mathrm{r}\mathrm{e}\mathrm{j}}$. The initial configuration is $(q_0,0,t_w)$, where $t_w$ is the input word followed by blanks as in Right-infinite tapes as finite-support functions, including the all-blank tape for empty input. These definitions use only the shared state/alphabet data of the deterministic and nondeterministic models.

For configurations $C=(q,h,t)$ and $C^{\mathrm{\prime }}=(q^{\mathrm{\prime }},h^{\mathrm{\prime }},t^{\mathrm{\prime }})$ of $N$, write $C{⊢}_N{C}^{\mathrm{\prime }}$ when $q\mathrm{\notin }\{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$ and there exists an allowed instruction $(p,b,D)\in \mathrm{\Delta }(q,t(h))$ such that $C^{\mathrm{\prime }}$ is obtained from $C$ by the same local rewrite and head-move recipe used in The one-step configuration relation, with $q^{\mathrm{\prime }}=p$.

An accepting computation of $N$ on input $w$ is a finite list of configurations, that is, a function on $\{0,\dots ,n\}$ with configuration values (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=(q_0,0,t_w)$, where $t_w$ is the input tape defined in the same way as for deterministic machines, each $C_i{⊢}_N{C}_{i+1}$ for $0\le i<n$, and $C_n$ is accepting.

We say that $N$ accepts $w$ if such an accepting computation exists.

• Nondeterministic acceptance is existential: one accepting branch is enough.

• Other branches may reject, may halt differently, or may continue forever; no global halting requirement is part of acceptance itself.