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")
Chomsky Hierarchy is his more fundamental work that joins computer science and linguistics. It was published in IRE Transactions on Information Theory. Chomsky, Noam (1956). "Three models for the description of language" https://chomsky.info/wp-content/uploads/195609-.pdf
Type-3 grammar ≡ finite-state automaton
Type-2 grammar ≡ Non-deterministic pushdown automaton
Type-1 grammar ≡ Linear-bounded non-deterministic Turing machine
Type-0 grammar ≡ Turing machine
ps. Chomsky was already aware of Finite State Automata and Turing Machines and understood that they match Type-3 and Type-0. Pushdown Automata was invented later, and connection between Type-1 grammar and Linear Bounded Automata was made few years later.
I asked Copilot
answer yes or no, is the following Java method syntactically well formed
static int aMethod() { return "5"; }
No.
It’s syntactically valid as Java code, but it will not compile because it returns a String where
an int is required.
here is a set of rules: ... is the production ... in the grammar?
And that's true about everything they do, one could argue that "in an exact sense, LLM can't do anything at all") They'll make a try at a weird question like
what percent of North Americans would recognize the kitsune hand gesture?
what is lowest mass eigenstate of the neutrino?
[1] javac implements type 1 behavior in the java language which is a substrate
E.g. would it be possible to create an algorithm that takes a grammar (and maybe a desired context window size) as input and constructs a transformer network that generates sentences exactly from that grammar?
("Construct" meaning directly setting the weights, without any iterative training process)
It should be already clear from this that this notion of language is rather different from natural languages. For example, if there is a formal language that contains "Good morning" and "My hovercraft is full of eels" as valid sentences, then nothing distinguishes these sentences any more. (Of course you could add annotations and build semantic values but they are not essential to the discussion of formal languages.)
It gets a bit more ridiculous when you try to connect LLMs to the Chomsky hierarchy. Modern LLMs do not really operate on the principle of "is this a valid sentence?" yet provide vastly superior results when it comes to generating naturally sounding sentences.
I think LLMs have put an end to any hope that formal language theory (in the style of Chomsky Hierarchy) will be relevant to understanding human languages.
Ultimately these are categories of formal languages, and natural language is an entirely different kind of thing.
Yeah you just need 10 trillion tokens of data.
Shalgren, Distributional Legacy: The Unreasonable Effectiveness of Harris’s Distributional Program. https://doi.org/10.1080%2F00437956.2024.2414515
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.
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
Except that practically all practically used programming languages are not context-free.
Programming languages usually have a number of "higher-level semantic layers" on top of the syntax tree that impose further constrains - e.g. that identifiers must have consistency between usage and definition, that all expressions are valid according to the type system, etc.
But all that stuff happens after an AST is created and so doesn't really affect the basic grammar.
I think if you ignore those higher-level constraints, a number of languages have valid context-free grammars.
T * x;
One could argue that it is acceptable to produce an ambiguous parse and defer the decision, and in practice compilers do rely on semantic information to resolve such cases.
However, this is not what context-free means in the Chomsky sense: a context-free grammar must be able to determine the syntactic structure without reference to prior declarations or semantic state.
───
I’m not arguing it’s useless — I’m trying to understand its scope here.
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.
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.
I'm not sure that was intended entirely seriously. After all, humans always terminate too...
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.
> There is a simple argument showing that GPTs, even with an infinite context window, cannot be Turing complete. Since the vocabulary size is finite, the rows of the embedding matrix are bounded, meaning each embedding is in a compact subset of Rn. By Tychonoff's Theorem, the product of the compact spaces the input embeddings live in is also compact. Because the transformer architecture does a bounded number of continuous operations, the output probabilities are bounded from above and below. In particular, the probability of emitting the end-of-sequence token (the special token that halts the completion) is bounded from below by some constant, so the probability of stopping in finite time is 1.
Even if the conclussion might be correct, the argument is pure nonsense.
First of all, why do we need to invoke compactness and Tychonoff's Theorem? Any serious discussion of computability must avoid discussing real numbers. And furthermore, here it is completely unnecessary. All sets are actually finite, so any mention of compactness is just fancy wording for finite in this case.
Second, a probability argument doesn't prove anything about turing completeness. Realistically we must consider LLM's as deterministic machines. The fact that we like to interpret the output of an ML model doesn't have anything to do with actual probability of what happens during execution of an LLM (again, it ia deterministic).
Third, even if we accept the probability argument, we can easily resolve it by just removing the end-of-sequence token and guarantee that the process never stops.
I think the real argument against Turing completeness of GPTs (even with infinite context) would be more along the lines of the fact that it must operate with finite number representations. And a consequence of this would be that it maps an infinite context into a finite set of states, which must result in periodic output at some point.
Finally, as a meta-point, why do so many people enjoy making such quasi-mathematical arguments? Often invoking theorems which obviously can't apply, if they just took a bit of time to clearly define the question. To me it seems like ML people know just enough math to notice some superficial correspondence, but lack the rigor to be able to trully evaluate it.