MURAL - Maynooth University Research Archive Library



    On the time complexity of 2-tag systems and small universal Turing machines


    Woods, Damien and Neary, Turlough (2006) On the time complexity of 2-tag systems and small universal Turing machines. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE, pp. 439-448. ISBN 0-7695-2720-5

    [img]
    Preview
    Download (169kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines.

    Item Type: Book Section
    Keywords: Turing machines; Computational modeling; Polynomials; Computer science; Computational complexity; Informatics; Mathematics; Educational institutions; Computer simulation; Councils;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15735
    Depositing User: Damien Woods
    Date Deposited: 28 Mar 2022 11:26
    Publisher: IEEE
    Refereed: Yes
    URI:
    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

    Downloads per month over past year

    Origin of downloads