July 07, 2026
Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with \(B\) bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set \(M\) at a cost of only \(\log_2|M|+O(1)\) additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool (a tape supporting only local \(\mathtt{read}\)/\(\mathtt{write}\)/\(\mathtt{move}\) commands) makes the system Turing complete: for every single-tape Turing machine with state set \(Q\) and tape alphabet \(\Gamma\), a controller with \(O(\log|Q|+\log|\Gamma|)\) bits of internal memory simulates it, and we exhibit a concrete exponential separation (\(\mathrm{EQ}_n\) requires \(2^n\) states without tools but a single constant-size controller with the tape tool). Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states, \(\{0,1\}\) transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation (\(O(\log B)\) recurrent bits suffice to simulate any \(B\)-state Turing machine), and prove a matching impossibility result: without external memory, directly realizing an arbitrary \(B\)-state transition map in one exact affine recurrent update requires dimension exactly \(B-1\), for any number of layers. Together, these results give a precise resource-accounting picture of tool-augmented recurrent computation.
expressivity; state-space models; tool use; oracle machines; Turing completeness; finite precision; recurrent models; computational complexity
Sequence models are no longer used only as sequence-to-sequence maps: they are deployed as agents that interleave output generation with calls to external tools such as calculators, code interpreters, retrieval systems, and scratchpads [1]–[3]. This raises a basic theoretical question:
Which tools increase the computational expressivity of a fixed finite-precision sequence model, by how much, and at what internal memory cost?
The starting point is that any fixed finite-precision recurrent model is, from the standpoint of expressivity, a finite-state machine: a model with \(B\) bits of internal state has at most \(2^B\) configurations, and hence, without external interaction, recognizes only regular languages [4]–[6]. This covers, in particular, finite-precision structured state-space models (SSMs) [7], [8], whose formal-language limitations have been analyzed in detail [6], [9]–[11]. Chain-of-thought decoding changes this picture only partially: it can add power, but in a way that is tightly constrained by the number of generated steps [11], [12]. Tool use is a different augmentation mechanism, and, as we show, its effect on expressivity is governed entirely by the interface and state space of the tool, not by the controller.
We abstract the sequence model as a deterministic finite-state controller that first reads its input and then, in a generation phase, repeatedly emits output tokens, issues tool commands from a finite command alphabet, receives observations from a finite observation alphabet, or halts (Section 3). Any fixed finite-precision recurrent model with \(B\) bits of state induces such a controller with at most \(2^B\) states, so all our lower bounds apply to such models, and all our upper bounds are constructive.
Our results form a sharp dichotomy, summarized in Table 1.
Finite-state tools add (almost) nothing. We formalize finite-state bounded-interface oracles and prove a product-state simulation theorem (Section 4): any such tool can be internalized by the controller at a cost of \(\log_2|M|+O(1)\) additional bits, where \(M\) is the oracle memory. The finite-state interface hypothesis is essential. We show that dropping it makes even a one-bit oracle arbitrarily powerful.
One minimal unbounded tool yields Turing completeness. We define a tape oracle supporting only local \(\mathtt{read}\)/\(\mathtt{write}\)/\(\mathtt{move}\) commands (Section 5) and prove that a controller with \(O(\log|Q|+\log|\Gamma|)\) bits of internal memory (constant in the input length) simulates any single-tape Turing machine (Section 6). We complement the asymptotic separation with a concrete finite one: solving \(\mathrm{EQ}_n\) requires \(2^n\) controller states without tools, while a single constant-size controller with tape access solves it for all \(n\) (Section 7).
Exact realization by a one-layer selective SSM. We prove that every observation-driven finite-state controller is realized exactly by a one-layer finite-precision selective affine SSM with one-hot binary hidden states, \(\{0,1\}\) transition matrices, and zero biases (Section 8). Instantiating this with the tape simulation makes finite-precision selective SSM controllers Turing complete with hidden dimension \(O(|Q|\,|\Gamma|)\). The one-hot encoding makes this dimension linear in \(|Q|\); Theorem 4 in the supplementary material shows that this linear dependence is not necessary and improves it to logarithmic (see Contribution 4).
Exact resource accounting (supplementary). In the supplementary material we give a fully explicit three-symbol realization with constant \(C_0=9\) (Appendix 10), and a logarithmic oracle-assisted universal simulation (Theorem 4 in Appendix 11): \(O(\log B)\) recurrent bits suffice to simulate any \(B\)-state Turing machine, by hard-coding the machine’s description in the fixed readout and copying it onto the tape. Since \(B=|Q|\) and the tape alphabet is fixed there, this can be viewed as a strict improvement of Contribution 3: it reduces the required recurrent dimension of the SSM controller from \(O(|Q|)\) one-hot coordinates to \(O(\log|Q|)\) recurrent bits, under resource conventions made explicit in the appendix (the tape is free external memory, and fixed parameters and the readout table are not charged to the recurrent-memory budget). We complement this with a matching impossibility theorem: without external memory, exactly realizing an arbitrary transition map \(f:[B]\times\{0,1\}\to[B]\) in one affine recurrent update requires total recurrent dimension exactly \(B-1\), for any number of triangular selective-affine layers. This resolves the direct-realization question negatively and pinpoints precisely which modeling conventions the logarithmic result depends on.
| Tool | Controller memory | Power | Where |
|---|---|---|---|
| none | \(b\) bits | regular languages | Sec. [sec:sec:interactive-tape] |
| finite-state oracle | \(+\log_2|M|+O(1)\) bits | still regular | Sec. [sec:sec:finite-state-tools] |
| tape oracle | \(O(\log|Q|+\log|\Gamma|)\) bits | Turing complete | Sec. [sec:sec:interactive-tape] |
| tape oracle (1-layer sel.SSM) | \(d=O(|Q|\,|\Gamma|)\), binary | Turing complete | Sec. [sec:sec:ssm-controller] |
| none, \(\mathrm{EQ}_n\) | \(\geq 2^n\) states | — | Sec. [sec:sec:eq-lower-bound] |
| tape oracle, universal | \(O(\log B)\) bits | simulates \(\mathcal T_B\) | App. [sec:app:log-simulation] |
| no external memory, direct | exactly \(B-1\) dims | one-step \(f\) | App. [sec:app:log-simulation] |
All results are exact constructions or unconditional lower bounds. No training, approximation, or probabilistic arguments are involved. All alphabets and interfaces are finite, and precision is fixed throughout.
With unbounded precision and time, recurrent networks are Turing complete [13], but under realistic finite precision they collapse to finite-state machines [4], [5]. For SSMs [7], [8], circuit-complexity upper bounds place fixed-depth models in \(\mathsf{TC}^0\) and expose state-tracking limitations [9], with refined formal-language characterizations by [10] and expressivity gains from richer recurrences [14]. [6] prove that finite-precision SSMs recognize only regular languages and establish function-composition lower bounds for one-layer SSMs, supported empirically on compositional benchmarks. Related compositional limitations of Transformers appear in [15] and [16]. [11] analyze multi-layer SSMs, showing an inherent gap to streaming models, that offline chain-of-thought does not fundamentally increase expressiveness while online chain-of-thought does, and that width and precision are non-interchangeable in the base model. Our work is complementary: we fix the controller to be finite-state (subsuming any fixed finite-precision model, including those studied in the works above) and vary the tool interface, obtaining an exact dichotomy between finite-state and tape-like tools.
Turing-completeness results for Transformers typically require unbounded precision or growing intermediate computation [17], and chain-of-thought provably extends expressive power as a function of the number of generated steps [12], [18]. The neural Chomsky-hierarchy study of [19] demonstrates empirically that external memory structure (stack, tape) determines which language classes are learnable. Our tape-oracle theorem gives the corresponding exact, constructive statement at the level of finite-state controllers, with explicit internal-memory bounds, and our appendix results quantify precisely how much recurrent memory is saved by offloading the program to the tape (from \(\Theta(B)\) to \(O(\log B)\), using small universal machines [20]).
Practical systems interleave generation with tool calls [1], [2] or scratchpad writes [3]. These works are empirical; we provide a minimal formal semantics for the command/observation loop (tags such as \(\mathtt{[TOOL]}\)/\(\mathtt{[OBS]}\) being a finite-state encoding convention) and characterize exactly when the loop increases expressivity.
We work with finite alphabets throughout. Multi-token tags such as \(\mathtt{[TOOL]}, \mathtt{[\backslash TOOL]}, \mathtt{[OBS]}, \mathtt{[\backslash OBS]}\) are only a finite-state encoding convention. For expressivity questions, they can be replaced by a finite command alphabet and a finite observation alphabet without changing the asymptotic conclusions. If desired, the literal tagged transcript can be recovered by expanding the finite control by a constant factor to print the corresponding fixed encodings.
Let \(A\) be an input alphabet and let \(\dashv\notin A\) be a right endmarker.
Definition 1 (Finite-state controller). A deterministic finite-state controller is a finite-state transducer \(C=(S,s_0,\delta_{in},\alpha,\delta_{out},\delta_{obs}),\) where:
\(S\) is a finite state set;
\(s_0\in S\) is the initial state;
\(\delta_{in}:S\times (A\cup\{\dashv\})\to S\) updates the controller while reading the input;
after the input phase, \(\alpha\) determines the next action of the controller. The possible actions are: \[\mathrm{halt},\qquad \mathrm{out}(a)\;\text{for an output token }a,\qquad \mathrm{cmd}(d)\;\text{for a tool command }d;\]
\(\delta_{out}\) updates the controller after an output token is emitted;
\(\delta_{obs}\) updates the controller after a tool observation is received.
The controller first reads \(x\dashv\) from left to right. It then enters the generation phase. In the generation phase it repeatedly outputs tokens, issues tool commands, or halts.
Let \(D=\{\mathtt{parity}\}\) be a one-command tool interface and let \(R=\{\mathtt{even},\mathtt{odd}\}\) be its observation alphabet. A controller may have a post-input state \(s_{ask}\) with \(\alpha(s_{ask})=\mathrm{cmd}(\mathtt{parity}).\) Thus the abstract action is the tool command \(\mathrm{cmd}(d)\), with \(d=\mathtt{parity}\). If one wants to display the same interaction as a literal tagged transcript, this single abstract command can be expanded into the fixed finite string \(\mathtt{[TOOL]}\;\mathtt{parity}\;\mathtt{[\backslash TOOL]}.\) After the environment executes the command, it returns an observation \(r\in R\). For example, if \(r=\mathtt{odd}\), the literal transcript could display the observation as \(\mathtt{[OBS]}\;\mathtt{odd}\;\mathtt{[\backslash OBS]}.\) The controller then updates by \(s'=\delta_{obs}(s_{ask},\mathtt{odd}).\) For instance, \(s'\) could be a state with \(\alpha(s')=\mathrm{out}(\mathtt{F})\), after which \(\delta_{out}\) moves the controller to a halting state. The tags \(\mathtt{[TOOL]}\), \(\mathtt{[\backslash TOOL]}\), \(\mathtt{[OBS]}\), and \(\mathtt{[\backslash OBS]}\) are not additional sources of computational power; they are only a fixed finite encoding of the abstract command and observation alphabets.
This is an explicit finite-state version of the bounded-memory sequence controller. Any fixed finite-precision recurrent model, including a finite-precision state-space model with \(B\) bits of internal state, induces such a controller with at most \(2^B\) possible internal states.
The finite-state tools are merely additional bounded-memory devices; this is correct only if the tool interface itself is finite-state. Merely requiring the oracle memory set \(\mathcal{M}\) to be finite is not enough: an arbitrary initialization map or an arbitrary command-to-observation map could encode nonregular or even undecidable behavior. We therefore use the following definition.
Definition 2 (Finite-state bounded-interface oracle). A finite-state bounded-interface oracle is a tuple \(\mathcal{O}=(M,m_0,\eta,D,R,\mathrm{Step}),\) where:
\(M\) is a finite oracle-memory set;
\(m_0\in M\) is the initial oracle state before reading the input;
\(\eta:M\times A\to M\) is a finite-state initialization transition;
\(D\) is a finite command set;
\(R\) is a finite observation set;
\(\mathrm{Step}:M\times D\to M\times R\) is a deterministic transition-and-observation map.
Operationally, when the current oracle memory is \(m\) and the controller issues a command \(d\in D\), the value \(\mathrm{Step}(m,d)=(m',r)\) means that the oracle memory becomes \(m'\) and the observation returned to the controller is \(r\in R\).
Given input \(x=x_1\cdots x_n\in A^\ast\), the initial oracle memory is \(\mathrm{Init}(x)=\eta^\ast(m_0,x),\) where \(\eta^\ast\) is the usual extension of \(\eta\) to words.
Take \(A=\{0,1\}\) and let the oracle memory be \(M=\{0,1\}\), with \(m_0=0\) and initialization transition \(\eta(m,a)=m\oplus a\). After reading the input, the oracle state records the parity of the input. Let the command set be \(D=\{\mathtt{query},\mathtt{flip}\}\) and the observation set be \(R=\{0,1,\mathtt{ok}\}\). Define \[\mathrm{Step}(m,\mathtt{query})=(m,m), \qquad \mathrm{Step}(m,\mathtt{flip})=(1-m,\mathtt{ok}).\] This is a finite-state bounded-interface oracle: both its memory and its command/observation interface are finite. The product-state simulation below simply stores the pair consisting of the controller state and this one-bit oracle state.
Let \(C\) be a deterministic finite-state controller interacting with a finite-state bounded-interface oracle \(\mathcal{O}\). Then there is a deterministic finite-state controller \(\widetilde{C}\), without tool access, that produces exactly the same scored output stream on every input. Moreover, \(\widetilde{C}\) may be chosen with state space contained in \(S\times M\) up to a constant-factor enlargement for fixed command and observation encodings. Thus finite-state bounded-interface tools increase memory by at most \(( \log_2 |M|+O(1) )\) bits.
Proof. Let \(C=(S,s_0,\delta_{in},\alpha,\delta_{out},\delta_{obs})\) and let \(\mathcal{O}=(M,m_0,\eta,D,R,\mathrm{Step}).\) Construct a no-tool controller \(\widetilde{C}\) whose state records a pair \((s,m)\in S\times M.\)
During the input phase, when the next input symbol is \(a\in A\), define \((s,m)\mapsto \bigl(\delta_{in}(s,a),\eta(m,a)\bigr).\) On the endmarker \(\dashv\), update the controller component by \(\delta_{in}\) and leave the oracle component fixed.
During the generation phase, suppose \(\widetilde{C}\) is in state \((s,m)\). If \(\alpha(s)=\mathrm{halt}\), then \(\widetilde{C}\) halts. If \(\alpha(s)=\mathrm{out}(a)\), then \(\widetilde{C}\) emits the same output token \(a\) and moves to \((\delta_{out}(s,a),m).\) If \(\alpha(s)=\mathrm{cmd}(d)\), compute \((m',r)=\mathrm{Step}(m,d).\) The original interaction would update the oracle memory from \(m\) to \(m'\), return the observation \(r\), and update the controller state to \(\delta_{obs}(s,r)\). Therefore \(\widetilde{C}\) moves to \((\delta_{obs}(s,r),m').\) No tool call is made externally, its effect has been simulated internally.
By induction on the number of generation steps, the simulated pair \((s,m)\) is exactly the controller state and oracle state that would occur in the true interaction. Hence every output token emitted by \(\widetilde{C}\) is exactly the corresponding output token emitted by \(C\), and conversely. Thus the scored output streams agree on every input. If one insists on reproducing the literal tagged transcript rather than only the scored output stream, one adds a finite emission buffer for the fixed encodings of \(d\in D\) and \(r\in R\). Since \(D\) and \(R\) are finite, this changes the state space only by a constant factor. ◻
The finite-state initialization hypothesis is essential. If \(\mathrm{Init}:A^\ast\to M\) is allowed to be arbitrary, then even a one-bit oracle state can encode membership in an arbitrary language. Similarly, if \(\mathrm{Step}:M\times \Sigma^\ast\to M\times \Sigma^\ast\) is arbitrary as a function of the whole command string, then the oracle can perform unbounded computation despite having finite memory. The product-state simulation theorem is therefore valid only for genuinely finite-state tool interfaces.
We now define a simple infinite-state tool. It performs only local tape operations, but its memory is unbounded. Let \(\Gamma\) be a finite tape alphabet containing a blank symbol \(\sqcup\), a left-end marker \(\vdash\), and an output endmarker \(\mathtt{[EOS]}\). Let \(A\subseteq \Gamma\setminus\{\sqcup,\vdash,\mathtt{[EOS]}\}\) be the input alphabet.
A tape configuration is a pair \((T,h)\), where \(T:\mathbb{N}\to \Gamma\) has finite support away from blanks, satisfies \(T(0)=\vdash\), and \(h\in\mathbb{N}\) is the head position.
Definition 3 (Tape oracle). The tape oracle \(\mathcal{O}_{tape}\) has memory space consisting of all tape configurations \((T,h)\). On input \(x=x_1\cdots x_n\in A^\ast\), it initializes \[T(0)=\vdash,\qquad T(i)=x_i\;\text{for }1\le i\le n,\qquad T(i)=\sqcup\;\text{for }i>n,\] and sets \(h=1\).
It supports the finite command set \[D=\{\mathtt{read},\mathtt{move\_left},\mathtt{move\_right}\} \cup \{\mathtt{write}(\gamma):\gamma\in\Gamma\}.\] The observations are symbols of \(\Gamma\), returned by \(\mathtt{read}\), together with a dummy acknowledgement symbol \(\mathtt{ok}\) for write and move commands.
The transition rules are:
\(\mathtt{read}\) returns \(T(h)\) and does not change the tape;
\(\mathtt{write}(\gamma)\) writes \(\gamma\) at the current head position, except that the left-end marker at cell \(0\) is preserved;
\(\mathtt{move\_right}\) replaces \(h\) by \(h+1\);
\(\mathtt{move\_left}\) replaces \(h\) by \(\max\{h-1,0\}\).
On input \(x=01\), the initial tape begins \(\vdash\;0\;1\;\sqcup\;\sqcup\;\cdots,\) and the head is on the first input symbol. The command \(\mathtt{read}\) returns \(0\). After \(\mathtt{move\_right}\), the head is on the symbol \(1\); issuing \(\mathtt{write}(0)\) changes the tape prefix to \(\vdash\,0\,0\). Moving right again and writing \(1\) uses the next previously blank cell. Although every command is local and the command alphabet is finite, an arbitrarily long computation can visit and modify arbitrarily many tape cells, which is why the oracle has an infinite state space.
We use the following standard output convention. A deterministic single-tape Turing machine is in output-normal form if, whenever it halts, its tape contains "\(\vdash\, y\, \mathtt{[EOS]}\)" starting at cell \(0\), the head is positioned at the first symbol of \(y\mathtt{[EOS]}\), and \(y\in A^\ast\) is the output. Every partial computable string function has a deterministic single-tape machine in this normal form: after computing its intended output, the machine can rewrite the tape into the required form and move its head to the first output cell.
Theorem 1 (Interactive tape tool-use is Turing complete). Let \(T\) be a deterministic single-tape Turing machine in output-normal form, with finite state set \(Q\) and tape alphabet \(\Gamma\). There exists a deterministic finite-state controller \(C_T\) such that, with interactive access to \(\mathcal{O}_{tape}\), the controller computes the same partial function as \(T\). More precisely, for every input \(x\in A^\ast\), the controller halts and outputs \(T(x)\mathtt{[EOS]}\) if and only if \(T\) halts on \(x\). The number of controller states is \(O(|Q||\Gamma|)\), equivalently \(O(\log |Q|+\log |\Gamma|)\) bits of internal memory. If \(\Gamma\) is fixed, this is \(O(\log |Q|)\) bits and is constant with respect to the input length.
Proof. Let the transition function of \(T\) be \(\delta_T:Q_{nh}\times \Gamma \to Q\times \Gamma\times \{L,R,S\},\) where \(Q_{nh}\subseteq Q\) is the set of nonhalting states. The controller \(C_T\) stores:
the current simulated machine state \(q\in Q\);
a mode flag indicating whether it is about to read, write, move, or print;
when needed, one tape symbol \(\gamma\in\Gamma\) obtained from the most recent read.
This is a finite amount of information, with \(O(|Q||\Gamma|)\) possible states. The simulation loop is as follows. Suppose the controller stores the simulated state \(q\in Q_{nh}\). First, it issues the command \(\mathtt{read}\). If the observation is \(\gamma\in\Gamma\), it computes in finite control \(\delta_T(q,\gamma)=(q',\gamma',d),\) where \(d\in\{L,R,S\}\). It then issues the command \(\mathtt{write}(\gamma')\). If \(d=L\), it issues \(\mathtt{move\_left}\); if \(d=R\), it issues \(\mathtt{move\_right}\); if \(d=S\), it issues no move command. It then updates its stored simulated state to \(q'\).
The invariant is that after each completed simulated transition, the oracle tape configuration is exactly the tape configuration of \(T\), and the controller stores exactly the current finite control state of \(T\). The invariant holds at initialization by the definition of \(\mathcal{O}_{tape}\). The preceding paragraph preserves it because the controller performs exactly the read, write, and head-move operations specified by \(\delta_T\).
If \(q'\) is nonhalting, the controller repeats the loop. If \(q'\) is halting, the output-normal-form convention guarantees that the oracle head is positioned at the first output symbol and that the tape contains a contiguous word \(y\mathtt{[EOS]}\). The controller enters print mode. In print mode it repeatedly issues \(\mathtt{read}\). If the observed symbol is \(\mathtt{[EOS]}\), it emits \(\mathtt{[EOS]}\) as an output token and halts. Otherwise it emits the observed symbol as an output token and then issues \(\mathtt{move\_right}\).
Thus the emitted output stream is exactly \(y\mathtt{[EOS]}\), where \(y=T(x)\). If \(T\) never halts, the simulation loop never reaches print mode, so the controller also never halts. Therefore the controller computes the same partial function as \(T\). ◻
Corollary 1 (Strict expressivity increase). There are decision and search problems solvable by a finite-state controller with interactive access to \(\mathcal{O}_{tape}\) that are not solvable by any finite-state controller without tool access.
Proof. By the theorem, interactive access to \(\mathcal{O}_{tape}\) allows a finite-state controller to simulate any Turing machine, and hence to compute any partial computable string function.
Without tools, a controller with a fixed finite state set recognizes only regular languages under the usual decision convention: after reading \(x\dashv\), its final behavior is determined by one of finitely many states. Therefore the accepted language is a regular language.
The language \(L_{eq}=\{u\#u:u\in \{0,1\}^\ast\}\) is not regular. Hence, it is not decidable by any no-tool finite-state controller, but it is decidable by a finite-state controller with interactive tape access, since it is Turing-decidable. ◻
We now give a finite-length version of the same separation.
Theorem 2 (Equality requires exponentially many internal states). For each \(n\in\mathbb{N}\), define the promise problem \(\mathrm{EQ}_n\) on inputs \[u\#v,\qquad u,v\in \{0,1\}^n,\] by requiring output \(\mathtt T\) if \(u=v\) and output \(\mathtt F\) otherwise.
Any deterministic no-tool finite-state controller that solves \(\mathrm{EQ}_n\) on all promised inputs has at least \(2^n\) internal states.
There is a single deterministic finite-state controller which, with interactive access to \(\mathcal{O}_{tape}\), solves \(\mathrm{EQ}_n\) for every \(n\).
Proof. Proof of (i). Let \(C\) be a deterministic no-tool finite-state controller solving \(\mathrm{EQ}_n\), and let \(S\) be its state set. After reading the first block \(u\in\{0,1\}^n\), the controller is in some state \(\phi(u)\in S.\) Thus \(\phi:\{0,1\}^n\to S\). If \(|S|<2^n\), then there exist distinct \(u,u'\in\{0,1\}^n\) such that \(\phi(u)=\phi(u').\) Now feed both computations the same continuation \(\#u\dashv\). Since the controller is deterministic and starts this continuation in the same state in both cases, its subsequent behavior is identical on \(u\#u \text{ and } u'\#u.\) Therefore it must output the same answer on both inputs. But \(u\#u\) is a positive instance, while \(u'\#u\) is a negative instance because \(u'\ne u\). This contradicts correctness. Hence \(|S|\ge 2^n.\)
Proof of (ii). The language \(L_{eq}=\{u\#u:u\in\{0,1\}^\ast\}\) is decidable by a deterministic Turing machine. For example, a single-tape machine can repeatedly mark the leftmost unmarked bit before the delimiter, remember whether it was \(0\) or \(1\), scan to the corresponding leftmost unmarked bit after the delimiter, compare and mark it, and then return to the beginning. When no unmarked bit remains before the delimiter, it checks that no unmarked bit remains after the delimiter. It accepts exactly when all comparisons succeed.
This algorithm uses only finitely many tape symbols and finitely many control states. By the Turing-completeness theorem above, there is a finite-state controller with interactive access to \(\mathcal{O}_{tape}\) that simulates this machine. The same controller works for all \(n\), because it decides the full language \(L_{eq}\), and therefore solves each promised problem \(\mathrm{EQ}_n\). ◻
We now show that the preceding Turing-completeness statement can be realized by a natural finite-precision SSM-type controller. The precise statement is architecture-dependent. We prove the positive result for selective affine state-space controllers, i.e. controllers whose transition matrix may depend on the current observation token. This selectivity is essential to the proof: a fixed linear time-invariant recurrence with one common transition matrix is not claimed to realize arbitrary finite control. The proof has two steps. First, we show that every deterministic finite-state controller is exactly realizable by a one-hot selective affine SSM. Second, we instantiate this construction with the finite controller that simulates a Turing machine using the read/write/move tape oracle.
Let \(\Omega\) be a finite observation alphabet. Let \(\mathbb{F}_p\subset \mathbb{R}\) denote a fixed finite set of real numbers representable with \(p\) bits, and assume \(0,1\in \mathbb{F}_p\). A generalized \(L\)-layer finite-precision SSM controller has hidden states: \[h_{\ell,t}\in \mathbb{F}_p^d, \qquad 1\leq \ell\leq L,\;t\geq 0,\] and layer outputs \(y_{\ell,t}\in \mathbb{F}_p^m.\) Given an observation token \(\omega_t\in\Omega\), set \(y_{0,t}=\operatorname{emb}(\omega_t,t),\) where \(\operatorname{emb}\) is any fixed finite-precision embedding. The layers evolve according to \[h_{\ell,t} = A_{\ell,t} h_{\ell,t-1} + B_{\ell,t} y_{\ell-1,t}, \qquad y_{\ell,t} = \operatorname{out}_{\ell,t} \bigl(h_{\ell,t},y_{\ell-1,t}\bigr), \] where \(A_{\ell,t}\) and \(B_{\ell,t}\) have finite-precision entries. As in selective SSMs, the matrices and readout maps may depend on the layer \(\ell\), the time \(t\), and the current lower-layer input \(y_{\ell-1,t}\), equivalently on the current observation token \(\omega_t\) after embedding. The construction below uses only the one-layer special case \(L=1\), with \(B_{1,t}=0\), binary hidden states, and transition matrices selected by the current observation.
We reuse the tape oracle of Section 5. For this section only, we write its commands as \[\mathcal{C} = \{\mathtt{read},\mathtt{left},\mathtt{right},\mathtt{stay}\} \cup \{\mathtt{write}_{\tau}:\tau\in\Gamma\},\] where \(\mathtt{stay}\) leaves the head in place. We write \(\Omega=\Gamma\cup\{\bot\}\) for the observation alphabet: a read returns the scanned tape symbol, while every write or move command returns the dummy observation \(\bot\). If \(\Delta\subseteq\Gamma\setminus\{\sqcup,\vdash,\mathtt{[EOS]}\}\) is the visible output alphabet, then \[\mathsf{Act} = \mathcal{C}\cup\Delta\cup\{\mathtt{[EOS]},\mathtt{halt}\}.\] The actions in \(\mathcal{C}\) are tool commands. The actions in \(\Delta\cup\{\mathtt{[EOS]}\}\) are visible output tokens, not tool commands. When such a visible token is emitted, no tape operation is performed; the environment appends the token to the visible output stream and returns the dummy observation \(\bot\) only to advance the recurrent update.
The action alphabet \(\mathsf{Act}\) does not include chain-of-thought tokens, private scratchpad tokens, or other hidden reasoning tokens. Any private computation of the controller is represented by its finite control or recurrent state, not by emitted actions. The visible output stream retains only the symbols in \(\Delta\cup\{\mathtt{[EOS]}\}\).
After the input has initialized the tape, the finite control used in the simulation is the following Moore-machine specialization of the controller from Section 3.
Definition 4 (Observation-driven finite-state controller). An observation-driven deterministic finite-state controller is a tuple \(\mathcal{K}=(S,s_0,\delta,\lambda),\) where \(S\) is finite, \(s_0\in S\), \(\delta:S\times\Omega\to S\), and \(\lambda:S\to\mathsf{Act}\). In state \(s_t\), the controller emits \(a_t=\lambda(s_t)\). If \(a_t=\mathtt{halt}\), the computation terminates. If \(a_t\in\mathcal{C}\), the environment executes the corresponding tape command and returns the resulting observation \(\omega_t\in\Omega\). If \(a_t\in\Delta\cup\{\mathtt{[EOS]}\}\), the environment appends this visible token to the output stream and returns the dummy observation \(\omega_t=\bot\). In either nonhalting case, the controller moves to \(s_{t+1}=\delta(s_t,\omega_t).\)
Definition 5 (Selective affine SSM controller). A finite-precision selective affine SSM controller over \(\Omega\) is a tuple \(\mathcal{M} = \bigl(d,h^{(0)},\{A_\omega,b_\omega\}_{\omega\in\Omega},\rho\bigr),\) where \(d\in\mathbb{N}\), \(h^{(0)}\in \mathbb{F}_p^d,\) each \(A_\omega\in \mathbb{F}_p^{d\times d}, b_\omega\in \mathbb{F}_p^d,\) and \(\rho:\mathbb{F}_p^d\to \mathsf{Act}\) is an action readout. At time \(t\), the controller emits \(a_t=\rho(h^{(t)}).\) If \(a_t=\mathtt{halt}\), the computation terminates. Otherwise the environment handles \(a_t\) according to the convention above: a tool command is executed by the tape oracle, while a visible output token is appended to the visible stream and produces the dummy observation \(\bot\). The returned observation \(\omega_t\in\Omega\) determines the hidden-state update \(h^{(t+1)} = A_{\omega_t}h^{(t)} + b_{\omega_t}.\) This is the one-layer selective specialization of \((\mathrm{SSM})\), with \(B_{1,t}=0\), \(A_{1,t}=A_{\omega_t}\), and the output map given by the finite action readout \(\rho\).
The controller is time-homogeneous in this specialization: the maps \(\{A_\omega,b_\omega\}_{\omega\in\Omega}\) and \(\rho\) are fixed for the entire computation. They may depend on the current observation and recurrent state, but not explicitly on the absolute time index.
Lemma 1 (Exact one-hot realization). Let \(\mathcal{K}=(S,s_0,\delta,\lambda)\) be an observation-driven deterministic finite-state controller. Then there exists a finite-precision selective affine SSM controller that realizes exactly the same state evolution and emits exactly the same action at every time step. One may choose hidden dimension \(d=|S|,\) binary hidden states, transition matrices with entries in \(\{0,1\}\), and all biases equal to zero.
Here “all biases equal to zero” means that \[b_\omega=0\in\mathbb{F}_p^d \qquad\text{for every }\omega\in\Omega.\] Thus, on each observation, the update is purely linear: \(h^{(t+1)}=A_{\omega_t}h^{(t)}\).
Proof. Enumerate the finite state set as \(S=\{s_1,\dots,s_m\}, m=|S|.\) Encode \(s_i\) by the \(i\)-th standard basis vector \(e_i\in \{0,1\}^m.\) Let \(s_{i_0}=s_0\), and set \(h^{(0)}=e_{i_0}.\)
For each observation \(\omega\in\Omega\), define a matrix \(A_\omega\in\{0,1\}^{m\times m}\) by specifying its columns: \[A_\omega e_i=e_j \qquad \text{whenever } \delta(s_i,\omega)=s_j.\] Equivalently, the \(i\)-th column of \(A_\omega\) is the one-hot encoding of the state \(\delta(s_i,\omega)\). Set \[b_\omega=0 \qquad \text{for every }\omega\in\Omega.\]
Define the SSM readout on reachable one-hot states by \(\rho(e_i)=\lambda(s_i).\) On non-one-hot vectors, define \(\rho\) arbitrarily; those vectors are never reached in the construction.
We prove by induction on \(t\) that, whenever the finite-state controller is in state \(s_i\) at time \(t\), the SSM hidden state is \(h^{(t)}=e_i\). The assertion holds at \(t=0\) by construction. Suppose it holds at time \(t\). Both systems emit the same action because \(\rho(h^{(t)}) = \rho(e_i) = \lambda(s_i).\) If this action is \(\mathtt{halt}\), both halt. Otherwise the environment returns the same observation \(\omega_t\) to both systems. If \(\delta(s_i,\omega_t)=s_j,\) then the SSM update gives \(h^{(t+1)} = A_{\omega_t}h^{(t)} = A_{\omega_t}e_i = e_j,\) which is exactly the one-hot encoding of the next finite state. Hence the induction closes. Therefore the SSM emits exactly the same action sequence as \(\mathcal{K}\), and hence has the same visible output stream. ◻
Theorem 3 (Turing completeness of selective finite-precision SSM controllers). Let \(T\) be a deterministic single-tape Turing machine with finite state set \(Q\) and tape alphabet \(\Gamma\). Assume \(T\) is in output-normal form: whenever it halts on input \(x\), its tape contains \(\vdash\, T(x)\,\mathtt{[EOS]}\) starting at the leftmost cell, and the head is positioned at the first symbol of \(T(x)\mathtt{[EOS]}\). Then there exists a one-layer finite-precision selective affine SSM controller \(\mathcal{M}_T\) such that, with interactive access to the tape oracle, \(\mathcal{M}_T\) halts and emits \(T(x)\mathtt{[EOS]}\) if and only if \(T\) halts on \(x\). If \(T\) does not halt on \(x\), then \(\mathcal{M}_T\) does not halt. Moreover, the hidden dimension may be chosen to be \(d=O(|Q|\,|\Gamma|).\) All transition matrices may be chosen with entries in \(\{0,1\}\), and all bias vectors may be chosen to be zero.
Proof. First construct an observation-driven finite-state controller \(\mathcal{K}_T=(S_T,s_0,\delta_T^{\mathcal{K}},\lambda_T)\) that simulates \(T\) using the tape oracle.
The controller stores in finite control:
the current simulated Turing-machine state \(q\in Q\);
a mode flag indicating whether it is about to read, write, move, or print;
when needed, one tape symbol \(\sigma\in\Gamma\) obtained from the most recent read.
Suppose the simulated machine is in a nonhalting state \(q\). The controller first emits the command \(\mathtt{read}\). If the returned observation is \(\sigma\in\Gamma\), it computes the Turing transition \[\delta_T(q,\sigma)=(q',\sigma',d), \qquad d\in\{L,R,S\},\] in finite control. It then emits \(\mathtt{write}_{\sigma'}\). After receiving the dummy observation \(\bot\), it emits \(\mathtt{left}\), \(\mathtt{right}\), or \(\mathtt{stay}\), according as \(d=L\), \(d=R\), or \(d=S\). After the next dummy observation, it updates the stored simulated state to \(q'\) and repeats.
The standard simulation invariant is the following: after each completed simulated transition, the oracle tape configuration is exactly the tape configuration of \(T\), and the finite controller stores exactly the current finite control state of \(T\). The invariant holds at initialization by the definition of the tape oracle, and it is preserved because each simulated Turing step is implemented by exactly one read, one write, and one head-move command.
When the simulated machine reaches its halting state, the output-normal-form convention implies that the oracle head is positioned at the first symbol of \(T(x)\mathtt{[EOS]}\). The controller then enters print mode. In print mode it repeatedly emits \(\mathtt{read}\). If the returned symbol is \(\mathtt{[EOS]}\), it emits the visible token \(\mathtt{[EOS]}\) and then enters a state whose action is \(\mathtt{halt}\). If the returned symbol is \(\tau\in\Delta\), it emits the visible token \(\tau\), receives the dummy observation \(\bot\), emits \(\mathtt{right}\), receives \(\bot\), and repeats.
Thus \(\mathcal{K}_T\) emits precisely the visible stream \(T(x)\mathtt{[EOS]}\) when \(T\) halts, and it does not halt when \(T\) does not halt. The number of states in \(\mathcal{K}_T\) is \(O(|Q|\,|\Gamma|)\): the controller needs only the simulated state, a constant-size mode flag, and at most one remembered tape symbol.
By Lemma 1, \(\mathcal{K}_T\) has an exact one-hot realization as a selective affine SSM controller of hidden dimension \(d=|S_T|=O(|Q|\,|\Gamma|).\) The constructed SSM has binary transition matrices and zero biases. Since it emits exactly the same action sequence as \(\mathcal{K}_T\), it has exactly the same visible output stream and halting behavior. This proves the theorem. ◻
The theorem is a statement about selective finite-precision SSMs, where the transition matrix may depend on the current observation token. It should not be read as a statement about every narrower SSM architecture. In particular, a fixed linear time-invariant recurrence with one common transition matrix is not automatically able to implement arbitrary finite-state control.
We gave an exact characterization of when tool access increases the expressive power of finite-precision recurrent sequence models. The dichotomy is sharp and interface-driven: finite-state bounded-interface tools can always be internalized at a cost of \(\log_2|M|+O(1)\) bits, whereas a single minimal unbounded tool (a tape with local read/write/move commands) yields full Turing completeness with only \(O(\log|Q|+\log|\Gamma|)\) bits of controller memory, and this is witnessed concretely by the exponential \(\mathrm{EQ}_n\) separation. The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity (input-dependent transition matrices) as the architectural ingredient that suffices for exact finite control in the interactive setting.
The supplementary material sharpens the resource accounting in both directions. On the one hand, by offloading the simulated machine’s description onto the tape, \(O(\log B)\) recurrent bits suffice to simulate any \(B\)-state Turing machine (Appendix 11), using small universal machines [20]. On the other hand, if external memory is removed and an arbitrary \(B\)-state transition map must be realized in one exact affine recurrent update, then total recurrent dimension exactly \(B-1\) is necessary and sufficient, for any number of triangular selective-affine layers. The logarithmic and linear answers are therefore both correct, for different, precisely specified resource conventions, and the gap between them quantifies exactly what external persistent memory and machine-specific readout parameters buy.
Natural directions for future work include stochastic and learned controllers, transformers as controllers, multiple concurrent tools, and the interaction between tool access and chain-of-thought budgets studied in [12] and [11].
Fix the input and tape alphabets \(\Sigma=\{0,1\}\), \(\Gamma=\{0,1,\sqcup\}.\) The tape is indexed by \(\mathbb{Z}\). On input \(x=x_0\cdots x_{n-1}\), cell \(i\) initially contains \(x_i\) for \(0\leq i<n\), every other cell contains \(\sqcup\), and the head starts at cell \(0\). The fixed tape oracle supports the commands \[\mathtt{read},\quad \mathtt{left},\quad \mathtt{right},\quad \mathtt{stay},\quad \mathtt{write}_{\gamma}\quad(\gamma\in\Gamma).\] A read command returns the currently scanned symbol in \(\Gamma\). Every write or move command returns the dummy observation \(\mathtt{ok}\). A deterministic Turing machine recognizes a language if it accepts every member and never accepts a nonmember. On a non-member, it may reject or run forever.
Definition 6 (State-bounded Turing-machine classes). For \(B\geq 1\), let \[\mathcal{T}_B = \left\{ K\subseteq\Sigma^*: K\text{ is recognized by a Turing machine with at most } B\text{ internal states} \right\}.\] Accept and reject are regarded as external halting outcomes and are not counted as internal states.
Definition 7 (One-layer selective affine oracle controller). A one-layer selective affine oracle controller consists of a recurrent state \(h=(h_1,\ldots,h_d),\) an action readout \(\rho\), and, for every observation \(\omega\in\Omega:=\Gamma\cup\{\mathtt{ok}\},\) an affine recurrent update: \(\Phi_\omega(h)=A_\omega h+b_\omega.\) At each interaction step, the controller emits the action \(\rho(h)\). If this action is accepting or rejecting, the computation halts. Otherwise, the tape oracle executes the action, returns an observation \(\omega\), and the state is updated to \(\Phi_\omega(h)\). Each recurrent coordinate is stored in a finite-precision register. If coordinate \(j\) uses \(p_j\) bits, the recurrent-memory cost is: \[\operatorname{mem}(\mathcal{M}) := \sum_{j=1}^{d}p_j.\] The affine updates are required to be exact on every reachable state. The fixed parameters and the finite readout table are not charged to the recurrent-memory budget. Let \(\mathcal{S}_b^{(1)}\) be the class of languages recognized by such a controller, with access to the fixed tape oracle above, using at most \(b\) recurrent-state bits.
The exclusion of parameter size from the recurrent-memory budget is essential below. In particular, the readout may contain a finite lookup table depending on the simulated Turing machine.
Lemma 2 (Linear one-hot simulation bound). There is an absolute constant \(C_0\) such that, for every \(B\geq 1\), \[\mathcal{T}_B \subseteq \mathcal{S}_{C_0B}^{(1)}.\] One may take, for example, \(C_0=9\).
The \(O(B)\) inclusion is also a direct consequence of the construction in Theorem 3: once the tape alphabet is fixed, its bound \(O(|Q|\,|\Gamma|)\) becomes \(O(B)\). The proof below is retained to make the controller-state bookkeeping and the explicit constant \(C_0=9\) transparent.
Proof. Let \(M=(Q,q_0,\delta)\) be a Turing machine with \(|Q|\leq B\) and tape alphabet \(\Gamma\). We first construct an observation-driven finite-state controller \(\mathcal{K}_M\) that simulates \(M\) through the tape oracle.
For each \(q\in Q\), introduce a state \(R_q\) whose action is \(\mathtt{read}\). If the oracle returns \(\gamma\in\Gamma\), the transition table of \(M\) determines either a halting outcome or a triple \[\delta(q,\gamma)=(q',\tau,d), \qquad q'\in Q,\quad \tau\in\Gamma,\quad d\in\{L,R,S\}.\] In the latter case the controller passes through the following constant-length protocol: \[R_q \longrightarrow W_{q,\gamma} \longrightarrow D_{q,\gamma} \longrightarrow R_{q'}.\] The state \(W_{q,\gamma}\) emits \(\mathtt{write}_{\tau}\). After receiving \(\mathtt{ok}\), the state \(D_{q,\gamma}\) emits \(\mathtt{left}\), \(\mathtt{right}\), or \(\mathtt{stay}\), according as \(d=L\), \(R\), or \(S\). After the next observation \(\mathtt{ok}\), the controller enters \(R_{q'}\).
If \(\delta(q,\gamma)\) is accepting or rejecting, the controller enters the corresponding halting state. Thus the number of controller states is at most: \[|Q|+|\Gamma||Q|+|\Gamma||Q|+2 \leq 7B+2 \leq 9B.\]
A direct induction on the number of simulated Turing-machine transitions shows that, whenever the controller is in state \(R_q\), the oracle tape and head position coincide with those of \(M\), and \(q\) is the current internal state of \(M\). Hence the controller recognizes the same language as \(M\).
It remains to realize this finite controller by a selective affine SSM. Enumerate its state set as: \[S=\{s_1,\ldots,s_N\}, \qquad N\leq 9B,\] and encode \(s_i\) by the standard basis vector \(e_i\in\{0,1\}^{N}.\) For each observation \(\omega\in\Omega\), define a matrix \(A_\omega\in\{0,1\}^{N\times N}\) columnwise by \(A_\omega e_i=e_j \Longleftrightarrow \delta_{\mathcal{K}_M}(s_i,\omega)=s_j.\) Set every bias to zero. Define the action readout on the reachable one-hot vectors by \(\rho(e_i)=\lambda_{\mathcal{K}_M}(s_i).\) The set of one-hot vectors is invariant under every \(A_\omega\), and the resulting SSM exactly reproduces the controller’s state and action sequences. Each recurrent coordinate is binary, so the recurrent-memory cost is \(N\leq 9B\) bits. Therefore \(\mathcal{T}_B\subseteq\mathcal{S}_{9B}^{(1)}.\) ◻
The proposed logarithmic statement becomes meaningful only after the oracle and the resource accounting have been fixed. Under the model above, it is true.
Lemma 3 (Fixed universal tape controller). There exist:
a fixed observation-driven finite-state tape controller \(\mathcal{U}\);
a self-delimiting binary encoding \(M\mapsto\langle M\rangle\);
such that, whenever the tape contains \(x\,\sqcup\,\langle M\rangle\,\sqcup\) and the head is on the final blank, \(\mathcal{U}\) accepts, rejects, or runs forever exactly as \(M\) does on \(x\). Moreover, if \(M\) has at most \(B\) internal states and tape alphabet \(\Gamma\), then \(|\langle M\rangle| \leq cB\log_2(B+1)\) for an absolute constant \(c\).
Proof. The existence of a fixed universal one-tape Turing machine with three tape symbols follows, for example, by composing Theorems 2.1 and 3.1 of [20]. Its three symbols may be renamed as \(0\), \(1\), and \(\sqcup\).
A fixed tape preprocessor can convert the layout \(x\,\sqcup\,\langle M\rangle\,\sqcup\) into the particular initial encoding required by that universal machine. Composing the preprocessor with the universal machine and then replacing every Turing transition by the fixed read–write–move oracle protocol produces the required finite controller \(\mathcal{U}\).
For the length estimate, label the states of \(M\) by integers below \(B\). Its transition table has \(3B\) entries. Each nonhalting entry contains a next-state label of length \(\lceil\log_2 B\rceil\), a written symbol, and a head direction. Halting entries require only constant additional information. A self-delimiting encoding of \(B\), followed by the transition entries, therefore has length \(O\!\left(B\log(B+1)\right).\) ◻
Theorem 4 (Logarithmic oracle-assisted simulation). There is an absolute constant \(C_1\) such that, for every \(B\geq 1\), \[\mathcal{T}_B \subseteq \mathcal{S}_{ \left\lceil C_1\log_2(B+1)\right\rceil }^{(1)}.\]
For each fixed simulated machine \(M\), the finite word \(w=\langle M\rangle\) is hard-coded in the controller’s fixed action readout: when the counter has value \(j\), the readout emits the preassigned action \(a_j\) that writes the next part of \(w\). Thus the whole description is not initially stored in the recurrent state. During the initialization phase, the controller copies \(w\) onto the oracle tape, which thereafter stores the description for the fixed universal controller \(\mathcal{U}\). This is compatible with the resource convention above because the readout table and oracle memory are not charged to recurrent memory; only the counter, flag, and constant-size finite-control register are charged.
Proof. Fix a Turing machine \(M\) with at most \(B\) states. Write \[w=\langle M\rangle=w_1\cdots w_D, \qquad D\leq cB\log_2(B+1).\] We construct a one-layer selective affine controller that:
scans to the first blank following the input;
writes \(w\) immediately to the right of that blank;
transfers control to the fixed universal controller \(\mathcal{U}\).
Let \[a_0,a_1,\ldots,a_{R-1}, \qquad R=2D+1,\] be the fixed action script \[\mathtt{right},\, \mathtt{write}_{w_1},\mathtt{right},\, \mathtt{write}_{w_2},\mathtt{right},\, \ldots,\, \mathtt{write}_{w_D},\mathtt{right}.\] Every action in this script returns the dummy observation \(\mathtt{ok}\).
Let \(S_{\mathcal{U}}\) be the fixed finite state set of the universal controller. Add two scanner states: \[s_{\mathrm{read}} \quad\text{and}\quad s_{\mathrm{move}}.\] Let \(u\in\{0,1\}^{k}\) be a one-hot register for these states and the states of \(\mathcal{U}\), where \(k\) is an absolute constant independent of \(B\). Let \(z\in\{0,1,\ldots,R\}\) be an integer counter and let \(\eta\in\{0,1\}\) be a program-writing flag. The complete recurrent state is \(h=(z,\eta,u).\)
For every observation \(\omega\), let \(D_\omega\) be the zero–one matrix implementing the appropriate one-hot transition of the fixed scanner/universal controller. In particular, \[D_0e_{s_{\mathrm{read}}} = D_1e_{s_{\mathrm{read}}} = e_{s_{\mathrm{move}}},\] and \[D_{\mathtt{ok}}e_{s_{\mathrm{move}}} = e_{s_{\mathrm{read}}}.\] Let \(\ell(u)\) denote the coordinate of \(u\) corresponding to \(s_{\mathrm{read}}\), and let \(e_{\mathcal{U},0}\) be the one-hot encoding of the initial state of \(\mathcal{U}\).
Define the recurrent updates on reachable states by \[\Phi_{\mathtt{ok}}(z,\eta,u) = \bigl(z+\eta,\eta,D_{\mathtt{ok}}u\bigr), \] \[\Phi_{\sqcup}(z,\eta,u) = \bigl( 0,\, \ell(u),\, D_{\sqcup}u+\eta e_{\mathcal{U},0} \bigr), \] and, for \(\sigma\in\{0,1\}\), \[\Phi_\sigma(z,\eta,u) = \bigl(0,0,D_\sigma u\bigr). \] Each of these maps is affine.
The initial recurrent state is \(h^{(0)}=(0,0,e_{s_{\mathrm{read}}}).\) The readout is defined as follows:
in state \(e_{s_{\mathrm{read}}}\) it emits \(\mathtt{read}\);
in state \(e_{s_{\mathrm{move}}}\) it emits \(\mathtt{right}\);
if \(\eta=1\), \(u=0\), and \(z=j<R\), it emits \(a_j\);
if \(\eta=1\), \(u=0\), and \(z=R\), it emits \(\mathtt{read}\);
if \(u\) encodes a state of \(\mathcal{U}\), it emits the action prescribed by \(\mathcal{U}\).
The readout may be defined arbitrarily on unreachable states.
The scanner alternates between reading the current tape cell and moving right. When it first reads \(\sqcup\), equation (2) sends \((0,0,e_{s_{\mathrm{read}}}) \longmapsto (0,1,0).\) The head is then on the blank immediately following the input.
While \(\eta=1\), every scripted action produces \(\mathtt{ok}\), and equation (1) gives \[(j,1,0)\longmapsto(j+1,1,0).\] Consequently, the controller emits the complete script and writes \(\langle M\rangle\) to the tape. After the final move, the head is on the blank immediately following the description and the recurrent state is \((R,1,0)\). Its next action is \(\mathtt{read}\). The returned blank and equation (2) give \((R,1,0) \longmapsto (0,0,e_{\mathcal{U},0}).\) At this point the tape has the form \(x\,\sqcup\,\langle M\rangle\,\sqcup,\) the head is on the final blank, and the controller has entered the initial state of \(\mathcal{U}\). It therefore accepts, rejects, or runs forever exactly as \(M\) does on \(x\).
The counter \(z\) requires \(\left\lceil\log_2(R+1)\right\rceil = O(\log(B+1))\) bits. The flag \(\eta\) and the one-hot register \(u\) require only a constant number of additional bits. Hence the total recurrent memory is \(O(\log(B+1)).\) All updates are time-homogeneous and affine. The machine-specific description occurs only in the finite readout values assigned to the counter states. ◻
The theorem relies on two conventions:
the tape oracle is free external persistent memory;
the finite model parameters and readout table are not charged to the recurrent-memory budget.
If the simulated transition table had to be represented solely by the recurrent affine state and applied in one recurrent step, the logarithmic conclusion would be false. This is precisely the issue addressed next.
The two questions referred to below are stated explicitly after the model definition. They are meaningful only after external memory is excluded and “implemented” is required to mean one exact recurrent update per input symbol. We use a layered model that is at least as general as the usual triangular selective-affine SSM recurrence.
Definition 8 (Layered triangular selective-affine realization). Fix a field \(\mathbb{K}\) and \(L\geq 1\). An \(L\)-layer triangular selective-affine recurrent system has states \[h_\ell\in\mathbb{K}^{d_\ell}, \qquad 1\leq\ell\leq L.\] For each input symbol \(a\in\{0,1\}\), the update has the form \[h_1^+ = A_{1,a}h_1+b_{1,a},\] and, for \(2\leq\ell\leq L\), \[h_\ell^+ = A_{\ell,a}(h_1,\ldots,h_{\ell-1})h_\ell + b_{\ell,a}(h_1,\ldots,h_{\ell-1}). \] The coefficient functions in (4) may depend arbitrarily on all lower layers. Dependence on updated lower-layer values is also covered, since those values are themselves functions of the old lower-layer prefix. The system exactly realizes \[f:[B]\times\{0,1\}\longrightarrow[B]\] if there is an injective encoding \[e(q) = \bigl(e_1(q),\ldots,e_L(q)\bigr)\] such that \[\Phi_a(e(q))=e(f(q,a))\] for every \(q\in[B]\) and \(a\in\{0,1\}\).
Define the worst-case required total recurrent dimension by: \[D_L(B) := \max_{f:[B]\times\{0,1\}\to[B]} \; \min \left\{ \sum_{\ell=1}^{L}d_\ell: f\text{ has an exact }L\text{-layer realization} \right\}.\]
For a fixed number of layers \(L\), is it true that \(D_L(B)=O(\log B)?\) Equivalently, can every mapping \(f:[B]\times\{0,1\}\to[B]\) be implemented exactly, in one recurrent update per input symbol and without external memory, using only \(O(\log B)\) recurrent-state coordinates (and hence \(O(\log B)\) bits at fixed precision)?
If Question 1 has a negative answer, what is the asymptotically tight, or ideally exact, growth of \(D_L(B)\) as a function of \(B\) and \(L\)?
Definition 9 (Congruence of a deterministic transition system). Let \(Q\) be a finite state set with transition maps \(f_a:Q\to Q\) indexed by input symbols \(a\). A congruence* is an equivalence relation \(\sim\) on \(Q\) that is preserved by every transition: \[q\sim q' \quad\Longrightarrow\quad f_a(q)\sim f_a(q') \qquad\text{for every }a.\] Equivalently, the transition maps descend to well-defined maps on the quotient set \(Q/{\sim}\). The equality relation and the universal relation, in which all states are equivalent, are always congruences.*
Theorem 5 (Answer to Questions 1 and 2). For every \(B\geq 2\) and every \(L\geq 1\), \[D_L(B)=B-1.\] Consequently:
Question 1 has a negative answer, even if the number of layers is allowed to depend on \(B\);
the asymptotically tight worst-case recurrent-state requirement is \(\Theta(B)\) bits under any fixed finite-precision convention;
over the Boolean field \(\mathbb{F}_2\), where one scalar coordinate is one bit, the exact worst-case requirement is \(B-1\) bits.
The hard transition system combines a cyclic permutation \(c\) with a “successor with an absorbing endpoint” map \(s\). The cycle forces any congruence classes to be invariant under cyclic translation, while the map \(s\) destroys every nontrivial translation-invariant partition. Hence this automaton has only the universal congruence and equality.
In a triangular layered realization, equality of the first \(\ell\) layer encodings defines a congruence, because the first \(\ell\) updated layers depend only on the first \(\ell\) current layers. Therefore, at the first layer that distinguishes any states, all \(B\) states must become distinct at once. The lower layers are constant there, so that single layer must realize the entire length-\(B\) successor chain by one fixed affine map. After translating the absorbing state to the origin, this produces a nilpotent orbit of length \(B-1\), which requires at least \(B-1\) linearly independent vectors and therefore dimension at least \(B-1\).
Proof. We first prove the upper bound \(D_L(B)\leq B-1.\) It suffices to use one layer.
Index the state set by \(\{0,1,\ldots,B-1\}.\) In \(\mathbb{K}^{B-1}\), define \(e(B-1)=0\) and \[e(i)=v_i, \qquad 0\leq i\leq B-2,\] where \(v_0,\ldots,v_{B-2}\) are the standard basis vectors.
Fix an arbitrary map \[f:\{0,\ldots,B-1\}\times\{0,1\} \longrightarrow \{0,\ldots,B-1\}.\] For each \(a\in\{0,1\}\), set \(b_a=e(f(B-1,a))\) and define the columns of \(A_a\) by \[A_av_i=e(f(i,a))-b_a, \qquad 0\leq i\leq B-2.\] Then \(A_ae(i)+b_a=e(f(i,a))\) for \(0\leq i\leq B-2\), while \[A_ae(B-1)+b_a=b_a=e(f(B-1,a)).\] Thus every \(f\) has a one-layer affine realization in dimension \(B-1\).
We now prove the matching lower bound. Identify the state set with the cyclic group \[\mathbb{Z}_B=\{0,1,\ldots,B-1\}.\] Consider the two transition maps \[s(i) = \begin{cases} i+1,&0\leq i\leq B-2,\\ B-1,&i=B-1, \end{cases} \] and \[c(i)=i+1\pmod B. \] Define \[f(i,0)=s(i), \qquad f(i,1)=c(i).\]
We claim that the automaton \((\mathbb{Z}_B,s,c)\) has no congruences other than equality and the universal relation. Let \(\sim\) be an equivalence relation satisfying \[i\sim j \quad\Longrightarrow\quad s(i)\sim s(j) \quad\text{and}\quad c(i)\sim c(j). \] Since \(c^B\) is the identity, invariance under \(c\) implies invariance under every cyclic translation. Hence the equivalence classes are the cosets of the subgroup \(H:=\{h\in\mathbb{Z}_B:0\sim h\}.\)
Suppose that \(H\) is nontrivial, and choose \(h\in H\setminus\{0\}.\) Translation invariance gives \[B-1\sim h-1\pmod B.\] Applying \(s\) and using \(h\neq0\), we obtain \[B-1=s(B-1)\sim s(h-1)=h.\] Thus \[h-(B-1)=h+1\pmod B\] belongs to \(H\). Since \(h\in H\) and \(H\) is a subgroup, it follows that \(1\in H\). Therefore \(H=\mathbb{Z}_B\). Hence every congruence is either equality or universal.
Now suppose that the pair \((s,c)\) has an \(L\)-layer realization \[e(i)=\bigl(e_1(i),\ldots,e_L(i)\bigr).\] For each \(\ell\), define an equivalence relation \[i\equiv_\ell j \quad\Longleftrightarrow\quad \bigl(e_1(i),\ldots,e_\ell(i)\bigr) = \bigl(e_1(j),\ldots,e_\ell(j)\bigr).\] Because the first \(\ell\) updated layers depend only on the first \(\ell\) current layers, \(\equiv_\ell\) is a congruence of the automaton: \[i\equiv_\ell j \quad\Longrightarrow\quad f(i,a)\equiv_\ell f(j,a)\] for \(a\in\{0,1\}\).
The full encoding is injective, so \(\equiv_L\) is equality. Let \(r\) be the least layer for which \(\equiv_r\) is equality. Since there are no nontrivial congruences, \(\equiv_{r-1}\) is universal. Consequently, the lower-layer prefix \(\bigl(e_1(i),\ldots,e_{r-1}(i)\bigr)\) is independent of \(i\), while \(e_r\) itself is injective.
Under input \(0\), the update of layer \(r\), restricted to the encoded states, is therefore one fixed affine map \(T(x)=Ax+b\) satisfying \(T(e_r(i))=e_r(s(i)).\)
Let \(x_*:=e_r(B-1).\) Because \(s(B-1)=B-1\), we have \(T(x_*)=x_*.\) Set \(y_i:=e_r(i)-x_*.\) Then \[Ay_i=y_{i+1} \qquad (0\leq i\leq B-2),\] where \(y_{B-1}=0.\) In particular, \[A^{B-1}y_0=0, \qquad A^{B-2}y_0=y_{B-2}\neq0.\]
The vectors \(y_0,Ay_0,\ldots,A^{B-2}y_0\) are linearly independent. Indeed, suppose \(\sum_{j=0}^{B-2}\alpha_jA^jy_0=0\) and let \(j_0\) be the least index with \(\alpha_{j_0}\neq0\). Applying \(A^{B-2-j_0}\) gives \(\alpha_{j_0}A^{B-2}y_0=0,\) because all terms with index larger than \(j_0\) acquire exponent at least \(B-1\) and vanish. This contradicts \(A^{B-2}y_0\neq0\). Thus layer \(r\) has dimension at least \(B-1\), and hence \(\sum_{\ell=1}^{L}d_\ell\geq B-1.\) Combining this with the upper bound proves \(D_L(B)=B-1.\)
At fixed scalar precision, dimension and recurrent bit complexity differ by only a constant factor, giving the tight bound \(\Theta(B)\). Over \(\mathbb{F}_2\), the simplex construction uses exactly \(B-1\) binary coordinates, so the exact bit requirement is \(B-1\). ◻
The logarithmic oracle-assisted theorem and the linear direct realization lower bound answer different questions.
The oracle-assisted simulation is allowed to:
use the unbounded tape as external persistent memory;
write the simulated machine’s transition table to the tape;
take arbitrarily many oracle interactions per simulated transition;
encode the machine-specific program in the fixed readout parameters.
By contrast, the direct realization problem requires the mapping \((q,a)\longmapsto f(q,a)\) to be performed in one recurrent update, without external memory. For this one-step affine problem, \(\Theta(B)\) recurrent state is both necessary and sufficient.