A theoretical study provides an exact account of when external tool access increases the computational expressivity of fixed finite-precision recurrent sequence models, such as state-space models. The research establishes a sharp dichotomy between finite-state and infinite-state tools regarding their impact on model capability.
- Tools that are themselves finite-state add essentially nothing to the system's complexity, as any bounded-interface oracle with finite memory can be internalized by the controller with minimal additional bits.
- A single minimal infinite-state tool, specifically a tape supporting local read, write, and move commands, makes the augmented system Turing complete.
- The study exhibits an exponential separation where solving EQ_n requires 2^n states without tools but only a constant-size controller with the tape tool.
- This Turing-complete construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states and selectivity.
The authors prove that O(log B) recurrent bits suffice to simulate any B-state Turing machine, establishing both the capability and the specific architectural requirements for this increase in power.