MURAL - Maynooth University Research Archive Library



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


    Neary, Turlough and Woods, Damien and Murphy, Niall and Glaschick, Rainer (2014) Wang's B machines are efficiently universal, as is Hasenjaeger’s small universal electromechanical toy. Journal of Complexity, 30 (5). pp. 634-646. ISSN 0885-064X

    [img]
    Preview
    Download (1MB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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.

    Item Type: Article
    Keywords: Polynomial time; Computational complexity; Small universal Turing machines; Wang’s B machine; Non-erasing Turing machines; Models of computation;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 12409
    Identification Number: https://doi.org/10.1016/j.jco.2014.02.003
    Depositing User: Damien Woods
    Date Deposited: 13 Feb 2020 12:04
    Journal or Publication Title: Journal of Complexity
    Publisher: Elsevier
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year