News for hackers. Stuff that matters.
Re:Neural Networks and the Chomsky Hierarchy [DeepMind, 2022] by jltsiren on Monday January 23, 2023 @09:56AM (#34489473)
The distinction is very practical. It's better to think about it in terms of hard-coded limits vs. arbitrary scaling than finite vs. infinite. Anything designed to handle n items needs "infinite" memory.

Language classes are about the code, not about the computer. With a finite state automaton, you have to commit to the size of the input in advance and write the state transitions explicitly. While there exist structurally similar automata that can handle larger inputs, your automaton – your code – cannot handle them. You can generate those automata algorithmically, but in order to do that, you need a more expressive formalism that can handle n items.

There are no comments on this comment yet.