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 中 。

0
下载
关闭预览

相关内容

100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
【深度学习视频分析/多模态学习资源大列表】
专知会员服务
91+阅读 · 2019年10月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
The Measure of Intelligence
Arxiv
6+阅读 · 2019年11月5日
Risk-Aware Active Inverse Reinforcement Learning
Arxiv
7+阅读 · 2019年1月8日
Arxiv
3+阅读 · 2018年10月11日
Mobile big data analysis with machine learning
Arxiv
6+阅读 · 2018年8月2日
Arxiv
3+阅读 · 2018年3月28日
Arxiv
3+阅读 · 2018年1月31日
Arxiv
27+阅读 · 2017年12月6日
VIP会员
相关VIP内容
相关资讯
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关论文
The Measure of Intelligence
Arxiv
6+阅读 · 2019年11月5日
Risk-Aware Active Inverse Reinforcement Learning
Arxiv
7+阅读 · 2019年1月8日
Arxiv
3+阅读 · 2018年10月11日
Mobile big data analysis with machine learning
Arxiv
6+阅读 · 2018年8月2日
Arxiv
3+阅读 · 2018年3月28日
Arxiv
3+阅读 · 2018年1月31日
Arxiv
27+阅读 · 2017年12月6日
Top
微信扫码咨询专知VIP会员