Search papers, labs, and topics across Lattice.
ETHCRRC Zhuzhou InstituteRobotics and Perception GroupShenzhen International Center for IndustrialShenzhen Research Institute of Big DataTengen Intelligence InstituteUZHJul 7, 2026arXiv:2607.06155This paper provides a detailed analysis of how tool access affects the computational expressivity of finite-precision recurrent models, specifically focusing on deterministic finite-state controllers. The authors establish that while finite-state tools do not enhance expressivity, a minimal infinite-state tool, such as a tape with local commands, can render the system Turing complete, significantly increasing its computational power. Their findings demonstrate that a simple one-layer selective affine state-space model can achieve this enhanced expressivity with logarithmic memory overhead, revealing a stark contrast in capabilities based on the type of tool used.
A single minimal infinite-state tool can elevate finite-precision models to Turing completeness, while finite-state tools add virtually no expressivity.
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, namely a tape supporting only local $\mathtt{read}$, $\mathtt{write}$, and $\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, where $O(\log B)$ recurrent bits suffice to simulate any $B$-state Turing machine, and prove a matching impossibility result.
