Почему знать, нужен ли какой-то кусок памяти, неразрешимо?

Question

Я перечитывал урок по Javascript для Mozilla и пролистал эту информацию.

В языки высокого уровня встроено программное обеспечение, называемое "сборщик мусора", задачей которого является отслеживание выделения и использования памяти, чтобы определить, когда часть выделенной памяти больше не нужна, и в этом случае она автоматически освобождает ее. Этот процесс является приближенным, поскольку общая проблема, связанная с определением того, нужен ли какой-то фрагмент памяти, неразрешима (не может быть решена алгоритмом).

Мне знакомо понятие неразрешимости и сборщика мусора, но я не могу понять, почему это неразрешимая проблема?

Answer 1

Все сборщики мусора, с которыми я знаком, собирают память, к которой больше нельзя получить доступ, например, все переменные (транзитивное замыкание), указывающие на нее, вышли из области видимости. Но это недооценка набора пространств памяти, которые могут быть собраны, потому что в любой точке ячейка памяти может иметь переменную, указывающую на нее в области видимости, но к ней больше никогда не будет обращаться.

Поиск точного набора областей памяти, которые могут быть собраны, легко сводится к любой нерешенной проблеме - например, найти набор областей памяти, которые можно собрать в точке A, в следующей программе:

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

И поэтому поиск этого набора сам по себе неразрешим.

Answer 2

Таким образом, вы можете изменить любую программу для выделения некоторого пространства в куче и доступа к ней только в том случае, если исходная программа завершается. Оптимальный сборщик мусора будет собирать память только в том случае, если программа не завершит работу.

Можем ли мы решить, будет ли программа прекращена или нет?