String register machine

In a string register machine, ${+}_a(k,q)$ appends $a$ to register $k$; ${?}_a(k,p,q)$ branches according to whether its final letter is $a$; ${?}_{\epsilon }(k,p,q)$ tests emptiness; and $-(k,p,q)$ branches to $p$ when empty, or deletes the final letter and branches to $q$ otherwise.

A machine computes the characteristic function of a language $X$ when it halts on every input with the one-letter output $1$ for inputs in $X$ and $0$ for inputs outside $X$.

Two string registers can recognize $\{a^n{b}^n:n>0\}$ by storing one marker per $a$ and removing one per $b$. A machine with only its input register cannot: two different terminal $b$-block lengths eventually reach the same state and remaining prefix, forcing equal outputs for one member and one nonmember.

To recognize words ending in a fixed symbol $a$, test the final input letter, choose one of two erasing loops, and append $1$ after the accepting loop or $0$ after the rejecting loop. The empty word follows the rejecting branch.

Replace the original halt state by a continuation state that tests whether its one-letter output is $0$ or $1$, removes it, appends the other symbol, and enters a new halt state. This computes the complement language without changing termination behavior.