Where Is GPT in the Chomsky Hierarchy?

Summary

Where is GPT in the Chomsky Hierarchy? 14th of December, 2025 The Chomsky hierarchy is a way to classify text-generating algorithms (formally called languages) by how expressive they are. Since generative pretrained transformers, GPTs, are getting quite a bit of attention these days, one might wonder where in the hierarchy they fall. To give a classic example of one category in the hierarchy, context-free languages are those whose strings are produced by iteratively applying rules that locally expand grammar particles into words. This covers practically all programming languages, because they conform to a syntax tree where each branch is an application of such a production rule. A subcategory of context-free languages are n-gram languages, where the possible continuations of a string depend only on a bounded number of words that came before in the sentence (whereas the syntax tree of a context-free language could have unboundedly many branches). Human language is of course much more complicated than these simple classes of languages. One argument for this could be that humans are generally intelligent, and can therefore simulate a Turing machine, which at least in principle gives us the power to understand any computable language. This is a strictly more expressive category of all the languages we talked about above. A more prosaic argument might describe concrete kinds of sentences that provably cannot be produced by, say, context-free grammars, which I will leave to linguistics textbooks. Surely then, a system like GPT, that understands human language so well that it can write perfect sonnets and win math competitions, must also be in this same rung in the Chomsky hierarchy as humans, by being Turing complete? First, we could be cheeky and say that, because GPT has a finite context window with finitely many possible tokens at each position, it can trivially only model n-gram languages. This is true, but not really in the spirit of the question. By the same logic, ...