[proofplan] We simulate a DFA $D$ computing $L$ by a register machine $M$ whose state set contains a local copy of $D$'s state set, indexed so that it does not collide with auxiliary states used for register manipulation. The simulation faces one directional mismatch: register machines destructively read the *last* letter of a register via the standard read operation, whereas a DFA consumes the *first* letter of the input. We reconcile this by pre-reversing the input: first, a dedicated sub-machine copies the content of register $0$ into register $1$ in reverse order, then clears register $0$. After the reversal, reading the last letter of register $1$ is equivalent to reading the first unread letter of the original input, and the DFA's transition function can be simulated directly. When register $1$ becomes empty, the simulation has processed the entire input, and we emit $a$ (accept) or $\varepsilon$ (reject) according to whether the current DFA state lies in $F$. The resulting machine computes $\mathbb{1}_L$, the characteristic function of $L$, showing $L$ is computable. [/proofplan] [step:Fix the DFA, the target computable function, and the register layout] Let $L \subseteq \Sigma^*$ be a [regular language](/pages/???). By the [definition of regularity](/pages/???), there exists a [deterministic finite automaton](/pages/???) (DFA) $D = (\Sigma, Q_D, \delta, q_0, F)$ with $\mathcal{L}(D) = L$, where $\Sigma$ is the (finite) input alphabet, $Q_D$ is the finite state set, $\delta : Q_D \times \Sigma \to Q_D$ is the transition function, $q_0 \in Q_D$ is the initial state, and $F \subseteq Q_D$ is the set of accepting states. For $w = b_1 b_2 \cdots b_n \in \Sigma^*$, we have $w \in L$ iff \begin{align*} \hat{\delta}(q_0, w) \in F, \quad \text{where } \hat{\delta}(q, b_1 \cdots b_n) := \delta(\cdots \delta(\delta(q, b_1), b_2) \cdots, b_n) \end{align*} is the extended transition function (applied left-to-right on the letters). Our goal is to exhibit a register machine $M$ over alphabet $\Sigma$ that computes the characteristic function \begin{align*} \mathbb{1}_L : \Sigma^* &\to \Sigma^*, \\ w &\mapsto \begin{cases} a & w \in L, \\ \varepsilon & w \notin L, \end{cases} \end{align*} where $a \in \Sigma$ is a fixed distinguished letter serving as "accept" marker. Since computability of $L$ means $\mathbb{1}_L$ is a computable total function, constructing such an $M$ proves the theorem. *Register conventions.* The register machine uses three registers: - Register $0$ holds the original input $w$ at the start; at the end it will hold the output $\mathbb{1}_L(w)$. - Register $1$ is auxiliary: it will hold the reverse of $w$ after the reversal phase. - Register $2$ is auxiliary: it holds a single-letter scratch value during the letter-moving loop. The standard register-machine read instruction on a register returns and removes the *last* letter of that register (popping from the right); the write instruction appends a letter to the right; the erase instruction removes all contents. These primitives are fixed by the [register-machine model](/pages/???). [/step] [step:Reverse the input from register $0$ into register $1$] We construct a sub-machine $M_{\text{rev}}$ with a dedicated set of states $Q_{\text{rev}}$, disjoint from the simulation states built in the next step. [claim:There is a register machine $M_{\text{rev}}$ with start state $q_{\text{rev}, S}$ and exit state $q_{\text{rev}, E}$ that, starting from any valuation with register $0 = w$, register $1 = \varepsilon$, register $2 = \varepsilon$, halts at $q_{\text{rev}, E}$ with register $0 = \varepsilon$, register $1 = \text{rev}(w)$, register $2 = \varepsilon$, where $\text{rev}(b_1 \cdots b_n) = b_n \cdots b_1$] We give the program of $M_{\text{rev}}$ explicitly: - State $q_{\text{rev}, S}$: read register $0$. If register $0$ is empty (indicated by the read instruction's $\varepsilon$ branch), transition to $q_{\text{rev}, E}$ and halt the sub-machine. Otherwise, for each $a \in \Sigma$, transition to state $q_{\text{rev}, a}$ carrying the read letter $a$ as the branch label. - State $q_{\text{rev}, a}$ (one such state per letter $a \in \Sigma$): write $a$ to register $1$, then transition back to $q_{\text{rev}, S}$. The register-machine read instruction destructively pops the last letter of register $0$, so on entry to $q_{\text{rev}, a}$ the letter $a$ has already been removed from register $0$. The subsequent write to register $1$ appends $a$ to register $1$. After one pass through the loop, register $0$ is shorter by one letter and register $1$ is longer by one letter, with the letter just removed from the end of register $0$ appended to the end of register $1$. *Loop invariant.* Let $w = b_1 \cdots b_n$ be the initial contents of register $0$. We claim that after $t \le n$ iterations of the loop, register $0$ contains $b_1 \cdots b_{n-t}$ and register $1$ contains $b_n b_{n-1} \cdots b_{n-t+1}$. By induction on $t$. Base $t = 0$: register $0 = w = b_1 \cdots b_n$ and register $1 = \varepsilon$ (empty product). Inductive step: at iteration $t + 1$, the read of register $0$ returns the last letter, which by the induction hypothesis is $b_{n-t}$; the register's new contents are $b_1 \cdots b_{n-t-1}$, and register $1$ receives the new letter $b_{n-t}$ appended to the right of $b_n \cdots b_{n-t+1}$, giving $b_n \cdots b_{n-t+1} b_{n-t}$. This matches the invariant at $t + 1$. At $t = n$, register $0$ is empty and register $1$ contains $b_n b_{n-1} \cdots b_1 = \text{rev}(w)$. The next read of register $0$ returns $\varepsilon$, triggering the transition to $q_{\text{rev}, E}$. Register $2$ was never touched. [/claim] [/step] [step:Build the simulation states $Q_q$ for $q \in Q_D$] For each state $q \in Q_D$, introduce a dedicated simulation state $q^\sharp$ in the register machine, meant to represent "the DFA is currently in state $q$, and the remaining unread input is in register $1$." These states are pairwise distinct and disjoint from $Q_{\text{rev}}$. *Transition from $q^\sharp$ for $q \in Q_D$.* We describe the instruction $P^\sharp(q^\sharp)$: Read register $1$. Two cases based on the read instruction's branch: - If register $1$ is empty ($\varepsilon$ branch), the simulation has consumed all of $w$ and the DFA's current state is $q$. Branch to the *accept* state $q_{\text{acc}}$ if $q \in F$, or to the *reject* state $q_{\text{rej}}$ if $q \notin F$. This branching is not a dynamic decision — $q \in F$ or not is fixed at construction time for each $q$, so each $q^\sharp$ is hard-wired to go to either $q_{\text{acc}}$ or $q_{\text{rej}}$ on the $\varepsilon$ branch. - If register $1$ is non-empty and the read instruction returns letter $b \in \Sigma$, branch to state $\delta(q, b)^\sharp$. Again, $\delta(q, b)$ is fixed at construction time, so the branch target for each $(q, b)$ pair is hard-wired. [claim:With start state $q_0^\sharp$ and simulation states $\{q^\sharp : q \in Q_D\}$, the sub-machine $M_{\text{sim}}$ just described simulates the DFA $D$ on the input stored in register $1$, consuming it letter-by-letter, so long as the input in register $1$ is $\text{rev}(w)$ for some $w \in \Sigma^*$] Let $w = b_1 \cdots b_n \in \Sigma^*$ and suppose at the start of $M_{\text{sim}}$ (state $q_0^\sharp$) register $1$ contains $\text{rev}(w) = b_n b_{n-1} \cdots b_1$. By induction on $t \in \{0, 1, \ldots, n\}$, we show that after $t$ iterations of the simulation loop, the current state is $\hat{\delta}(q_0, b_1 \cdots b_t)^\sharp$ and register $1$ contains $b_n b_{n-1} \cdots b_{t+1}$. Base $t = 0$: start state is $q_0^\sharp = \hat{\delta}(q_0, \varepsilon)^\sharp$, and register $1$ contains $b_n \cdots b_1$, matching. Inductive step. Assume at iteration $t$ the current state is $\hat{\delta}(q_0, b_1 \cdots b_t)^\sharp$ and register $1$ contains $b_n \cdots b_{t+1}$. The instruction at $\hat{\delta}(q_0, b_1 \cdots b_t)^\sharp$ reads register $1$; the last letter of register $1$ is $b_{t+1}$ (the rightmost letter of $b_n \cdots b_{t+1}$), so the read returns $b_{t+1}$ and the register's new contents are $b_n \cdots b_{t+2}$. The branch target for letter $b_{t+1}$ at state $\hat{\delta}(q_0, b_1 \cdots b_t)^\sharp$ is $\delta(\hat{\delta}(q_0, b_1 \cdots b_t), b_{t+1})^\sharp = \hat{\delta}(q_0, b_1 \cdots b_{t+1})^\sharp$ by the recursive definition of $\hat{\delta}$. This matches the invariant at step $t + 1$. At step $t = n$, the state is $\hat{\delta}(q_0, w)^\sharp$ and register $1$ is empty. The next read returns $\varepsilon$, and by the hard-wired branching at $\hat{\delta}(q_0, w)^\sharp$, the sub-machine enters $q_{\text{acc}}$ if $\hat{\delta}(q_0, w) \in F$ (equivalently $w \in L$) or $q_{\text{rej}}$ if $w \notin L$. [/claim] [/step] [step:Emit the output in register $0$ and halt] The sub-machine has two exit states, $q_{\text{acc}}$ and $q_{\text{rej}}$. - At $q_{\text{acc}}$: write $a$ to register $0$, then transition to the halt state $q_H$. - At $q_{\text{rej}}$: transition directly to $q_H$ (register $0$ is already $\varepsilon$ after the reversal phase). Because the reversal phase emptied register $0$, the output register $0$ ends as $a$ iff the sub-machine entered $q_{\text{acc}}$ iff $w \in L$, and as $\varepsilon$ iff $w \notin L$. Register $1$ is empty at exit (it was depleted during the simulation), and register $2$ remained untouched (hence empty throughout). So the final valuation of register $0$ is $\mathbb{1}_L(w)$. [/step] [step:Assemble $M$ and conclude] Define the full register machine \begin{align*} M &:= (\Sigma, Q_{\text{rev}} \cup \{q^\sharp : q \in Q_D\} \cup \{q_{\text{acc}}, q_{\text{rej}}, q_H\}, P^\sharp), \end{align*} with start state $q_{\text{rev}, S}$ (start of the reversal phase), halt state $q_H$, and the program $P^\sharp$ obtained by concatenating the sub-programs described above, identifying $q_{\text{rev}, E}$ with $q_0^\sharp$ (the exit of the reversal phase is the start of the simulation phase). By the disjointness of $Q_{\text{rev}}$ from the simulation states and from $\{q_{\text{acc}}, q_{\text{rej}}, q_H\}$, the program is well-defined on its finite domain. For every input $w \in \Sigma^*$ placed in register $0$, the computation of $M$ proceeds: \begin{align*} &\text{reversal phase: register } 0 = w \to \varepsilon, \quad \text{register } 1 = \varepsilon \to \text{rev}(w); \\ &\text{simulation phase: current state progresses } q_0^\sharp \to q_1^\sharp \to \cdots \to \hat{\delta}(q_0, w)^\sharp, \\ &\qquad \text{register } 1 = \text{rev}(w) \to \varepsilon; \\ &\text{emission phase: register } 0 \text{ receives } a \text{ if } \hat{\delta}(q_0, w) \in F, \text{ else } \varepsilon. \end{align*} All three phases terminate (the reversal loop decrements register $0$ each iteration; the simulation loop decrements register $1$ each iteration; both are bounded by $|w|$). Therefore $M$ halts on every input, and the final content of register $0$ equals $\mathbb{1}_L(w)$. Hence $M$ computes the total function $\mathbb{1}_L$, and $L$ is computable. [/step]