= Solution
Suppose a zero-register machine decided $L=\{a^nb^n:n>0\}$, and choose $k\ne\ell$ as in part (d). Take $m\geq\max\{k,\ell\}$ and set
$$
x=a^mb^{m-k}.
$$
Then
$$
xb^k=a^mb^m\in L,
$$
whereas
$$
xb^\ell=a^mb^{m-k+\ell}\notin L.
$$
Part (d) puts both computations into the identical configuration $(q,x)$. Determinism forces their subsequent computations and outputs to agree, a contradiction. Therefore
$$
\boxed{L\text{ is not $0$-computable}}.
$$
This is the <one-register separation for equal block lengths>.
Back to article page
