Geek
科学家证明了万智牌是图灵完全的
世界上第一款集换式卡牌游戏(TCG)《万智牌》Magic：The Gathering，你可以从19000张牌中组建出自己的牌组，然后与其他玩家对战。
但今年3月发布的论文，将这个原本就很复杂的游戏提升了一个档次。他们表明，存在特定的牌组，它们的效果相当于在游戏中构造了一台图灵机。
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
虽然看起来相当简单，但现代计算机本质上都和图灵机等价：现代计算机能够完成的任务，图灵机也一定能完成；图灵机本质上做不到的事情，计算机也做不到。
数学家和计算机科学家已经证明，大部分计算机编程语言都是图灵完全的——可以用这些语言模拟运行抽象的图灵机。
在过去的几年里，我们知道，乐高玩具和游戏《我的世界》也是图灵完全的。
现在，科学家又把目光转向了卡牌游戏，证明《万智牌》也是图灵完全的。
抛去集换式实体卡牌游戏的特征，《万智牌》有点像是规则更复杂、组合更丰富的《炉石传说》，或者说是更严密的《游戏王》。
研究人员创建的“图灵机”牌组与普通玩法的不同之处在于，不是由玩家来决定出牌的次序，而是由上一轮打出的卡牌触发，依次类推。
因此，在这种情况下，图灵机的程序是一组牌，“纸带”是桌面上的大量生物仆从，而“机器头”是读取牌面并完成操作的玩家。
一旦“万智牌机”启动，就只有两个结果——机器陷入到无限循环中；最终停止，且玩家获胜。
这项研究由剑桥大学的独立研究员Alex Churchill经数年努力而成——是完整研究的一部分。但科学家为什么要和卡牌游戏过不去呢？
在数理逻辑中，存在所谓的停机问题：
停机问题(halting problem)是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。更本质的说法， 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的(countable) S 也是可停机的。
我们通过牌组构造出了虚拟图灵机，现在就想看看能否提前判断出，运行“牌组”程序的图灵机是否能够停机。
结果，“首次在真实世界的游戏里显示，其中的确定的获胜策略是不可计算的。”他们在论文中解释道。
既然“图灵机”牌组只会带来两个结果：胜利，以及比赛进入死循环(也就是最终会无效重赛)，那么我们是否能够拿这套“永不会输”的牌组来参加正规的比赛呢？
是这样的，虽然牌组本身是标准的(也就是可以参赛)，但是在数学证明过程中，我们假设排序是完美的(因为我们要证明的是，它具备构造出图灵机的能力，而不是必然性)，而实际上你只有5万分之一的几率，拿到天胡牌序。
“但是，如果真的有人这么做了，也很有趣不是吗？”Churchill最后补充说。
点击这里，可以阅读到原始论文。
本文译自 sciencealert，由 majer 编辑发布。