Navigation auf zora.uzh.ch

Search ZORA

ZORA (Zurich Open Repository and Archive)

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

Neary, Turlough; Woods, Damien; Murphy, Niall; Glaschick, Rainer (2014). Wang’s B machines are efficiently universal, as is Hasenjaeger’s small universal electromechanical toy. Journal of Complexity, 30(5):634-646.

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 indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Neuroinformatics
Dewey Decimal Classification:570 Life sciences; biology
Scopus Subject Areas:Physical Sciences > Algebra and Number Theory
Physical Sciences > Statistics and Probability
Physical Sciences > Numerical Analysis
Physical Sciences > General Mathematics
Physical Sciences > Control and Optimization
Physical Sciences > Applied Mathematics
Language:English
Date:2014
Deposited On:25 Feb 2015 10:08
Last Modified:06 Nov 2024 04:40
Publisher:Elsevier
ISSN:0885-064X
OA Status:Closed
Publisher DOI:https://doi.org/10.1016/j.jco.2014.02.003
Full text not available from this repository.

Metadata Export

Statistics

Citations

Dimensions.ai Metrics
1 citation in Web of Science®
1 citation in Scopus®
Google Scholar™

Altmetrics

Authors, Affiliations, Collaborations

Similar Publications