Editing Rule 110 (section)

===Spaceships in Rule 110===
The function of the universal machine in Rule 110 requires a finite number of localized patterns to be embedded within an infinitely repeating background pattern.  The background pattern is fourteen cells wide and repeats itself exactly every seven iterations.  The pattern is '''00010011011111'''.

Three localized patterns are of particular importance in the Rule 110 universal machine.  They are shown in the image below, surrounded by the repeating background pattern.  The leftmost structure shifts to the right two cells and repeats every three generations.  It comprises the sequence '''0001110111''' surrounded by the background pattern given above, as well as two different evolutions of this sequence.

In the figures, time elapses from top to bottom:  the top line represents the initial state, and each following line the state at the next time.

[[Image:ca110-structures2.png]]

The center structure shifts left eight cells and repeats every thirty generations.  It comprises the sequence '''1001111''' surrounded by the background pattern given above, as well as twenty-nine different evolutions of this sequence.

The rightmost structure remains stationary and repeats every seven generations.  It comprises the sequence '''111''' surrounded by the background pattern given above, as well as five different evolutions of this sequence.

Below is an image showing the first two structures passing through each other without interacting other than by translation (left), and interacting to form the third structure (right).

[[Image:ca110-interaction2.png]]

There are numerous other spaceships in Rule 110, but they do not feature as prominently in the universality proof.