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
|
Abstract
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 |
| 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)
 |
Item control page |
Downloads
Downloads per month over past year
Altmetric
Altmetric