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.
翻译:Braid 是围绕反向时间能力的2008 年拼图游戏 。 我们显示 Braid 可以模拟任意计算 。 我们的构造没有使用 Braid 独特的时间机械, 因此可能适用于其他游戏 。 我们还显示, Braid 的“ 捆绑” 变体在 2- EXPSPACE 中。 我们的证据依赖于关于图灵 机器的技术性灵敏。 这可能具有独立的兴趣 。 也就是说, 我们定义像 条纹的图灵 机器是图灵 机器, 当它写到磁带时, 它会将磁带上的所有数据删除到头部右侧 。 我们证明决定这种机器行为的方法在 EXPSPACE 中 。