超级马里奥兄弟在数学上是不可能解决的

这是——一个我！复杂性理论中的一个不可判定的问题！

理论上，你可以玩马里奥直到你死，而且永远不会赢。

图片来源：Andrei Armiagov/Shutterstock.com

这里有两个关于数学的事实经常被忽视：首先，有些问题根本无法解决。并不是你个人不够聪明，或者你用了错误的方法来解决这个问题；这个问题、猜想或概念永远不会被任何人解决。其次，高级数学思想的灵感有时可能来自最意想不到的地方。

恰当的例子：最近的一篇论文，目前驻留在 arXiv 预印本服务器上（也就是说，尚未经过同行评审），内容正是关于…… 超级马里奥兄弟 

“在《新超级马里奥兄弟》之后发布的 2D 马里奥游戏中，我们已经证明，除了《超级马里奥奇迹》之外，所有游戏都是不可判定的，”该研究报告指出。来自麻省理工学院计算机科学和人工智能实验室硬度小组的团队。 

即使对于超级马里奥奇迹，“有证据表明它可能是[,]基于事件的存在和无限生成的 Goombas，”他们补充道，“但游戏仍然非常新，需要更多的研究来充分理解游戏的机制，以便对不确定性做出进一步的主张。 ”

那么这在实践中意味着什么呢？基本上，一个不可判定的问题就像它听起来的那样：这是一个不可能正确找到是或否答案的问题。在这种情况下，问题是，作为一名游戏玩家，你真的希望更直接 - 它很简单，“游戏可以被击败吗？ ”

“没有比这更难的了，”麻省理工学院计算机科学教授、该论文的作者之一埃里克·德梅因 (Erik Demaine) 告诉《新科学家》。 “你能到达终点吗？没有算法可以在有限的时间内回答这个问题。 ”

现在，证明这样的事情并不是一件容易的事——毕竟，只是无限地玩游戏，同时有趣地使用研究经费，显然是不可能的。因此，该团队使用了麻省理工学院研究生 Linus Hamilton 十年前在游戏《时空幻境》中使用的技术。

“中心思想是用占据关卡中特定位置的敌人数量来表示时空幻境关卡中每个计数器的值，”论文解释道，“利用这个数字可以任意大即使在有界大小的水平上。 ”

用正式语言来说，该团队正在建立一台计数器机器：一种理论机器，通过操纵一组“计数器”来模拟计算机如何工作。它们非常简单——超级马里奥兄弟中的一个计数器只配备了“向上”、“向下”和“跳跃”指令，仅此而已 – 但非常有用，能够减少将潜在无限 Goombas 的问题转化为更简单的问题：停止问题。

这意味着什么？好吧，启动一个计算机程序并按“开始”——它会终止吗？还是永远继续奔跑？这听起来可能是一个愚蠢的问题，但这就是停止问题——不可判定问题的典型例子。如果一款游戏可以简化为停止问题（就像《时空幻境》和许多《超级马里奥兄弟》游戏一样），那么它也是不可判定的。

“我们的想法是，只有当这个特定的计算终止时，你才能解决这个马里奥关卡，而我们知道没有办法确定这一点，”德梅因告诉《新科学家》，“所以没有办法确定你是否可以解决水平。 ”

换句话说：下次有人说你浪费时间玩愚蠢的视频游戏时，不要担心 - 你可以告诉他们你实际上正在解决复杂性理论领域中的一个无法判定的问题。古姆巴斯和有知觉的恐龙只是装饰门面。

该研究已发布到 arXiv。