Something I noticed when skimming the paper that is also called out by one of the reviewers:
"Moreover, in the submission the authors considered only Transformers with input and output of bounded lengths, which are quite strange since Turing machines do not pose constraints on the tape length. If the length is constrained in Transformers, they clearly do not match Turing machines."
I don't think the comparison apply in this way, Turing machine may operate on an unconstrained tape but they only look at a single cell at each step.
This find and replace technique operate on a bounded context but, in the same way as a turing machine, they can "technically" operate on an unconstrained tape (technically here because the find transformer wouldn't be able to lookup an infinite tape in the real world).
I guess you could say that a turing machine has a bounded input length of 1.
Okay, actually I think I just misunderstood the argument in the paper. After taking a second look, I think their argument goes as follows:
A typical autoregressive transformer model operates on a fixed-size context that acts as both input and a queue to which the output of the model is appended. If a model operates on a context of length k with n possible symbols in its alphabet, then there are n^k possible contexts.
If you run such a model for n^k iterations, then
1) if the <eos> (end of sequence) symbol appears in the context, then the model halts.
2) if the <eos> symbol never appears in the context, then you know the model never halts because it must repeat a context string by the pigeon hole principal and must be in an infinite loop.
Therefore, the halting problem is decidable for transformer models with finite length contexts that are autoregressive in this way and that would imply a contradiction if we claim they are Turing complete (because the halting problem is known to be undecidable for Turing complete systems).
I'm not entirely sure this proves anything (it sounds believable I guess?), but at least I think it describes the argument they are making.
It is sort of interesting how it highlights the different between a system that can write to any position in memory vs. one that can only append to memory while being required to delete the first memory cell (where memory is a queue).
However, the overall paper is awful and pretty hard to take seriously.
An autoregressive transformer is trivially a finite state machine with the state being the k input tokens. The state update just discards the leftmost token of the context and adds the predicted token to the right.
It is somewhat tempting to look at the entire token sequence as a tape but that is misleading, once a token fell out of the context it is lost forever whereas a Turing machine always maintains access to the entire tape as it can just move as far left as it likes.
As said, for this question it is really more useful to think of the state as a fixed size array or queue of tokens where in each step everything gets pushed one position to the left by the newly predicted token and the leftmost token gets discarded.
This seems at least plausible, and it agrees with my preconceived notions that a good chunk of LLM capability is driven by memorization and not computation[0]. Is there any substantive critique of the underlying idea from the other reviewers, and not just the (evidently terrible) presentation of it?
I'm not sure why that argument is applicable to a queue but not to any fixed sized memory? A transformer can conceptually modify any position by simply outputting the whole context except with 1 different value. Basically, it's restating in a convoluted way the known fact that anything with finite memory has finite states and thus the halting problem is solvable.
Yeah, I guess you're right. The queue vs. addressable memory thing seems secondary. Is the real difference that a transformer model is stateless and Turing machine is stateful? And the assumption of a stateless model is why they can assert that a repeated state implies an infinite loop (assuming we're not sampling the softmax to get the output token)?
But then, the same can be said of a computer with a finite-sized memory.
I think the real thing in the paper is the computational complexity of calculations. With turing machines, each step is O(1), with transformers it's at least O(n), where n is memory size.
A modern computer can be cast as a seq-to-seq model, too, so their "arguments" apply to those as well, just with larger n and k. Any finite machine suffers from this.
"Moreover, in the submission the authors considered only Transformers with input and output of bounded lengths, which are quite strange since Turing machines do not pose constraints on the tape length. If the length is constrained in Transformers, they clearly do not match Turing machines."