Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2014 | public
Journal Article

Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy

Abstract

In the 1960s 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.

Additional Information

© 2014 Elsevier Inc. Received 29 September 2013. Accepted 31 January 2014. Available online 14 February 2014. We thank Benedikt Löwe for inviting us to the Isaac Newton Institute for Mathematical Sciences in Cambridge (UK) to participate in the 2012 program "Semantics and Syntax: A Legacy of Alan Turing", and for facilitating this fun project. Finally, we thank David Soloveichik for translating the work of Zykin [17]. Turlough Neary was supported by Swiss National Science Foundation grant 200021-141029. Damien Woods was supported by the USA National Science Foundation under grants 0832824 (The Molecular Programming Project), CCF-1219274, and CF-1162589. Niall Murphy was supported by a PICATA Young Doctors fellowship from CEI Campus Moncloa, UCM-UPM, Madrid, Spain. Rainer Glaschick was supported by the Heinz Nixdorf Museums Forum, Germany.

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023