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的模拟了另一个机器在模拟了另一个图象机的快速的模拟结果。