Tuesday, May 07, 2013

The Organisms in Your Truth Table

I've been reading up on cellular automata, which is an interesting field: lots of genuinely worthwhile work combined with lots of enthusiasm outrunning evidence. It's a field where one gets claims like this, about the most famous cellular automaton, Conway's Game of Life (quoted from here, which is a good resource for understanding what cellular automata are):

Upon observing the seemingly unlimited complexity and variety of Life's evolving patterns, it becomes almost impossible to refrain from imagining, along with Conway, that, were the game really to be played on an infinite lattice, there must surely arise true living ‘life-forms’, perhaps themselves evolving into more complex, possibly sentient, ‘organisms’. (Ilachisnki 2001, p. 133)

This makes for fun science fiction, but vague sense of analogy doesn't really get very far, and that's all that's really working here. Cellular automata are nothing more than truth tables linked in series and networks -- usually a single truth table, applied to initial conditions, and then repeatedly re-applied to the results of previous applications. This is very obvious when it comes to what Wolfram calls 'elementary cellular automata'; the rules for these are just three-place truth tables, and the standard 'icon' for each rule is just its truth-table represented as a fragmentary cellular automaton. Thus Rule 110, whose Wolfram icon you can see here, is just the truth table:

TTT : F
TTF : T
TFT : T
TFF : F
FTT : T
FTF : T
FFT : T
FFF : F

The same is true of Conway's Game of Life, although in that case the truth table is a nine-place truth table (one place for each neighboring square, and for the central square at time t-1), so it would be quite large, and I won't put it here.

Conway's rules, simple as they are, are actually just descriptions of this monster truth table. They boil down to:

(1) Whenever [center] takes false, and there are exactly three neighbors that take true, the string is true; else the string is false.
(2) Whenever [center] takes true, and there are two or three neighbors that take true, the string is true; else the string is false.

Now, to be sure, it's a little more complicated than this, since the reiteration of the truth table requires that there by some underlying set of rules that defines how the results of applying the truth table are related to each other. That is, there are implicit rules that define what counts as the new center, and what its neighbors are, and each neighbor is itself a center whose next phase is determined by a truth table (the same truth table, usually, and certainly in Wolfram's elementary automata or Life), with well-defined numbers. In cellular automata these rules are just the underlying principle of the matrix itself, the 'board' for Life, for instance. We could easily change what counts as a 'neighbor' to a square by changing these implicit rules, showing that they are actually quite important, and that the full rule-set for Conway's Game of Life is actually somewhat more extensive than people usually let on. But these implicit rules defining centrality and neighborhood are just the rules for applying the truth tables. I actually wish I could lay out the rules clearly, but this is where I crash into the limits of my mathematical education.

So what we are actually seeing is just the graphic representation of truth tables applied in particular ways to initial conditions, and however much the squares in Life may look like little critters, all Ilachinski's claim boils down to is the claim that if you reiterate truth tables enough according to the implicit rules of Life, starting with the right kind of initial conditions, you will eventually at some point get a result that describes the same logical structure as some kind of animal or even intelligent behavior, if features of that behavior are mapped to truth values. This is pretty trivial. (If we don't read the quotes in Ilachinski's claim as scare quotes, then the suggestion, namely, that the single truth table in Life, applied according to the specific rules governing centrality and neighborhood, suffices for a complete description of some kind of organism, and particularly a sentient organism, is something that we have absolutely no reason to believe, and that no number of little cartoon figures -- which is what the graphic representations are, precisely defined cartoon figures -- could possibly give us reason to believe.)

Cellular automata are still quite fun, though, even if we don't indulge in science fiction.