HackerPapers

arXiv:1412.0784cs.CC

Braid is undecidable

Linus Hamilton

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jun 2015 to Oct 2015. Found in 2 HN submissions from Jun 2015 to Oct 2015. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Surprisingly Turing-Complete 1 comment

    • 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…

      jamesmiller5View on HNParent context

  2. Braid is undecidable (2014) [pdf] 1 comment

    • 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…

      SniffnoyView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.