科學家證明了萬智牌是圖靈完全的

世界上第一款集換式卡牌遊戲(TCG)《萬智牌》Magic：The Gathering，你可以從19000張牌中組建出自己的牌組，然後與其他玩家對戰。

但今年3月發布的論文，將這個原本就很複雜的遊戲提升了一個檔次。他們表明，存在特定的牌組，它們的效果相當於在遊戲中構造了一台圖靈機。

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

雖然看起來相當簡單，但現代計算機本質上都和圖靈機等價：現代計算機能夠完成的任務，圖靈機也一定能完成；圖靈機本質上做不到的事情，計算機也做不到。

數學家和計算機科學家已經證明，大部分計算機編程語言都是圖靈完全的——可以用這些語言模擬運行抽象的圖靈機。

在過去的幾年裡，我們知道，樂高玩具和遊戲《我的世界》也是圖靈完全的。

現在，科學家又把目光轉向了卡牌遊戲，證明《萬智牌》也是圖靈完全的。

拋去集換式實體卡牌遊戲的特徵，《萬智牌》有點像是規則更複雜、組合更豐富的《爐石傳說》，或者說是更嚴密的《遊戲王》。

研究人員創建的「圖靈機」牌組與普通玩法的不同之處在於，不是由玩家來決定出牌的次序，而是由上一輪打出的卡牌觸發，依次類推。

因此，在這種情況下，圖靈機的程序是一組牌，「紙帶」是桌面上的大量生物僕從，而「機器頭」是讀取牌面並完成操作的玩家。

一旦「萬智牌機」啟動，就只有兩個結果——機器陷入到無限循環中；最終停止，且玩家獲勝。

這項研究由劍橋大學的獨立研究員Alex Churchill經數年努力而成——是完整研究的一部分。但科學家為什麼要和卡牌遊戲過不去呢？

在數理邏輯中，存在所謂的停機問題：

停機問題(halting problem)是邏輯數學中可計算性理論的一個問題。通俗地說，停機問題就是判斷任意一個程序是否能在有限的時間之內結束運行的問題。更本質的說法， 給定一個圖靈機 T，和一個任意語言集合 S, 是否 T 會最終停機於每一個s∈S。其意義相同於可確定語言。顯然任意有限 S 是可判定性的，可列的(countable) S 也是可停機的。

我們通過牌組構造出了虛擬圖靈機，現在就想看看能否提前判斷出，運行「牌組」程序的圖靈機是否能夠停機。

結果，「首次在真實世界的遊戲里顯示，其中的確定的獲勝策略是不可計算的。」他們在論文中解釋道。

既然「圖靈機」牌組只會可以帶來兩個結果：勝利，以及比賽進入死循環(也就是最終會無效重賽)，那麼我們是否能夠拿這套「永不會輸」的牌組來參加正規的比賽呢？

是這樣的，雖然牌組本身是標準的(也就是可以參賽)，但是在數學證明過程中，我們假設排序是完美的(因為我們要證明的是，它具備構造出圖靈機的能力，而不是必然性)，而實際上你只有5萬分之一的幾率，拿到天胡牌序。

「但是，如果真的有人這麼做了，也很有趣不是嗎？」Churchill最後補充說。

點擊這裡，可以閱讀到原始論文。

本文譯自 sciencealert，由譯者 majer 基於創作共用協議(BY-NC)發布。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！