2 ms·

* On the Turing Completeness of Modern Neural Network Architectures, https://arxiv.org/abs/1901.03429 https://arxiv.org/abs/1901.03429 * On the Computational P

* On the Turing Completeness of Modern Neural Network Architectures, https://arxiv.org/abs/1901.03429 https://arxiv.org/abs/1901.03429 * On the Computational Power of Transformers and its Implications in Sequence Modeling, https://arxiv.org/abs/2006.09286 https://arxiv.org/abs/2006.09286

tgv 4y ago
A TM cannot learn an arbitrary CFG. It needs constraints. Those constraints must also exist in our brain. At birth. It's like an NN architecture. Our brains are much more complex than an artificial NN, though. So the mere thought that the two somehow share functionality after a wildly different learning process is somewhat far-fetched.
- naasking 4y ago
  > A TM cannot learn an arbitrary CFG. It needs constraints. Well sure, because CFGs can have unbounded depth, and all real brains are finite. But they can learn bounded CFGs: https://arxiv.org/abs/2112.09174 https://arxiv.org/abs/2112.09174 > Our brains are much more complex than an artificial NN, though. Yes, brains have a few orders of magnitude more parameters, and lots of evolutionary baggage. It's not clear how many parameters would be needed without that evolutionary baggage. Time will tell. > So the mere thought that the two somehow share functionality after a wildly different learning process is somewhat far-fetched. I don't know what precisely you mean by "share functionality", but it doesn't seem like a stretch to suggest they are in some sense isomorphic given Turing equivalence. Rule 110 doesn't look like it should share much with Turing machines or the lambda calculus or SKI combinators, but these are all equivalent in a formal sense.
  - tgv 4y ago
    That's not what learnable means, but it would only show there needs to be an a priori limit on the structure of learning. > in some sense isomorphic given Turing equivalence Then you're brain is just like any CPU, which is very far from what such a statement tries to express in the context of NNs.
    - naasking 4y ago
      > Then you're brain is just like any CPU, which is very far from what such a statement tries to express in the context of NNs. Yes, the brain is like a CPU + a specific program running on that CPU. The properties of that program are where the isomorphism comes in. So to come full circle back to your original point, we don't yet know that "weight adaptations" are not a sufficient operational model for that program.
    - naasking 4y ago
      I'm also struggling to understand how you can claim that LLMs cannot learn CFGs when ChatGPT can understand nested quantifiers, which simply cannot be parsed using CFGs. LLMs can actually learn unrestricted grammars.

tgv 4y ago

A TM cannot learn an arbitrary CFG. It needs constraints. Those constraints must also exist in our brain. At birth. It's like an NN architecture. Our brains are much more complex than an artificial NN, though. So the mere thought that the two somehow share functionality after a wildly different learning process is somewhat far-fetched.

naasking 4y ago
> A TM cannot learn an arbitrary CFG. It needs constraints. Well sure, because CFGs can have unbounded depth, and all real brains are finite. But they can learn bounded CFGs: https://arxiv.org/abs/2112.09174 https://arxiv.org/abs/2112.09174 > Our brains are much more complex than an artificial NN, though. Yes, brains have a few orders of magnitude more parameters, and lots of evolutionary baggage. It's not clear how many parameters would be needed without that evolutionary baggage. Time will tell. > So the mere thought that the two somehow share functionality after a wildly different learning process is somewhat far-fetched. I don't know what precisely you mean by "share functionality", but it doesn't seem like a stretch to suggest they are in some sense isomorphic given Turing equivalence. Rule 110 doesn't look like it should share much with Turing machines or the lambda calculus or SKI combinators, but these are all equivalent in a formal sense.
- tgv 4y ago
  That's not what learnable means, but it would only show there needs to be an a priori limit on the structure of learning. > in some sense isomorphic given Turing equivalence Then you're brain is just like any CPU, which is very far from what such a statement tries to express in the context of NNs.
  - naasking 4y ago
    > Then you're brain is just like any CPU, which is very far from what such a statement tries to express in the context of NNs. Yes, the brain is like a CPU + a specific program running on that CPU. The properties of that program are where the isomorphism comes in. So to come full circle back to your original point, we don't yet know that "weight adaptations" are not a sufficient operational model for that program.
  - naasking 4y ago
    I'm also struggling to understand how you can claim that LLMs cannot learn CFGs when ChatGPT can understand nested quantifiers, which simply cannot be parsed using CFGs. LLMs can actually learn unrestricted grammars.