CODEWITHSUNDEEP
memory-managementgarbage-collectiondecidable
ralzaul
ralzaul

Reputation: 4470

Why knowing whether some piece of memory is needed is undecidable?

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?

Upvotes: 20

Views: 1164

Answers (2)

Oak
Oak

Reputation: 26868

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.

Upvotes: 16

transporter_room_3
transporter_room_3

Reputation: 2633

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?

Upvotes: 12

Related Questions