Um estudo teórico fornece uma conta exata de quando o acesso externo a ferramentas aumenta a expressividade computacional de modelos recorrentes de sequência de precisão finita fixa, como modelos de espaço de estados. A pesquisa estabelece uma dicotomia nítida entre ferramentas de estado finito e infinito em relação ao seu impacto na capacidade do modelo.
- Ferramentas que são elas mesmas de estado finito adicionam essencialmente nada à complexidade do sistema, pois qualquer oráculo com interface limitada e memória finita pode ser internalizado pelo controlador com bits adicionais mínimos.
- Uma única ferramenta mínima de estado infinito, especificamente uma fita que suporta comandos locais de leitura, escrita e movimento, torna o sistema aumentado Turing completo.
- O estudo exibe uma separação exponencial onde resolver EQ_n requer 2^n estados sem ferramentas, mas apenas um controlador de tamanho constante com a ferramenta de fita.
- Esta construção Turing completa é realizada exatamente por um controlador SSM afim seletivo de precisão finita de uma única camada natural com estados ocultos one-hot binários e seletividade.
Os autores provam que O(log B) bits recorrentes são suficientes para simular qualquer máquina de Turing de B estados, estabelecendo tanto a capacidade quanto os requisitos arquitetônicos específicos para este aumento de poder.