Un estudio teórico proporciona una descripción exacta de cuándo el acceso externo a herramientas aumenta la expresividad computacional de los modelos recurrentes de secuencia de precisión finita fija, como los modelos de espacio de estados. La investigación establece una dicotomía nítida entre las herramientas de estado finito y las de estado infinito en cuanto a su impacto en la capacidad del modelo.
- Las herramientas que son ellas mismas de estado finito añaden esencialmente nada a la complejidad del sistema, ya que cualquier oráculo con interfaz acotada y memoria finita puede ser internalizado por el controlador con bits adicionales mínimos.
- Una única herramienta mínima de estado infinito, específicamente una cinta que soporta comandos locales de lectura, escritura y movimiento, hace que el sistema aumentado sea Turing completo.
- El estudio exhibe una separación exponencial donde resolver EQ_n requiere 2^n estados sin herramientas pero solo un controlador de tamaño constante con la herramienta de cinta.
- Esta construcción Turing completa se realiza exactamente mediante un controlador SSM afín selectivo de precisión finita de una sola capa natural con estados ocultos one-hot binarios y selectividad.
Los autores demuestran que O(log B) bits recurrentes son suficientes para simular cualquier máquina de Turing de B estados, estableciendo tanto la capacidad como los requisitos arquitectónicos específicos para este aumento de poder.