MURAL - Maynooth University Research Archive Library

    Small weakly universal Turing machines

    Neary, Turlough and Woods, Damien (2009) Small weakly universal Turing machines. In: Fundamentals of Computation Theory. Springer Verlag, pp. 267-273. ISBN 3-642-03408-X

    Download (429kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We give small universal Turing machines with state-symbol pairs of (6,2), (3,3) and (2,4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines. Despite their small size these machines are efficient polynomial time simulators of Turing machines.

    Item Type: Book Section
    Keywords: Turing Machine; Universal Machine; Universal Turing Machine; Tape Head; Elementary Cellular Automaton;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15730
    Depositing User: Damien Woods
    Date Deposited: 23 Mar 2022 12:47
    Publisher: Springer Verlag
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads