When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?

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 Γ, a controller with O(\log |Q| + \log |Γ|) bits of internal memory simulates it, and we exhibit a concrete exponential separation: 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.