The Chomsky hierarchy is all about the type of memory. First note that to get to interesting classes, i.e. everything above regular languages / finite state au

The Chomsky hierarchy is all about the type of memory. First note that to get to interesting classes, i.e. everything above regular languages / finite state automata (FSA), you need infinite memory. When you have finite memory, it is always only just as powerful as a FSA. Adding one (infinite) stack will give you pushdown automata complexity, and adding two (or more) (infinite) stacks will get you to Turing machines. Consider that a float in hardware (f32, bf16, or whatever you like), but also in reality (think of the neuronal spike voltage) is not infinite in memory but finite. This is different from mathematics, where you can store infinite memory in a real number. Note that there is an infamous paper, "On the computational power of neural nets", Siegelmann & Sonntag, 1992, which states that RNNs are Turing complete. But this construction assumes that you can store infinite memory in a single neuron activity, which is never true in practice. In practice, a RNN or LSTM has finite memory. However, in practice, also any computer has finite memory. Also the human brain has finite memory. So, it follows, you always only have the complexity of FSAs. But is this right? Wouldn't the intuition say sth different? Maybe the Chomsky hierarchy is not really so relevant? Or the question is somewhat ill posed. What would make a computer Turing complete? You need infinite memory. So, you need to abstract away from a particular computer towards the concept of a computer with infinite memory. The official C language definition calls this an "abstract machine". This abstract machine is Turing complete. How can you apply this to neural networks? How to define an abstract neural network with some explicit memory component, which can grow to infinite sizes? You get to memory-augmented models like the differential neural computer (extended from the neural Turing machine). In theory, you can think of abstract variants of those models with infinite memory, and then you can think about the Chomsky hierarchy. In practice, the memory is always finite though. What they do in the paper is to focus more on the Chomsky hierarchy in practice, i.e. applied to some actual benchmarks. When you limit the length of the input problems, there is some maximum amount of memory which should be sufficient to solve them. Depending on the structure of the neural model, it gives you a clue to what compute complexity it mostly corresponds to when you test it. I have written down some own thoughts on this here: https://stackoverflow.com/questions/2990277/how-useful-is-turing-completeness-are-neural-nets-turing-complete https://stackoverflow.com/questions/2990277/how-useful-is-tu...