Share and Export
Share and Export
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
Preview
DW_P-completeness.pdf
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 |
| Related URLs: | |
| URI: | https://mural.maynoothuniversity.ie/id/eprint/15737 |
| 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
