理論的研究は、状態空間モデルなどの固定された有限精度の再帰シーケンスモデルにおいて、外部ツールアクセスが計算表現力を高める時期を正確に説明している。この研究は、有限状態と無限状態のツールの間のモデル能力への影響に関する明確な二項対立を確立した。

  • 有限状態であるツール自体は、システムの複雑さに本質的に何も追加しない。なぜなら、有限メモリを持つ任意の有界インターフェースオラクルは、最小限の追加ビットでコントローラーによって内部化できるからである。
  • ローカルな読み書きと移動コマンドをサポートするテープという単一の最小無限状態ツールは、拡張されたシステムをチューリング完全にする。
  • この研究は、EQ_n を解く際にツールなしでは 2^n ステートが必要だが、テープツールを使用すると定数サイズのコントローラーだけで済むという指数関数的な分離を示している。
  • このチューリング完全な構成は、バイナリワンホット隠れ状態と選択性を持つ自然な1層の有限精度選択的アフィン SSM コントローラーによって正確に実現される。

著者たちは、O(log B) の再帰ビットが任意の B ステートチューリングマシンをシミュレートするのに十分であることを証明し、この能力の増加とそのための特定のアーキテクチャ要件の両方を確立した。