Turing-Machine Configuration Boundary Interface: Examples

Removing $A,R$ from $Q$ leaves exactly $\{s\}$, so the transition domain is $\{(s,a),(s,\bigsqcup )\}$. The two entries give one value to each pair, both in $Q\times \mathrm{\Gamma }\times \{\mathsf{L},\mathsf{R}\}$. All sets are finite, $\bigsqcup \mathrm{\notin }\mathrm{\Sigma }$, and the three designated states are distinct. Thus the data meet every raw-tuple requirement.

The empty word has length zero. For any natural $i$, the condition $i<0$ is false, so its initial-tape formula gives $t_{\epsilon }(i)=\bigsqcup =t_{\mathrm{b}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{k}}(i)$. Its support is $\{i:\bigsqcup \mathrm{\ne }\bigsqcup \}=\mathrm{\varnothing }$, a finite set. Hence it is a tape and $I_M(\epsilon )=(s,0,t_{\mathrm{b}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{k}})$ is a configuration; zero is a head coordinate even though it is not an index of an input letter.

Its state is $s$, unequal to $A$ and $R$. The accepting and rejecting equalities are both false, so their disjunction is false and the configuration is nonhalting. This conclusion concerns the initial triple and does not apply the transition function.

Both machines remove the same set $\{A,R\}$ from $Q$. Their nonhalting domain is therefore exactly $\{(s,a),(s,\bigsqcup )\}$, and the two displayed entries provide a unique correctly typed output at each pair. In $M$ the designated triple is $(s,A,R)$, and in $N$ it is $(s,R,A)$; each has distinct entries. Their finite sets and blank exclusions are the same, so both tuples satisfy all the requirements.

The blank tape has support $\{i\in \mathbb{N}:\bigsqcup \mathrm{\ne }\bigsqcup \}=\mathrm{\varnothing }$. It is consequently a tape for both machines, and $A\in Q$ and $0\in \mathbb{N}$ make $C$ a configuration of both. The shared state, head, and tape components require no change when the designations are interchanged.

For $M$ the accepting equality is $A=q_{\mathrm{a}\mathrm{c}\mathrm{c}}^M=A$, which is true, whereas the rejecting equality is $A=q_{\mathrm{r}\mathrm{e}\mathrm{j}}^M=R$, which is false. Thus $C$ is accepting and not rejecting for $M$.

For $N$ the rejecting equality is $A=q_{\mathrm{r}\mathrm{e}\mathrm{j}}^N=A$, which is true, whereas the accepting equality is $A=q_{\mathrm{a}\mathrm{c}\mathrm{c}}^N=R$, which is false. Thus $C$ is rejecting and not accepting for $N$. It is halting for both machines, but the named outcome depends on the machine's designations, as asserted.