  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.
