Transformers are universally expressive — given enough parameters, they can represent any function. Universal expressiveness is a statement about capacity, not about tendency. The question is not what a transformer can represent but what it will learn.
Infinite-width transformers exhibit an inherent preference for simpler algorithms within the EPTHS complexity class (arXiv:2603.11161). Despite being able to express arbitrarily complex functions, the inductive bias of the architecture channels learning toward lower-complexity solutions. The network can represent a hard algorithm. It will tend to find an easy one.
This preference is not a limitation of training — it is an architectural property. The structure of attention and feedforward layers, in the infinite-width limit, favors solutions that decompose into operations within a specific complexity class. Search, copy, and sort are within this class. Higher-complexity algorithms — those requiring computational steps that exceed the class — are expressible but not preferred. The network would need to be steered past its inductive bias to find them.
The connection to grokking is direct. The authors define grokking formally as the capacity to generalize to arbitrary problem sizes with controllable error and minimal sample adaptation. This distinguishes genuine algorithmic learning (the network has captured the algorithm) from statistical fitting (the network has memorized the training distribution). The complexity ceiling determines which algorithms can be grokked: those within the preferred complexity class are reachable through standard training. Those beyond it require something more.
Expressiveness is not bias. What a network can do and what it will do are different questions with different answers.