A Concrete View of Rule 110 Computation Export

@article{citeulike:5038089, abstract = {Rule 110 is a cellular automaton that performs repeated simultaneous updates of an infinite row of binary values. The values are updated in the following way: 0s are changed to 1s at all positions where the value to the right is a 1, while 1s are changed to 0s at all positions where the values to the left and right are both 1. Though trivial to define, the behavior exhibited by Rule 110 is surprisingly intricate, and in (Cook, 2004) we showed that it is capable of emulating the activity of a Turing machine by encoding the Turing machine and its tape into a repeating left pattern, a central pattern, and a repeating right pattern, which Rule 110 then acts on. In this paper we provide an explicit compiler for converting a Turing machine into a Rule 110 initial state, and we present a general approach for proving that such constructions will work as intended. The simulation was originally assumed to require exponential time, but surprising results of Neary and Woods (2006) have shown that in fact, only polynomial time is required. We use the methods of Neary and Woods to exhibit a direct simulation of a Turing machine by a tag system in polynomial time.}, archivePrefix = {arXiv}, author = {Cook, Matthew}, citeulike-article-id = {5038089}, citeulike-linkout-0 = {http://arxiv.org/abs/0906.3248v1}, citeulike-linkout-1 = {http://arxiv.org/pdf/0906.3248v1}, comment = {Compile Turing machines, using time polynomial in the size of their initial configuration, into Rule 110 initial states of polynomial size. }, day = {17}, eprint = {0906.3248v1}, keywords = {cellular\_automata, theoretical\_computer\_science, turing\_machines}, month = {Jun}, posted-at = {2009-07-02 01:28:43}, priority = {2}, title = {A Concrete View of Rule 110 Computation}, url = {http://arxiv.org/abs/0906.3248v1}, year = {2009} }

TY - JOUR ID - citeulike:5038089 L3 - citeulike-article-id:5038089 N2 - Rule 110 is a cellular automaton that performs repeated simultaneous updates of an infinite row of binary values. The values are updated in the following way: 0s are changed to 1s at all positions where the value to the right is a 1, while 1s are changed to 0s at all positions where the values to the left and right are both 1. Though trivial to define, the behavior exhibited by Rule 110 is surprisingly intricate, and in (Cook, 2004) we showed that it is capable of emulating the activity of a Turing machine by encoding the Turing machine and its tape into a repeating left pattern, a central pattern, and a repeating right pattern, which Rule 110 then acts on. In this paper we provide an explicit compiler for converting a Turing machine into a Rule 110 initial state, and we present a general approach for proving that such constructions will work as intended. The simulation was originally assumed to require exponential time, but surprising results of Neary and Woods (2006) have shown that in fact, only polynomial time is required. We use the methods of Neary and Woods to exhibit a direct simulation of a Turing machine by a tag system in polynomial time. TI - A Concrete View of Rule 110 Computation KW - cellular_automata KW - theoretical_computer_science KW - turing_machines N1 - Compile Turing machines, using time polynomial in the size of their initial configuration, into Rule 110 initial states of polynomial size. AU - Cook, Matthew PY - 2009/Jun/17/ UR - http://arxiv.org/abs/0906.3248v1 ER -