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 study 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, and establish a separation between the two regimes analyzed. First, every finite-state bounded-interface tool with memory set M can be internalized at a cost of at most 2M +O(1) recurrent bits, so the combined system remains finite-state. Second, a single unbounded tape with only local / / commands suffices for Turing completeness: every single-tape Turing machine with state set Q and tape alphabet Γ is simulated by a controller with O(Q+ Γ) recurrent bits, and EQ n requires 2 n states without tools but one constant-size controller with the tape. Third, this construction is realized exactly by a one-layer finite-precision selective affine SSM with binary one-hot states, 0,1 transition matrices, and zero biases. Under explicitly stated resource conventions, O(B) recurrent bits suffice for tape-assisted simulation of any B-state Turing machine, whereas directly realizing an arbitrary B-state transition map in one exact affine update without external memory requires total recurrent dimension exactly B-1. Fixed description size, occupied tape cells, and interaction cost are reported separately from recurrent memory. Our results concern exact expressivity under deterministic semantics, not learnability or empirical performance.