2014/12/02 by Linus Hamilton, Hamilton, Linus · 2 voices
Computer Science · Mathematics · #Algorithm #Artificial Intelligence in Games #Artificial intelligence #Braid #Braid group #Braid theory #Cellular Automata and Applications #Combinatorics #Computability, Logic, AI Algorithms #Computation #Computer science #DTIME #Description number #Discrete mathematics #EXPTIME #Embedding #Mathematics #NSPACE #Super-recursive algorithm #Theoretical computer science #Time hierarchy theorem #Turing machine #Undecidable problem #Universal Turing machine #cs.CC
paper · pdf · doi:10.48550/arxiv.1412.0784
arxiv created 2014/12/02 · openalex publication_date 2014/12/02 · arxiv updated 2014/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.