I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it.
But then i was confused to what "memory requirement" really means and how we could quantify it .
Looking for how Computational Complexity treats the memory requirement of a computational problem made me even more confused, because it always consider memory requirement under Turing Machines ... so it really doesnt treat the memory requirement as universal as it could ( applied to any possible model of computation : be it FSM, Lambda Calc, or whatever ).
Let me elaborate on my confusion.
It was intuitively thinking of characterizing the memory requirement of algorithms in terms of levels of memory. For automatas, binary addition of numbers too small so we don't need carriers would be a problem that would require no memory at all .
But addition with carriers and 1-momment delaying would be problems at least 1 level of memory. Binary multiplication of arbitrarily large numbers, however, would require arbitrarily large levels of memory . It's so wierd that Combinational Logic circuits can solve all those problems ( arithmetic with carriers ) if it doesn't have any memory at all ( no flip-flop ). How can we understand that ? Is a combinational logic circuit doing computations ? Can we see it as a weak model of computation ?
I had a hope that Space Complexity in the Computational Complexity discipline cold formalize this idea of "levels of memory, but it seems that since the framework is always Turing Machines, everything requires memory, even a simple addition without carriers ( in fact, it needs memory to simulate combinational logic circuits that are models of computation that don't require memory ) .
But there are many problems with this notion of "levels of memory".
1 - What does a level of memory really mean ? Do we universally have only two ways of encoding those levels of memory : either on the states of a machine , or on auxiliary memory read by a machine.
2 - In case the first question is true, would the correspondence for encoding levels of memory on the states of a machine be : n levels of memory require at least 2^n states ? At least, for Finite State Machines, it seems to be that way .
But what about the correspondence for encoding levels of memory on auxiliary memory ( tape-memory ) read by a machine ?
Anyways, i'm really stuck with this doubt for some time and any clarification ( suggestion of a topic for me to read, or any resource at all , explanations and any insight about that ) on how we can understand treat this memory requiment concept universally would be really helpful.
Thanks a lot in advance.
