Re:Neural Networks and the Chomsky Hierarchy [DeepMind, 2022]
by naasking on Monday January 23, 2023 @09:43AM
(#34489292)
> In other words, when you have reasonably big practical finite problem with limited memory. FSA runs quickly out of memory.
Yes this is a difference in the expressiveness of each model, because FSAs can require a combinatorial explosion in the number of states to model a finite Turing machine. The parent is still technically correct though.
> The point of stating that a mathematical model is Turing Complete is to reveal the capability of the model to perform any calculation, given a sufficient amount of resources (i.e. infinite), not to show whether a specific implementation of a model does have those resources. Non-Turing complete models would not be able to handle a specific set of calculations, even with enough resources, something that reveals a difference in the way the two models operate, even when they have limited resources. Of course, to prove this property, you have to do have to assume that the models are able to use an infinite amount of resources, but this property of a model is relevant even when resources are limited.
In other words, when you have reasonably big practical finite problem with limited memory. FSA runs quickly out of memory.