MURAL - Maynooth University Research Archive Library



    Small Semi-Weakly Universal Turing Machines


    Woods, Damien and Neary, Turlough (2009) Small Semi-Weakly Universal Turing Machines. Fundamenta Informaticae, 91 (1). pp. 179-195. ISSN 0169-2968

    [thumbnail of Woods_SmallSemi_2009.pdf]
    Preview
    Text
    Woods_SmallSemi_2009.pdf

    Download (128kB) | Preview

    Abstract

    We present three small universal Turing machines that have 3 states and 7 symbols, 4 states and 5 symbols, and 2 states and 13 symbols, respectively. These machines are semi-weakly universal which means that on one side of the input they have an infinitely repeated word, and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our machines has only 17 transition rules, making it the smallest known semi-weakly universal Turing machine. Interestingly, two of our machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique.
    Item Type: Article
    Additional Information: Note that the pdf has incorrect page numbers
    Keywords: 4-state; Simulation technique; Transition rule; Universal Turing machine;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 12415
    Identification Number: 10.3233/FI-2009-0039
    Depositing User: Damien Woods
    Date Deposited: 13 Feb 2020 15:56
    Journal or Publication Title: Fundamenta Informaticae
    Publisher: IOS Press
    Refereed: Yes
    Related URLs:
    URI: https://mu.eprints-hosting.org/id/eprint/12415
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads