翱游网络

2024年年底，历史的潮流似乎充满了不确定性，理论计算机科学也不例外。在几项突破性进展和新发现的背后，计算机科学领域也面临着许多疑问和局限性。

例如，人工智能再次成为今年的热门话题。研究人员开始深入探索神经网络中的"黑箱"——这些网络驱动着像Bard和ChatGPT这样的聊天机器人，并试图证明这些系统确实能够理解它们所处理和生成的数据。然而，也有越来越多的声音认为，人工智能的发展速度已经开始放缓。

计算机科学的其他领域则取得了更加明确的成功。经过几十年的沉寂，一种神秘的数值生物——第五只忙碌海狸，终于被发现。但即使是在这里，消息也并非全是好消息：初步的搜索结果显示，第六只忙碌海狸可能超出了无法逾越的数学障碍。

错误更正码这一领域——一种在发生错误时能自我修复的数学构造——在2024年也引起了广泛关注。研究人员首次证明了对量子计算机至关重要的错误更正技术确实有效。然而，另一项发现则揭示，某些经典错误更正码在本质上效率低下，这让人们对这种"神奇现象"在实际应用中的前景感到失望。

忙碌海狸的突破

今年夏天，一支由热衷业余爱好者组成的团队解决了计算机科学中的一个重大未解难题——找到了第五只忙碌海狸。这个问题源于一种特别费时的计算机程序，该程序需要长时间运行，因而得名“忙碌海狸”。这个问题与计算机科学和数学中一些最深刻的未解问题密切相关。

问题的核心是图灵机，它是最简单的计算设备之一，最早由艾伦·图灵提出，作为通用计算机的模型，现在可以轻松在线模拟。根据图灵机的初始设置，它们要么会永远运行下去，要么在有限的步骤后停止。忙碌海狸问题问的是：在规定数量的规则下，这些机器能运行多长时间？研究人员已经解决了具有1、2、3或4条规则的机器问题（分别需要1、6、21和107步），但第五只忙碌海狸的数字却困扰了他们几十年。

<《量子》杂志记者本·布鲁贝克（Ben Brubaker）记录了一个由全球非专业人士组成的团队如何找到并证明这个数字——47,176,870，并且证明它不会更大。尽管这个问题没有直接的实际应用，但找到答案本身标志着在人类对复杂数学问题的挑战中取得了一次胜利。而根据对第六只忙碌海狸的初步搜索结果来看，我们可能永远无法再见到类似的突破。

另外，在今年1月，我们曾报道过另一支由非专业人士组成的多元化团队，他们解决了另一类数字谜题。这项工作聚焦于约翰·康威的“生命游戏”（Game of Life），并追寻特定长度的重复图案。通过发现19步和41步后重复的图案，他们证明了“生命游戏”是“全周期”的——即它能够在每一个可能的步数后重复。

通过编码实现更好的生活

量子计算机一直吸引着研究人员的关注，但尽管经过了多年的努力，真正有用的量子计算机仍然遥不可及。这部分是由于它们的本质：量子计算机利用量子力学的奇妙规律，这些规律支配着宇宙中最微小的相互作用，因此它们容易受到严重的错误影响。近30年前，研究人员证明，通过某种方式组合量子比特（即计算机中的量子比特，相当于传统计算机的二进制比特），可以使其容忍错误。但要实现这一点，每个量子比特的错误率必须低于某个最低阈值。今年12月，谷歌的一个团队宣布他们已经达到了这个水平，首次证明量子错误更正码可以使这些先进的机器成为可能（尽管还远未实现）。

<《量子》杂志还在2月报道了一种新型的量子错误更正码，这种码基于非周期性铺砌——由一组形状组合而成，组合方式永不重复。正如布鲁贝克所写，这种联系之所以可行，是因为对于这些铺砌和码来说，“了解大系统的一小部分并不能揭示整个系统的情况”。

今年，量子错误更正并非唯一的亮点——科学家们还解答了一个关于经典错误更正码的重大问题，这些码可以用于我们今天使用的计算机。最有前景的错误更正码一直是极其低效的，研究人员一直在想是否有可能做到更好。经过20多年的研究，答案是否定的：这种低效性无法避免。

洞察量子世界

今年的许多重要发现表明，通过计算机科学的视角，即使是复杂难懂的量子力学世界也能变得稍微清晰一些。微小粒子之间的相互作用极为复杂，科学家们仍然难以完全理解它们所组成的系统。然而，四位计算机科学家最近开发了一种新的算法，能够高效地输出任何系统的完整描述，这是该领域的首次突破。通过将数学中的优化工具与计算机科学中的放松技术结合，研究团队展示了如何快速生成任何量子系统的哈密顿量——一种完整描述系统的超级方程——前提是该系统保持在恒定温度下。

同一个研究团队还做出了另一个重要的量子发现，他们证明了温度的升高不仅会削弱粒子之间的纠缠互动，还总有一个特定温度，纠缠会在此温度下完全消失。

另外一个独立团队也展示了一个与量子系统相关的问题——寻找其局部最小能量水平——对于量子计算机来说相对容易解决。这不仅是量子物理领域的一个进步，还证明了量子计算机确实有可能解决一些超出经典计算机能力范围的有用问题。量子理论的复杂性也可能为未来的密码学提供新基础，特别是在当前的密码学体系在量子比特面前可能崩溃的情况下。

对人工智能的深入理解

人工智能可能是理论计算机科学中最具可见性——同时也是最易被误解的领域。今年，因ChatGPT而闻名的OpenAI发布了其o1聊天机器人模型，这些模型似乎能够完成一些令人惊讶且强大的创新性任务。然而，尽管取得了这样的进展，这些工具的内部运作依然不明晰，这为安全漏洞和其他问题留下了隐患。

研究人员特别关注这些模型是否真的理解它们所说的内容，还是仅仅像2021年一篇论文所说的“随机鹦鹉”，仅仅重复它们之前听到的内容。最新的研究表明，这些机器可能确实有理解能力。谷歌DeepMind的一个团队在研究这些语言模型完成其非凡任务所需的技能时得出结论，机器不可能仅仅是重复训练数据。“他们有力地展示了，某些模型可以生成将技能和话题结合的文本，而这些组合几乎肯定不会出现在训练数据中。”AI先驱Geoff Hinton说道，他因在机器学习领域的工作获得了2024年诺贝尔物理学奖。

事实上，一种被称为“grokking”的现象——模型经过过度训练，直到达到意外的精通水平——为我们提供了理解这些神秘机器如何处理信息的新方式。其他团队则利用计算复杂性理论——计算机科学的一个分支，研究不同问题的相对难度——帮助解释为什么语言模型在逐步解决问题时似乎表现得更好。