1
$\begingroup$

We know that how much time a program needs is not computable.

Do we know how much memory a program needs is decidable?

$\endgroup$
2
  • 4
    $\begingroup$ Consider the program that loads a Turing machine, runs one step, allocates one byte, runs another step, allocates another byte, and so on until the Turing machine halts. $\endgroup$
    – user253751
    Dec 1 '15 at 23:08
  • 1
    $\begingroup$ Any arbitrary program, or specifically tailored programs? Embedded software developers often write code with specific patterns to permit the measure of maximum memory usage, choosing to forgo the constructions which make general purpose programs hard to estimate. $\endgroup$
    – Cort Ammon
    Dec 2 '15 at 0:12
8
$\begingroup$

No, and there's a simple way to see it.

Suppose that there was a way to compute how much memory a program needs. What does it mean precisely? It would mean that there's a way to find, given an arbitrary program¹, a number $n$ such that the program can run on a machine with $n$ bits¹ of memory.

First snag: what about programs that require an infinite amount of memory? Our memory analyzer would have to return something like $\infty$ in that case. Ok, that's not too bad — we could have an analyzer that returns either a (finite) amount of memory or $\infty$. If the program needs an infinite amount of memory, it doesn't terminate (each step of computation can only access a finite amount of memory).

If the memory analyzer returns a finite amount $n$, then we can run the program in a machine with $n$ bits of memory. But a “machine with $n$ bits of memory” is a finite automaton! Deciding whether a finite automaton terminates is easy.

So our memory analyzer has let us decide whether the program terminates. Since this is impossible (it's the halting problem), the hypothesis that there's a way to compute how much memory a program needs is false. If you have a correct memory analyzer (i.e. one that returns $n$ or $\infty$ if a program can run in at most $n$ bits of memory) then there must be programs for which the analyzer returns $\infty$, yet the program could in fact run in a finite amount of memory.

¹ A program including all of its inputs! The amount of memory is a function of the inputs in general.
² You can use any unit, bits are just an example. That only changes the amount of memory from a finite number to a different finite number.

$\endgroup$
0
1
$\begingroup$

There's the notion of how much memory a program 'actually' needs - to consider. You would have to consider the programming language of the program being analyzed. I'm sure there are other factors as well, but in the end, it doesn't really matter.

If you acknowledge (and it has been proven) that it is impossible to know if a program will halt, then I think it should follow that it is equally undecidable how much memory it will require.

Consider the following line of pseudocode:

malloc(rand())

Here we asked for a random amount of memory to be allocated. Since it's impossible to know how much exactly this line of code will need, then likewise it is unknowable how much the entire program will need.

Therefore, I will make the statement, that if we can provide one example that contradicts the statement that it is decidable, then it is not (Turing) decidable.

$\endgroup$
7
  • 2
    $\begingroup$ that exactly is the problem.. why should it follow? your answer gives nothing new than what I stated in first sentence of my problem. $\endgroup$
    – Turbo
    Dec 1 '15 at 19:53
  • $\begingroup$ Because if you don't know when the program will end, then how can you know how much memory it will use? You cannot. $\endgroup$
    – ryuu9187
    Dec 1 '15 at 19:54
  • 1
    $\begingroup$ may not be the case... any program under consideration could very well need a finite amount of memory all the time and still running time could be undecidable. $\endgroup$
    – Turbo
    Dec 1 '15 at 19:55
  • $\begingroup$ I'll provide a proof. $\endgroup$
    – ryuu9187
    Dec 1 '15 at 19:57
  • $\begingroup$ @Turbo To address your first comment: I changed one word in my response. Because what I intended to say was actually that it is not decidable if a program will halt given an input, not necessarily "when." That is indeed something completely different, but which is also quite impossible (or, has yet to be proven - just look at OS scheduling algorithms). $\endgroup$
    – ryuu9187
    Dec 2 '15 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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