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

    [img]
    Preview
    Download (379kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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: https://doi.org/10.1016/j.tcs.2006.06.002
    Depositing User: Damien Woods
    Date Deposited: 17 Feb 2020 14:42
    Journal or Publication Title: Theoretical Computer Science
    Publisher: Elsevier
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year