“This is buried but fascinating: magic the gathering is turing complete”
Magic: The Gathering is Turing Complete
证明万智牌的最优对局至少与停机问题一样难
论文给出把任意图灵机嵌入一局万智牌(Magic: The Gathering)的方法:先手必胜当且仅当该图灵机停机,由此证明真实万智牌中的最优对局至少与停机问题一样难。构造符合真实规则,可用标准的锦标赛合法牌组实现,不依赖随机性或隐藏信息,且双方的所有行动都是被迫的,说明即使双方都没有实质决策,判断胜者也是不可判定的。
HN 上它是「图灵完备出现在意想不到之处」的常用例子,被用来说明某些局面不可判定、一副卡牌也能当计算机,也常被拿来开玩笑。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“or whatever: Magic”
“Related to your comment, here's the paper [0]”
“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!”
“And here's the paper on the latest turing machine construction in mtg: Magic”
“Awesome, thanks! I'll definitely check that out”
看全部 17 条 →
“And Magic: the Gathering is Turing-Complete [1], but we are not communicating over an implementation of the http protocol in Magic: the Gathering.”
“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]”
“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”
“Note that Magic: The Gathering is Turing Complete”
“which includes the abstracted rather than physically implemented rules of MtG as used by Churchill, Biderman, & Herrick in their paper”
“See Magic for the preprint”
“is Magic Turing complete? And of course the answer appears to be yes!”
“Similarly, you can arrange your deck to form a Turing-complete computer:”
“As an example, Magic The Gathering (the card game) is Turing-complete: Magic”
“it turns out that some people showed in 2019 that it's Turing-complete”
“Whatever you do with docker can also be done with a Turing machine built using magic the gathering[1].”
- Magic: The Gathering Is Turing Complete ↗lainon · 2019-04-23 · 4 分
- Magic: The Gathering Is Turing Complete ↗headalgorithm · 2019-04-23 · 3 分
- Magic: The Gathering Is Turing Complete ↗Sniffnoy · 2019-04-25 · 3 分