Warum ist es unentscheidbar, ob ein Teil der Erinnerung benötigt wird?

Question

Ich habe das Javascript-Tutorial von Mozilla reediert und ich komme durch diese Information.

Hochsprachen einbetten ein Stück Software „garbage Sammler“ genannt, deren Aufgabe es ist, Speicherzuordnung zu verfolgen und um finden Verwendung, wenn ein Stück zugewiesenen Speicher nicht mehr in welchem ​​Fall benötigt wird, , es wird es automatisch befreien. Dieser Prozess ist eine Approximation, da das allgemeine Problem, zu wissen, ob ein Teil des Speichers benötigt wird, unentscheidbar ist (kann nicht durch einen Algorithmus gelöst werden).

Ich bin vertraut mit dem Begriff der Unentscheidbarkeit und Müllsammler, aber ich kann nicht verstehen, warum dies ein unentscheidbares Problem ist?

Answer 1

Alle Müllsammler, mit denen ich vertraut bin, arbeiten durch Sammeln von Speicher, auf den nicht mehr zugegriffen werden kann, z. alle (die transitive Schließung von) Variablen, die darauf hindeuten, gingen aus dem Rahmen. Aber das ist eine Unterannäherung der Menge der Speicherräume, die gesammelt werden können, weil an irgendeinem Punkt eine Speicherstelle immer noch eine Variable haben kann, die auf sie im Gültigkeitsbereich zeigt, aber nie wieder darauf zugegriffen wird.

den genauen Satz von Speicherplatz zu finden, die gesammelt werden können, ist trivial reduzierbar auf ein noch nicht entschiedenes Problem - zum Beispiel, um den Satz von Speicherplatz finden, die am Punkt A in dem folgende Programm gesammelt werden können:

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

Und diese Menge zu finden, ist in sich unentscheidbar.

Answer 2

So können Sie jedes Programm ändern, um Speicherplatz auf dem Heap zuzuweisen und nur darauf zuzugreifen, wenn das ursprüngliche Programm beendet wird. Ein optimaler Garbage Collector würde dann nur den Speicher sammeln, wenn das Programm nicht beendet wird.

Können wir entscheiden, ob ein Programm beendet wird oder nicht?