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

DOI10.1016/J.JCO.2014.02.003MaRDI QIDQ2509952zbMATH OpenOpenAlexFDO

Authors Turlough Neary, Damien Woods, Niall Murphy, Rainer Glaschick

Publication date 31 July 2014

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.0053

zbMATH Keywords

computational complexitymodels of computationnon-erasing Turing machinespolynomial timesmall universal Turing machinesWang's B machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Recommendations

• Small Weakly Universal Turing Machines
• Small fast universal Turing machines
• The Complexity of Small Universal Turing Machines
• Four Small Universal Turing Machines
• The Complexity of Small Universal Turing Machines: A Survey

Cites work

• Alan Turing's impact in Münster
• Frontier between decidability and undecidability: A survey
• scientific article; zbMATH DE number 4020483 (Why is no real title available?)
• scientific article; zbMATH DE number 522863 (Why is no real title available?)
• scientific article; zbMATH DE number 3273195 (Why is no real title available?)
• P-completeness of Cellular Automaton Rule 110
• Small deterministic Turing machines
• Solvability of the halting problem for certain classes of Turing machines
• The Complexity of Small Universal Turing Machines: A Survey
• The laterality problem for non-erasing Turing machines on \lbrace 0,1\rbrace is completely solved
• Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines

Cited in

(1)

• An instruction set for reversible Turing machines

This page was built for publication: Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509952)