Une étude théorique fournit un compte rendu exact du moment où l'accès aux outils externes augmente l'expressivité computationnelle des modèles de séquence récurrents à précision finie fixe, tels que les modèles d'espace d'état. La recherche établit une dichotomie nette entre les outils à état fini et ceux à état infini concernant leur impact sur la capacité du modèle.
- Les outils qui sont eux-mêmes à état fini n'ajoutent essentiellement rien à la complexité du système, car toute oracle à interface bornée avec une mémoire finie peut être internalisée par le contrôleur avec un nombre minimal de bits supplémentaires.
- Un seul outil minimal à état infini, spécifiquement un ruban prenant en charge les commandes locales de lecture, d'écriture et de déplacement, rend le système augmenté Turing-complet.
- L'étude présente une séparation exponentielle où la résolution de EQ_n nécessite 2^n états sans outils, mais seulement un contrôleur de taille constante avec l'outil ruban.
- Cette construction Turing-complète est réalisée exactement par un contrôleur SSM affine sélectif à précision finie à une couche naturelle, avec des états cachés one-hot binaires et une sélectivité.
Les auteurs prouvent que O(log B) bits récurrents suffisent pour simuler n'importe quelle machine de Turing à B états, établissant à la fois la capacité et les exigences architecturales spécifiques pour cette augmentation de puissance.