20

I was reading the Javascript tutorial of Mozilla and I come through this piece of information.

High-level languages embed a piece of software called "garbage collector" whose job is to track memory allocation and use in order to find when a piece of allocated memory is not needed any longer in which case, it will automatically free it. This process is an approximation since the general problem of knowing whether some piece of memory is needed is undecidable (can't be solved by an algorithm).

I am familiar with the notion of undecidability and garbage collector, but I can't seem to understand why this is an undecidable problem?

ralzaul
  • 4,280
  • 6
  • 32
  • 51

2 Answers2

15

All garbage collectors I'm familiar with work by collecting memory which can no longer be accessed, e.g. all (the transitive closure of) variables pointing to it went out of scope. But that's an under-approximation of the set of of memory spaces that can be collected, because at any point a memory location may still have a variable pointing to it in scope, yet it will never be accessed again.

Finding the precise set of memory spaces that can be collected is trivially reducible to any undecided problem - for example, find the set of memory spaces that can be collected at point A in the following program:

x = allocate()
// Point A
if (result of some known-to-be-undecidable problem is true):
  print(x)

And so finding that set is undecidable in itself.

Oak
  • 26,231
  • 8
  • 93
  • 152
  • It is not trivial that it can be reducible to any undecided problem – Nursultan Zarlyk May 14 '16 at 17:05
  • 3
    @NursultanZarlyk let's name the solution of the problem tested by the if statement as `P`, and let's call the the collector's decision whether the memory pointed to by `x` can be collected at point A as `C`. `P => !C` since otherwise our collector may collect live memory, and `!P => C` since our hypothetical collector doesn't over-approximate. This means a solution for `P` is also a solution for `C`, thus it's a reduction. What am I missing here? – Oak May 14 '16 at 17:17
  • Theory of Computation always was a magic for me. Thank you for deep answer. – Nursultan Zarlyk May 16 '16 at 09:27
11

So you can modify any program to allocate some space on the heap and only access it if the original program terminates. An optimal garbage collector would then only collect the memory if the program does not terminate.

Can we decide if a program will terminate or not?

transporter_room_3
  • 2,583
  • 4
  • 33
  • 51