Rule 110 is an algorithm for a cellular automaton. The automaton works on of an infinite tape of 1s and 0s. It has a write head that can write to a specific position on the tape, and a read head that reads the position under the write head as well as the positions to either side. The set of three values read determines the value written by the write head according to the following rules:
Values Read | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
Value Written | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
If you notice, the value to write for each set of three values read corresponds to the position of the bits in the binary representation of the number 110. Hence, the name of the rule. Wikipedia has more information here.
If you iterate through the possible rules, the large majority of them are uninteresting. Some don't create any patterns, and a handful create variations on the Sierpinski triangle A few, however, create quite intricate patters. Only Rule 110, however, has shown to be Turing complete. That means that, given a starting state for the tape, in some number of steps you can eventually find every possible pattern. In other words, if you wanted to write a program that took some input, and generated some output – any output – using Rule 110 you would only need to specify the number of iterations to run.