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.


1 Answer 1


Yes, there's plenty of theoretical work on space complexity. No, it's not necessarily Turing machines; you can talk about space complexity in other models of computation, e.g., the RAM model. You might find that more practically relevant. I suggest you study RAM machines and existing work on space complexity.

It's not clear what you mean by "levels of memory", and I don't see anything there that's useful. Instead, standard space complexity results talks about the space requirement: e.g., $\Theta(n)$ space, $\Theta(n^2)$ space, $\Theta(2^n)$ space. See also LOGSPACE, PSPACE and similar complexity classes.

  • $\begingroup$ Don't have you at least have a grasp of what i'm talking about with "levels of memory" ? For instance, what is the difference in the ammount of memory required by a 1-momment delayer and the ammount of memory required by a 3-momment delayer ? Doesnt the first have to remember one level back and the third have to remember 3 levels back ? Wouldn't you agree that the memory required by a 1-momment delayer would be similar to the ammount of memory required to do binary addition with carriers ? $\endgroup$
    – nerdy
    Feb 1, 2015 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.