3 ms·

This response by the authors to the reviews to me looks like they didn't really understand the objection: > First, it's worth noting that different reviewers s

This response by the authors to the reviews to me looks like they didn't really understand the objection: > First, it's worth noting that different reviewers sometimes gave opposite critiques of the paper, e.g. Reviewer erh8: The conclusion in this paper is questionable... It contradicts to [1], which shows that Transformers are Turing-complete Reviewer bz3o: The main claim that transformers with finite attention span are not computationally universal is both somewhat obvious and previously already stated If I'm reading the reviews correctly, the claim by both reviewers was that transformers are actually Turing complete, but one reviewer added that they're "obviously" not Turing complete if you restrict their memory a priori (which I would agree is obvious). So there isn't really a contradiction between the reviews. From briefly skimming the paper, this does look indeed to me like researchers which aren't really familiar with theoretical CS trying to handwave their way into something that looks ground-breaking. But while you absolutely can get away with vague-ish description in a more experimental part of CS, you absolutely can't get away with it in computability theory - that field is rigorous, and basically maths.

inciampati 3y ago
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 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...
- Tainnor 3y ago
  It appears that it's exactly the distinction between fixed and arbitrary precision that decides whether or not transformers are Turing Complete: https://openreview.net/forum?id=HyGBdo0qFm&noteId=r1lxKiAJlV https://openreview.net/forum?id=HyGBdo0qFm&noteId=r1lxKiAJlV 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.
  - light_hue_1 3y ago
    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.
    - Tainnor 3y ago
      > 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.

inciampati 3y ago

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 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...

Tainnor 3y ago
It appears that it's exactly the distinction between fixed and arbitrary precision that decides whether or not transformers are Turing Complete: https://openreview.net/forum?id=HyGBdo0qFm&noteId=r1lxKiAJlV https://openreview.net/forum?id=HyGBdo0qFm&noteId=r1lxKiAJlV 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.
- light_hue_1 3y ago
  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.
  - Tainnor 3y ago
    > 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.