Transformers with fixed precision and any amount of memory are not Turing complete. They're bounded by a variant of first order logic with counting quantifiers. https://arxiv.org/abs/2301.10743
This supports the intuitive idea that they "learn circuits for things" that I've heard a few others mention.
If they have infinite precision then I suppose they can simulate a Turing machine in their infinitely precise states...
I think the larger point though is that "is X Turing Complete?" depends on the exact assumptions made and that's a point that the authors of the paper IMHO failed to understand while reading the reviews.
The arbitrary vs fixed precision people are also totally clueless.
All of the arbitrary precision papers should have been rejected. This is CS theory 101. Any non-trivial architecture is not just Turing complete, it can perform hypercomputation (solving the halting problem), if it can use arbitrary precision numbers.
> Any non-trivial architecture is not just Turing complete, it can perform hypercomputation (solving the halting problem), if it can use arbitrary precision numbers.
Can you explain this part? (It doesn't seem like CS theory 101 to me - maybe 201).
I suppose that I'm not entirely sure what you mean by "use arbitrary precision numbers". TMs can use arbitrary precision numbers (integers and rationals) and they can't solve the halting problem, so you must mean something different.
If what you say is true (I don't really know anything about transformers), then that reflects rather poorly on the field that such wrong results would end up being published.
This supports the intuitive idea that they "learn circuits for things" that I've heard a few others mention.
If they have infinite precision then I suppose they can simulate a Turing machine in their infinitely precise states...