Perché sapere se è necessario un pezzo di memoria è indecidibile?

Question

Stavo riecheggiando il tutorial su Javascript di Mozilla e passo attraverso questa informazione.

linguaggi avanzati incorporano un software chiamato "garbage collector", il cui compito è quello di monitorare l'allocazione di memoria e utilizzare per trovare quando un pezzo di memoria allocata senza più in qual caso , lo libererà automaticamente. Questo processo è un'approssimazione poiché il problema generale di sapere se è necessario un pezzo della memoria è indecidibile (non può essere risolto da un algoritmo).

mi è familiare con il concetto di indecidibilità e garbage collector, ma io non riesco a capire perché questo è un problema indecidibile?

Answer 1

Tutti i garbage collector Ho familiarità con il lavoro raccogliendo memoria a cui non è più possibile accedere, ad es. tutte le variabili (la chiusura transitiva di) che puntavano ad essa sono andate oltre lo scopo. Ma questa è una sotto-approssimazione dell'insieme di spazi di memoria che possono essere raccolti, perché in qualsiasi punto una posizione di memoria può ancora avere una variabile che punta ad essa in ambito, eppure non sarà mai più accessibile.

Trovare il preciso insieme di spazi di memoria che possono essere raccolti è banalmente riducibile ad alcun problema indecisi - per esempio, trovare l'insieme di spazi di memoria che possono essere ritirati presso il punto A nel seguente programma:

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

E quindi trovare quel set è indecidibile in sé.

Answer 2

Quindi è possibile modificare qualsiasi programma per allocare spazio nello heap e accedervi solo se il programma originale termina. Un garbage collector ottimale raccoglie quindi la memoria solo se il programma non termina.

Possiamo decidere se un programma terminerà o no?