MURAL - Maynooth University Research Archive Library

    P-completeness of Cellular Automaton Rule 110

    Neary, Turlough and Woods, Damien (2006) P-completeness of Cellular Automaton Rule 110. Lecture Notes in Computer Science, 4051. pp. 132-143. ISSN 0302-9743

    Download (8MB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We show that the problem of predicting t steps of the 1D cellular automaton Rule 110 is P-complete. The result is found by showing that Rule 110 simulates deterministic Turing machines in polynomial time. As a corollary we find that the small universal Turing machines of Mathew Cook run in polynomial time, this is an exponential improvement on their previously known simulation time overhead.

    Item Type: Article
    Keywords: Cellular Automaton; Turing Machine; Transition Rule; Data Word; Tape Data;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15737
    Depositing User: Damien Woods
    Date Deposited: 28 Mar 2022 11:45
    Journal or Publication Title: Lecture Notes in Computer Science
    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