按年被提到
20142015 · 4 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:1412.0784 · cs.CC

Braid is undecidable

Linus Hamilton · 2014
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2015-06-02 · 最近 2015-10-02
4不同的人
2活跃月份
3讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Braid is a 2008 puzzle game centered around the ability to reverse time. We show that Braid can simulate an arbitrary computation. Our construction makes no use of Braid's unique time mechanics, and therefore may apply to many other video games. We also show that a plausible "bounded" variant of Braid lies within 2-EXPSPACE. Our proof relies on a technical lemma about Turing machines which may be of independent interest. Namely, define a braidlike Turing machine to be a Turing machine that, when it writes to the tape, deletes all data on the tape to the right of the head. We prove that deciding the behavior of such a machine lies in EXPSPACE.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论Sniffnoy · 2015-06

“A note -- if you're linking to arXiv, it's better to link to the abstract (http://arxiv.org/abs/1412.0784) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Than…”

Braid is undecidable (2014) [pdf]原评论 ↗
评论jamesmiller5 · 2015-10

“If you didn't catch it in the article, it links to a proof of Braid the game's undecidability without use of it's time mechanics. http://arxiv.org/abs/1412.0784 I'd guess Super Mario Maker could be similar if monsters can infinitely spawn, be destroyed and interact with one another, skimming the paper it looks like a requirement.”

Surprisingly Turing-Complete原评论 ↗
被提交为 story · 2 次