In the 1960's Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger's machine simulates Hao Wang's B machines, which were proved universal by Wang. Unfortunately, Wang's original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger's machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang's B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger's machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger's machine is both small and fast. In another application of our result, we show that Hooper's small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.


翻译:1960年的Gisbert Hasenjaeger用电子机械继电器和非电机制造了图灵机器。 最近, Glaschick 反向设计了其中一台机器的程序,发现它是一个通用图灵机器。 事实上,它的程序只使用四个州和两个符号,使它成为一个非常小型的通用图灵机器。 (机器有三盘磁带和若干其他特性,在将它与其他小型通用机器进行比较时必须记住。 ) Hasenjaeger 的机器模拟Hao Wang's B 机器,这些机器已被王所证明是普遍的。 不幸的是,王的原始模拟算法在模拟图灵机器时受到加速减速的影响。 因此,通过这个模拟,Hasenjaeger的机器在模拟图灵机器时也出现加速减速。 在这项工作中,我们为王的B 机器提供了一个新的高效模拟算法, 显示它们模拟图灵机只是一个多边减速。 作为第二个结果,我们发现Hasenjager的机器在模拟多式机器中也有效地模拟了小型图解机器。 因此,Hasenjaeger的模拟了另一个机器在模拟了另一个图象机的快速的模拟结果。

0
下载
关闭预览

相关内容

导师 Hao Wang(王灏)现为 Rutgers 计算机系助理教授,之前在 MIT 的 CSAIL 实验室从事博士后工作,主要研究方向为统计机器学习和贝叶斯学习,其工作在医疗数据预测、推荐系统等领域有广泛应用,并在Nature Medicine, NIPS, ICML, KDD, AAAI 等国际知名期刊/会议上发表多篇论文。
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
【CMU】机器学习导论课程(Introduction to Machine Learning)
专知会员服务
59+阅读 · 2019年8月26日
RoBERTa中文预训练模型:RoBERTa for Chinese
PaperWeekly
57+阅读 · 2019年9月16日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Universal Transformers
Arxiv
5+阅读 · 2019年3月5日
Arxiv
3+阅读 · 2018年3月28日
Arxiv
3+阅读 · 2017年12月14日
VIP会员
相关VIP内容
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
【CMU】机器学习导论课程(Introduction to Machine Learning)
专知会员服务
59+阅读 · 2019年8月26日
相关资讯
RoBERTa中文预训练模型:RoBERTa for Chinese
PaperWeekly
57+阅读 · 2019年9月16日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员