Boone Machine Simulation and Fixed-Presentation Undecidability — Examples

By [F1], $a,b$ are distinct letters of $\bar{S}$. Applying the defining letter substitution to the two positions gives $(ab{)}^{\mathrm{\#}}=a^{\mathrm{\#}}{b}^{\mathrm{\#}}=a^{-1}{b}^{-1}$.

The word $b^{-1}{a}^{-1}$ is the inverse spelling: $(ab)(b^{-1}{a}^{-1})$ cancels first $b{b}^{-1}$ and then $a{a}^{-1}$; the product in the other order cancels first $a^{-1}a$ and then $b^{-1}b$. Thus $(ab{)}^{-1}=b^{-1}{a}^{-1}$.

The two outputs start with different symbols and neither has adjacent inverse pairs, so their reduced spellings differ. For a single tape letter the two operations agree, and both send the empty word to the empty word. The length-two instance displays why sharp cannot be replaced by word inversion; no inequality in an arbitrary quotient group is inferred from spelling alone.

Substitute $q_{0}b=q_0$ with prefix $ha$ and suffix $h$. The result is $ha{q}_{0}h$, whose left tape is the one-letter word $a$ and whose right tape is empty. It is augmented because its state is $q_0$.

Substitute $a{q}_{0}h=q_{0}h$ with prefix $h$. The result is $h{q}_{0}h$, with both tape contexts empty and the same stopping state.

Substitute $h{q}_{0}h=q$ with both contexts empty. This produces the terminal augmented word $q$. Each preceding word had one state and the two outer markers; this last rule removes the markers. The three substitutions remain valid for $a=b=s_0$, giving a concrete all-blank instance. Thus requiring nonempty right tape throughout cleanup would exclude the explicitly reached middle words.

Hard-code the finite string describing ${\mathcal{P}}_{\mathcal{B}}$ in a wrapper machine. On input $z$ over its signed generating alphabet, the wrapper writes this constant string and the pair delimiter, copies $z$, and runs $U$. This explicitly computes $D(z)=U({\mathcal{P}}_{\mathcal{B}},z)$; the preprocessor terminates because the prefix is fixed and $z$ is finite.

Every such pair is a valid input for $U$, so $D$ halts on every $z$ and satisfies $D(z)=\mathrm{y}\mathrm{e}\mathrm{s}$ exactly when $z=1$ in $\mathcal{B}$. For instance $D(\epsilon )=U({\mathcal{P}}_{\mathcal{B}},\epsilon )=\mathrm{y}\mathrm{e}\mathrm{s}$, and $D(x{x}^{-1})=\mathrm{y}\mathrm{e}\mathrm{s}$ by cancellation. The claimed behavior for all words, rather than these two calculations alone, makes $D$ a decider forbidden by [F1]. Thus the proposed uniform algorithm cannot exist.