  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.
