Search code examples
theorycellular-automata

Wolfram's Rule 34 in XKCD


The hover "joke" in #505 xkcd touts "I call rule 34 on Wolfram's Rule 34".

I know what rule 34 is in Internet terms and I've googled up who Wolfram is but I'm having a hard time figuring out what Wolfram's Rule 34 is.

So what exactly is this "Rule 34"?

Here's the comic: http://xkcd.com/505/.


Solution

  • Wolfram has organized the 256 possible 1-D cellular automata based on nearest neighbors in this way:

    RULES:
    0:        0        0        0
    1:        0        0        1
    2:        0        1        0
    3:        0        1        1
    4:        1        0        0
    5:        1        0        1
    6:        1        1        0
    7:        1        1        1
    

    If you're evaluating a stage in a cellular automaton (CA) that follows rule 2, then whenever a three-bit string matches rule 2's configuration, the center bit becomes (or stays, in this case) true on the next iteration.

    A CA's rules are described as a bitstring. Say it's rule 110 (my favorite). In binary, 110 is 01101110. The digit of least significance is zero. This means that if the cell and its neighbors match rule 0 above, it turns white/negative/0/false/whatever. The second least significant digit is one, so if the cell and its neighbors match rule 1 above, it turns black/positive/1/true/whatever`, etc. etc. until you see that, for rule 110, if a cell and its neighbors match rules 1,2,3,5,6, then the cell turns black. Otherwise, it turns white. A while back, I wrote some JS code to allow me to play around with these unique CA:

    http://lucasoman.com/files/projects/caeditor/caed.php

    As you can see by playing with it, you can randomly toggle any block, which alters every block below it according to the rules. It's kind of a neat way to see the chain reaction caused by aberrations in the process.