What question did this study set out to answer?

The aim is to analyze transformer-based language models using the Chomsky hierarchy to identify their computational limitations.

March 3, 2026Open Access

Transformers, the Chomsky Hierarchy, and the Limits of Simulation

Key Points

The aim is to analyze transformer-based language models using the Chomsky hierarchy to identify their computational limitations.
Analyzed transformer architecture under Chomsky hierarchy constraints
Characterized transformers as bounded finite-state transition systems
Distinguished between simulation and instantiation
Explored economic implications of bounded systems
Transformers can approximate higher language classes but lack full computational power of Turing machines.
They operate under fixed architectural and precision constraints.
The paper discusses the trade-offs between probabilistic and deterministic computational methods.

Abstract

This paper analyzes transformer-based language models through the lens of the Chomsky hierarchy. We argue that implemented transformers are best characterized as bounded finite-state transition systems (Type-3 by mechanism) under fixed architectural and precision constraints. While such systems can approximate higher language classes within bounded regimes, they do not instantiate pushdown stacks, linear bounded tapes, or Turing-complete symbolic machinery. The paper distinguishes simulation from instantiation and explores both formal and economic implications of this boundary, including compositional drift under invariant density and the runtime cost tradeoffs between probabilistic recomputation and deterministic enforcement.

Transformers, the Chomsky Hierarchy, and the Limits of Simulation

Key Points

Abstract

Cite This Study