计算机科学重大突破：计算所需内存空间或远低于预期

理论计算机科学家一直在探索空间（内存）和时间之间的关系。近日，一项新的研究表明，计算所需的内存空间可能远低于之前的预期，这为计算机科学的基础理论带来了新的认识。

长期以来的理论认知

在过去的50年里，专家们普遍认为，一个需要X步完成的计算，至少需要X/log X个内存单元。例如，如果一个计算需要100步，由于log 100等于2，那么这个计算就需要50个内存单元。

然而，一项新的研究表明，实际所需的内存空间可能远低于这个数值。研究结果显示，一个需要X步完成的计算，可能只需要X log X的平方根个内存单元。回到之前的例子，如果一个计算需要100步，那么所需的内存单元将从50个骤降至14个左右。

尽管这项发现并不能直接缩短计算所需的时间，但它揭示了计算机科学中空间和时间关系的复杂性，也意味着我们对这一领域仍有很多未知的知识需要探索。

麻省理工学院的理论计算机科学家 Ryan Williams 在论文中写道：“理论计算机科学中最基本的问题之一是：计算中时间与空间的关系如何？我们已经证明，通过简化为树评估问题，多带图灵机和电路具有惊人的空间效率评估算法。”

“树评估问题”最初是在2000年代后期提出的，它涉及重复解决一个简单的数学问题，将一对输入数字转换为一个输出。由于其分支状结构，问题被分层复制，必须先解决子问题才能解决“根”问题，因此得名“树评估问题”。Williams 的论文指出，最近的研究表明，在计算机内存已满的情况下，可以重复使用内存。

这个想法被称为“催化计算”，借用了化学术语，描述了额外的内存如何像催化剂一样产生计算“反应”。正如《新科学家》所说，这一突破就像人类只用短期记忆解决一个复杂的多步骤问题。

据《新科学家》报道，Williams 的模型代表了任何计算问题，一旦他应用了这种新的树评估算法，它就显示了所需内存的急剧减少。不过，Williams 告诉媒体，该结果是“数学技巧”和“神奇抵消”的结合。

这项突破意味着，完成计算所需的内存空间更少了，但它并没有缩短计算所需的时间。因此，Williams 的发现不太可能从根本上改变我们使用计算机的方式。但如果反过来被发现，那么更多的内存可以加快计算时间。不难想象，这样的突破会有多么巨大，尤其是在处理器速度提升（即摩尔定律）正在放缓的时刻。

空间和时间是我们已知现实的组成部分，对于我们的计算现实来说，也是如此。