Теоретическое исследование предоставляет точное описание того, когда внешний доступ к инструментам увеличивает выразительную силу фиксированных рекуррентных моделей последовательностей конечной точности, таких как модели пространств состояний. Исследование устанавливает четкую дихотомию между инструментами с конечным и бесконечным числом состояний относительно их влияния на возможности модели.
- Инструменты, которые сами по себе имеют конечное число состояний, практически не добавляют сложности системе, поскольку любой оракул с ограниченным интерфейсом и конечной памятью может быть интернализирован контроллером с минимальными дополнительными битами.
- Один минимальный инструмент с бесконечным числом состояний, а именно лента, поддерживающая локальные команды чтения, записи и перемещения, делает расширенную систему тьюринговски полной.
- Исследование демонстрирует экспоненциальное разделение: решение задачи EQ_n требует 2^n состояний без инструментов, но только контроллер постоянного размера с инструментом-лентой.
- Эта тьюринговская конструкция точно реализуется естественным однослойным контроллером SSM конечной точности с селективной аффинностью, бинарными скрытыми состояниями one-hot и селективностью.
Авторы доказывают, что O(log B) рекуррентных битов достаточно для симуляции любой машины Тьюринга с B состояниями, устанавливая как возможности, так и конкретные архитектурные требования для этого увеличения мощности.