按年被提到
20192019 · 7 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:1904.09828 · cs.AI

Magic: The Gathering is Turing Complete

万智牌是图灵完备的
Alex Churchill, Stella Biderman, Austin Herrick · 2019

证明万智牌的最优对局至少与停机问题一样难

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 28 人首次 2019-04-23 · 最近 2026-06-12
28不同的人
16活跃月份
24讨论串
33被引(OpenAlex)

论文给出把任意图灵机嵌入一局万智牌(Magic: The Gathering)的方法:先手必胜当且仅当该图灵机停机,由此证明真实万智牌中的最优对局至少与停机问题一样难。构造符合真实规则,可用标准的锦标赛合法牌组实现,不依赖随机性或隐藏信息,且双方的所有行动都是被迫的,说明即使双方都没有实质决策,判断胜者也是不可判定的。

HN 为什么提它

HN 上它是「图灵完备出现在意想不到之处」的常用例子,被用来说明某些局面不可判定、一副卡牌也能当计算机,也常被拿来开玩笑。

其他难度 3 / 5约 30 分钟经得起时间
读之前最好知道
1图灵机与停机问题
2可判定性(decidability)
3计算复杂性基础
4万智牌规则基础

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐ljlolel · 2023-12

“This is buried but fascinating: magic the gathering is turing complete”

推荐它,称万智牌是图灵完备的这一点藏得深但很有意思
I Hacked Magic the Gathering: Arena for a 100% Win Rate原评论 ↗
引用Zanni · 2019-05

“or whatever: Magic”

随手贴出万智牌图灵完备的证明 PDF
Magic: The Gathering is Turing Complete原评论 ↗
引用cyberfart · 2019-11

“Related to your comment, here's the paper [0]”

针对对方的评论,贴出万智牌图灵完备的论文
My Kid Lost a Game of 'Magic' to Its Creator But Scored a Piece of Its Art原评论 ↗
引用dodobirdlord · 2020-06

“Sadly, this doesn't work, because the game rules are complex enough to simulate a Turing machine, and as a result some board states are undecidable!”

拿它说明万智牌规则复杂到能模拟图灵机,因此某些局面不可判定
Simplifying Board Games原评论 ↗
引用rcxdude · 2020-06

“And here's the paper on the latest turing machine construction in mtg: Magic”

补充万智牌中最新的图灵机构造论文
How the Magic: The Gathering Color Wheel Explains Humanity原评论 ↗
引用saghm · 2020-06

“Awesome, thanks! I'll definitely check that out”

感谢对方分享万智牌图灵机构造的论文,打算去读
How the Magic: The Gathering Color Wheel Explains Humanity原评论 ↗
看全部 17 条 →
引用YeGoblynQueenne · 2022-06

“And Magic: the Gathering is Turing-Complete [1], but we are not communicating over an implementation of the http protocol in Magic: the Gathering.”

拿万智牌图灵完备作类比,说明能力不等于拿它实现 HTTP 通信
AI Is Ushering in a New Scientific Revolution原评论 ↗
引用mdaniel · 2022-12

“Anyway, I'm certainly glad that Technology Review has stumbled upon this groundbreaking achievement that we've known since 2019: Magic and reported here repeatedly: [LINK]”

调侃媒体才发现这个 2019 年起就已知的成果,并贴出论文
“Magic: The Gathering” is officially the world’s most complex game原评论 ↗
引用trynewideas · 2022-12

“This paper completes the project started by Churchill [4] and continued by Churchill et al. [5] of embedding a universal Turing machine in Magic: The Gathering”

指出它完成了 Churchill 等人在万智牌中嵌入通用图灵机的工作
“Magic: The Gathering” is officially the world’s most complex game原评论 ↗
引用nyrikki · 2023-06

“Note that Magic: The Gathering is Turing Complete”

拿万智牌图灵完备说明图灵完备这一性质多么容易达到
Attention is Turing complete [pdf]原评论 ↗
引用ben_w · 2023-12

“which includes the abstracted rather than physically implemented rules of MtG as used by Churchill, Biderman, & Herrick in their paper”

指出论文用的是抽象化而非实物实现的万智牌规则
I Hacked Magic the Gathering: Arena for a 100% Win Rate原评论 ↗
引用eesmith · 2023-12

“See Magic for the preprint”

给出万智牌图灵完备证明的预印本链接
Apollo 11 vs. USB-C Chargers (2020)原评论 ↗
引用anitil · 2024-09

“is Magic Turing complete? And of course the answer appears to be yes!”

问万智牌是否图灵完备,并以这篇论文回答:是
How to sort your library in exactly 51,271 steps原评论 ↗
引用jfengel · 2024-09

“Similarly, you can arrange your deck to form a Turing-complete computer:”

类比说明排好牌组就能构成一台图灵完备的计算机
Deal infinite damage for 4GRU, as long as the twin primes conjecture is true原评论 ↗
引用FartyMcFarter · 2026-02

“As an example, Magic The Gathering (the card game) is Turing-complete: Magic”

举万智牌图灵完备为例,说明衍生物 token 可充当存储
Show HN: X86CSS – An x86 CPU emulator written in CSS原评论 ↗
引用akoboldfrying · 2026-06

“it turns out that some people showed in 2019 that it's Turing-complete”

指出 2019 年就有人证明万智牌是图灵完备的
MTG Bench: Testing how well LLMs can play magic原评论 ↗
玩笑orf · 2025-01

“Whatever you do with docker can also be done with a Turing machine built using magic the gathering[1].”

We Need to Talk About Docker Hub原评论 ↗
被提交为 story · 3 次