MURAL - Maynooth University Research Archive Library

    Small fast universal Turing machines

    Neary, Turlough and Woods, Damien (2006) Small fast universal Turing machines. Theoretical Computer Science, 362. pp. 171-195. ISSN 0304-3975

    Download (379kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We present deterministic polynomial time universal Turing machines (UTMs) with state-symbol pairs of (3,11), (5,7), (6,6), (7,5) and (8,4). These are the smallest known UTMs that simulate Turing machines in polynomial time.

    Item Type: Article
    Keywords: Universality; Small universal Turing machine; Computational complexity; Polynomial time;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 12421
    Identification Number:
    Depositing User: Damien Woods
    Date Deposited: 17 Feb 2020 14:42
    Journal or Publication Title: Theoretical Computer Science
    Publisher: Elsevier
    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