为什么知道是否需要某些内存是不可判定的？

Question

我正在使用Mozilla的Javascript教程,我来了解这条信息.

高级语言嵌入了一个名为"垃圾收集器"的软件,其工作是跟踪内存分配和使用,以便找到不再需要分配内存的时间,在这种情况下,它将自动释放它.该过程是近似的,因为知道是否需要某些存储器的一般问题是不可判定的(不能通过算法解决).

我熟悉不可判断性和垃圾收集器的概念,但我似乎无法理解为什么这是一个不可判定的问题？

Answer 1

我熟悉的所有垃圾收集器通过收集无法访问的内存来工作,例如指向它的所有(传递闭包)变量都​​超出了范围.但这是可以收集的一组内存空间的近似值,因为在任何时候内存位置仍然可以在范围内有一个指向它的变量,但它永远不会再被访问.

找到可以收集的精确内存空间集可以简单地减少到任何未决定的问题 - 例如,找到可以在以下程序中的A点收集的内存空间集:

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

所以发现这个集合本身就是不可判定的.

Answer 2

因此,您可以修改任何程序以在堆上分配一些空间,并且只有在原始程序终止时才访问它.如果程序没有终止,那么最佳垃圾收集器将仅收集内存.

我们可以决定一个程序是否会终止？