The Chomsky Hierarchy isn't the right way to think about, in fact the Chomsky paradigm probably held back progress in language technology over the past 70 years.
In the Kuhnian sense, Syntactic Structures was the vanguard of a paradigm shift that let linguists do "normal science" in terms of positing a range of problems and writing papers about them. It was also useful in computer science for formally defining computer languages that are close enough to natural languages that people find them usable.
On the other hand, attempts to use the Chomsky theory to develop language technology failed miserably outside of very narrow domains and in the real world Markov models and conditional random fields often outperformed when the function was "understanding", "segmentation", etc.
From an engineering standpoint, the function that tells if a production is in the grammar that is central to the theory is not so interesting for language technology, I mean, if LLMs were -centric then an LLM would go on strike if you got the spelling or grammar wrong or correct you in a schoolmarmish William Safire way but rather it is more useful for LLMs to silently correct for obvious mistakes the same way that real language users do.
The other interesting thing is the mixing of syntax and semantics. For a long time I believed the "Language Instinct" idea of Pinker in which the ability to serialize and deserialize language is a peripheral that is attached to an animal and you need the rest of the animal and even the surrounding world to have "human" competence. Now LLMs come around and manage to show a lot of linguistic competence without the rest of the animal and boy we have egg on our face, and coming out of the shadow of the Chomsky theory, structuralism will rear it's head again. (e.g. "X is structured like a language" got hung up on the unspoken truth that "language is not structured like a language")
I don’t think LLMs contradict the Pinker description - it just turns out that the output stream embodies a lot of information, and you can construct a model (of some reasonable fidelity) of the original sources from sufficient examples of the output stream.
> For a long time I believed the "Language Instinct" idea of Pinker in which the ability to serialize and deserialize language is a peripheral that is attached to an animal and you need the rest of the animal and even the surrounding world to have "human" competence.
I think most PL parsers use recursive descent, which doesn't require any formal language theory. That said, it's possible that formal language theory has enabled regular expressions to enter widespread use - first via theory; then to make tokenisers; then included in text editors; and then to make GREP.
You're going to have a very hard time parsing a language using recursive descent if you don't understand some formal language theory. Recursive descent algorithms have a lot of trouble with left-recursion, and can result in arbitrary backtracking if you're not careful, which can blow up memory and time. To fix left-recursion you need to rewrite your grammar, which means familiarity with formal language theory. To avoid backtracking you typically use an LL(N) or variations thereof, which once again require having a pretty good understanding of formal language theory.
Don't worry, the LLMs are already post-structuralist (at least the ones working on them are often familiar with those thinkers). Which is incredibly disturbing, I think, for many linguists who have spent their entire careers fighting against the French, only to have such philosophical and intellectual work become the most important in the development of this new technology. Hey, at least I'm employed! (And they said it "wasn't serious," that Chomskian Linguistics was the "real science"!)
Well, technically, they're more structuralist than post-structuralist. Arguably they even prove that Saussure's original structuralist hypothesis was correct.
"This covers practically all programming languages, because they conform to a syntax tree where each branch is an application of such a production rule."
Except that practically all practically used programming languages are not context-free.
No. If you have infinite memory, you get into decidability issues, which the author does. Lots of people have been down this rathole. Penrose is probably the most prominent. It doesn't help.
The real issues are combinatoric. How hard is this? Is there an upper bound? Is this one of those many problems where the worst case limit is exponential but the average limit is much lower? Or where a "good enough" solution is far cheaper computationally than a perfect one. The Traveling Salesman problem is the classic example, but it comes up in other optimization contexts, such as the simplex method of linear programming.
Although to be fair, nothing above regular (that I'm aware of, it's been a while) requires infinite space, just unlimited space... you can always make a real Turing machine as long as you keep adding more tape whenever it needs it.
there’s decent work on computational reasoning power of transformers, SSMs, etc.
some approximate snippets that come to mind are that decoder-only transformers recognize AC^0 and think in TC^0, that encoder-decoders are strictly more powerful than decoder-only, etc.
Person with last name Miller iric if poke around on arXiv, a few others, been a while since was current top of mind so ymmv on exact correctness of above snippets
The Chomsky hierarchy is a classification of grammars. So it's about Syntax.
GPT is purely about semantics, about truth. To the extent that I think it can be said to be fundamentally informal in its dedication to truth, since it can easily be prompted to produce syntactically incorrect output - wrt the syntax of whatever language whose semantics determine the truth GPT is asked to reflect.
So I think this is a categorically incorrect question.
I mean, what is the fundamental syntax of the output of an LLM? It would have to be that any sequence of utf8 chars is valid.
LLMs have absolutely nothing to do with truth. If anything the analogy is closer to syntax as LLMs are pure form, just language in absence of any context or reference.
So unless I'm mistaken, the TL;DR is that GPTs inherently can not be Turing complete because they always terminate, ie. there is always a non-zero probability of the end-of-token character to be generated.
Seems like a fair argument to raise, although not too insightful.
As a nitpick, it really is not the case that most programming languages are context-free, but I can sympathize with what the author is trying to get at. Most programming languages have a context-free superset that is useful to use as one of many stages in the parsing pipeline, before type checking and name resolution etc... but apart from perhaps some dynamically typed programming languages, the vast majority of programming languages are context-sensitive, not context-free.
Except that as far as I understand, one of the inspirations for the Turing machine is to explain precisely the computations a human computer could perform with (potentially a lot of) pen and paper.
We can simulate a Turing machine, given storage. The infinite storage and infinite time is always a sticking point when comparing any real physical system to a theoretical Turing machine, so we tend to ignore those bits.
The "flaw" is also fixed by simply not recognizing the end-of-sampling token. Even the limited size of the context window can be worked around with tool calls.
The Chomsky Hierarchy isn't the right way to think about, in fact the Chomsky paradigm probably held back progress in language technology over the past 70 years.
In the Kuhnian sense, Syntactic Structures was the vanguard of a paradigm shift that let linguists do "normal science" in terms of positing a range of problems and writing papers about them. It was also useful in computer science for formally defining computer languages that are close enough to natural languages that people find them usable.
On the other hand, attempts to use the Chomsky theory to develop language technology failed miserably outside of very narrow domains and in the real world Markov models and conditional random fields often outperformed when the function was "understanding", "segmentation", etc.
From an engineering standpoint, the function that tells if a production is in the grammar that is central to the theory is not so interesting for language technology, I mean, if LLMs were -centric then an LLM would go on strike if you got the spelling or grammar wrong or correct you in a schoolmarmish William Safire way but rather it is more useful for LLMs to silently correct for obvious mistakes the same way that real language users do.
The other interesting thing is the mixing of syntax and semantics. For a long time I believed the "Language Instinct" idea of Pinker in which the ability to serialize and deserialize language is a peripheral that is attached to an animal and you need the rest of the animal and even the surrounding world to have "human" competence. Now LLMs come around and manage to show a lot of linguistic competence without the rest of the animal and boy we have egg on our face, and coming out of the shadow of the Chomsky theory, structuralism will rear it's head again. (e.g. "X is structured like a language" got hung up on the unspoken truth that "language is not structured like a language")
I don’t think LLMs contradict the Pinker description - it just turns out that the output stream embodies a lot of information, and you can construct a model (of some reasonable fidelity) of the original sources from sufficient examples of the output stream.
> For a long time I believed the "Language Instinct" idea of Pinker in which the ability to serialize and deserialize language is a peripheral that is attached to an animal and you need the rest of the animal and even the surrounding world to have "human" competence.
Yeah you just need 10 trillion tokens of data.
I think most PL parsers use recursive descent, which doesn't require any formal language theory. That said, it's possible that formal language theory has enabled regular expressions to enter widespread use - first via theory; then to make tokenisers; then included in text editors; and then to make GREP.
You're going to have a very hard time parsing a language using recursive descent if you don't understand some formal language theory. Recursive descent algorithms have a lot of trouble with left-recursion, and can result in arbitrary backtracking if you're not careful, which can blow up memory and time. To fix left-recursion you need to rewrite your grammar, which means familiarity with formal language theory. To avoid backtracking you typically use an LL(N) or variations thereof, which once again require having a pretty good understanding of formal language theory.
Nah. Source: have done it without formal language theory. You can do most things by printf debugging and kludging.
(Left-recursion? Use a while loop! Mutable state is a pathway to many abilities functional programmers consider unnatural.)
Don't worry, the LLMs are already post-structuralist (at least the ones working on them are often familiar with those thinkers). Which is incredibly disturbing, I think, for many linguists who have spent their entire careers fighting against the French, only to have such philosophical and intellectual work become the most important in the development of this new technology. Hey, at least I'm employed! (And they said it "wasn't serious," that Chomskian Linguistics was the "real science"!)
Well, technically, they're more structuralist than post-structuralist. Arguably they even prove that Saussure's original structuralist hypothesis was correct.
"This covers practically all programming languages, because they conform to a syntax tree where each branch is an application of such a production rule."
Except that practically all practically used programming languages are not context-free.
> Let's grant our GPT an infinite context-window.
No. If you have infinite memory, you get into decidability issues, which the author does. Lots of people have been down this rathole. Penrose is probably the most prominent. It doesn't help.
The real issues are combinatoric. How hard is this? Is there an upper bound? Is this one of those many problems where the worst case limit is exponential but the average limit is much lower? Or where a "good enough" solution is far cheaper computationally than a perfect one. The Traveling Salesman problem is the classic example, but it comes up in other optimization contexts, such as the simplex method of linear programming.
Regular...albeit astronomically large (unless we're granting idealizations like infinite context, etc.)
Exactly, same as all real-world computers.
Although to be fair, nothing above regular (that I'm aware of, it's been a while) requires infinite space, just unlimited space... you can always make a real Turing machine as long as you keep adding more tape whenever it needs it.
there’s decent work on computational reasoning power of transformers, SSMs, etc.
some approximate snippets that come to mind are that decoder-only transformers recognize AC^0 and think in TC^0, that encoder-decoders are strictly more powerful than decoder-only, etc.
Person with last name Miller iric if poke around on arXiv, a few others, been a while since was current top of mind so ymmv on exact correctness of above snippets
You are probably thinking of Merrill (whose work is referenced towards the end of the article).
This is a trivial category mistake.
The Chomsky hierarchy is a classification of grammars. So it's about Syntax.
GPT is purely about semantics, about truth. To the extent that I think it can be said to be fundamentally informal in its dedication to truth, since it can easily be prompted to produce syntactically incorrect output - wrt the syntax of whatever language whose semantics determine the truth GPT is asked to reflect.
So I think this is a categorically incorrect question.
I mean, what is the fundamental syntax of the output of an LLM? It would have to be that any sequence of utf8 chars is valid.
LLMs have absolutely nothing to do with truth. If anything the analogy is closer to syntax as LLMs are pure form, just language in absence of any context or reference.
So unless I'm mistaken, the TL;DR is that GPTs inherently can not be Turing complete because they always terminate, ie. there is always a non-zero probability of the end-of-token character to be generated.
Seems like a fair argument to raise, although not too insightful.
As a nitpick, it really is not the case that most programming languages are context-free, but I can sympathize with what the author is trying to get at. Most programming languages have a context-free superset that is useful to use as one of many stages in the parsing pipeline, before type checking and name resolution etc... but apart from perhaps some dynamically typed programming languages, the vast majority of programming languages are context-sensitive, not context-free.
> GPTs inherently can not be Turing complete because they always terminate
I'm not sure that was intended entirely seriously. After all, humans always terminate too...
To follow on logically, maybe humans aren't Turing complete? we are not equivalent to Turing machines...
No machine instantiated in the physical universe is Turing complete in this sense.
Except that as far as I understand, one of the inspirations for the Turing machine is to explain precisely the computations a human computer could perform with (potentially a lot of) pen and paper.
And an unlimited life span.
We can simulate a Turing machine, given storage. The infinite storage and infinite time is always a sticking point when comparing any real physical system to a theoretical Turing machine, so we tend to ignore those bits.
"Unbounded" is a better term to use than "infinite."
As a quick hack, is this flaw fixed by using top-p or top-k or min-p or whatever the current hottest logit sampling algorithm is?
The "flaw" is also fixed by simply not recognizing the end-of-sampling token. Even the limited size of the context window can be worked around with tool calls.
On Little Saint James, with Chomsky himself.