为什么超级马里奥在数学上比大多数算法更复杂
虽然它看起来只是一个关于水管工拯救公主的简单平台跳跃游戏，但超级马里奥实际上是通往理论计算机科学最深奥奥秘的门户。来自麻省理工学院（MIT）的新研究表明，该游戏的某些配置在数学上是不可判定的，这使其处于远超标准计算问题的复杂度类别中。
从 PSPACE 到 RE-Complete：复杂度的巨大飞跃
多年来，包括 MIT 教授 Erik Demaine 在内的研究人员达成了一个共识，即超级马里奥属于 PSPACE 复杂度类别。这类问题是可解的，但随着输入规模的增长，需要消耗极其庞大的内存和时间。虽然 PSPACE 问题非常困难，但只要给予足够的资源，计算机在根本上仍然是“可解”的。
然而，由 Hayashi Ani、Holden Hall、Ricardo Ruiz 和 Naveen Venkat 组成的学生团队最近的研究打破了这一假设。通过利用关卡编辑器和 Super Mario Maker，研究人员构建了特定的 RE-Complete 关卡。这意味着游戏已经进入了不可判定问题的领域。在这些特定场景下，从数学上讲，不可能编写出一个能够始终准确预测马里奥能否成功到达旗杆或城堡的计算机程序。
与停机问题的联系
要理解为什么一个电子游戏会是不可判定的，必须追溯到艾伦·图灵（Alan Turing）和停机问题（Halting Problem）。图灵证明了不存在一种通用算法可以确定任何给定的程序最终会停止还是永远运行下去。
MIT 研究团队通过一种称为归约（reduction）的技术，将这一逻辑应用于蘑菇王国（Mushroom Kingdom）。通过将超级马里奥关卡分解为被称为“小部件”（gadgets）的局部组件，研究人员能够在游戏机制内模拟复杂的计算逻辑。这些小部件充当逻辑门；当它们以特定的管道、平台以及像板栗仔（Goombas）或刺刺（Spinies）这样的敌人模式排列时，可以模拟图灵机的行为。因此，判断马里奥是否能到达关卡终点，在功能上等同于判断一个复杂的程序是否会停止运行。
为什么这对人工智能和计算的未来至关重要
这一发现不仅仅是游戏玩家的一个趣闻；它深刻地提醒了我们计算的根本极限。随着我们不断推向人工智能和自动推理的边界，我们必须认识到，某些逻辑结构本质上是任何算法都无法触及的，无论拥有多少处理能力或内存。
通过证明一个看似简单的环境可以承载不可判定问题，MIT Hardness Group 展示了复杂度理论如何应用于交互式、基于规则的系统。这对于我们如何设计复杂软件、验证自动化系统，以及在日益算法化的世界中理解什么是“可计算”的边界，都具有深远的影响。
核心要点
- 不可判定性： 某些超级马里奥关卡现在被归类为 RE-Complete，这意味着没有任何算法能够完美预测玩家是否能完成它们。
- 复杂度转变： 该游戏已从“可解但困难”的 PSPACE 类别跨越到了不可判定领域，这与停机问题相呼应。
- 计算小部件： 研究人员利用游戏机制（管道、敌人和平台）作为“小部件”，构建了模拟通用计算的复杂逻辑门。