Cellular automata consist of a lattice of discrete sites, each of which may take on values from a finite set. In classical (synchronous) automata the values of sites evolve in discrete time steps from an initial configuration s0 in accordance with deterministic rules that specify the value of each site in terms of the values of sites in a chosen neighborhood n.
The two-dimensional value graphs outlined for systems above might also be thought of on the model of two-dimensional automata arrays of this type. Much to our surprise, we found that the distribution of values under particular connectives within such arrays can also be generated by simple automata rules.
Consider, for example, an array corresponding to a system value-space with 16 units along each axis, such as that shown in Figure 21. Here, however, we will be concerned only with the lattice of spaces itself. Each cell in such a lattice, with the exception of those at the edges, is surrounded by eight neighbors. We will be concerned in particular with just three of these neighbors, which we will terml 'southeastern' neighbors and which are marked with x's in the sketch below.
| X | ||
| X | X |
A square will be darkened on the next round if and only if exactly one square in its southeast corner is.The series of steps in the evolution of a sixteen-sided array under this simple rule is shown in Figure 33. The surprising fact is that the squares occupied by black in each step in this evolution correspond precisely and in order to the values occupied by 0000, 0001, 0010, ... in our original value space for the Sheffer stroke (Figure 20). This simple cellular automaton, in other words, is 'ticking off' progressive values for NAND or the Sheffer stroke, plotted in value space. By the sixteenth step--for the value 1111--the array evolves into the Sierpinski pattern for tautologies noted in section 5.
Other equally simple automata will generate value spaces for the other connectives outlined above. With precisely the same rule and starting point, but thinking of our values in reverse--from 1111 to 0000 in the case of a 16-sided value space, for example--the value space generated step by step is that of conjunction. The value space for disjunction is generated by beginning in the upper left hand corner with the value 0000 following a second rule, symmetrical to that above:
| X | X | |
| X | ||
A square will be darkened on the next round if and only if exactly one square in its northwest corner is.
This second rule and starting place, thought of as enumerating values in order from 1111 through 0000, generates the value space for NOR or the dagger. A further change in rule and beginning position give us a cellular automaton adequate to implication. A bit of thought shows that indeed these rules must generate the progressive values noted within the lattice of any value space. Consider as a single example the case of 'or', beginning from the upper left corner with the second rule above. The 'or' of the system-value grid, it will be remembered, is what we have termed a 'bitwise or', giving a '1' in any row just in case at least one of its disjuncts has a 1 in that row. Regardless of the number of binary digits in our value representation, it should also be noted, each step along the axis amounts to addition by 1: our values are listed in binary sequence ...000, ...001, ...010, and so forth. What we want to show for the general case, therefore, given axes numbered in binaries of any given number of digits, is that the central cell marked D below will take a binary value of n+1 if and only if precisely one of the cells marked x takes a value of n.
| X | X | |
| X | D | |
| x | |||
| y | A | B | |
| C | D | ||
Either x and y will contain no zeros, therefore, or will share a 0 in the same first position from the right. If neither contains zeros, A occupies the lower right-hand corner of the lattice and there is no place for D; the position exhibited does not form a part of our lattice. In all other cases x and y share a 0 in the same first position from the right. Adding 1 to each of x and y-- moving along the axes from x to x+1 and from y to y+1--will close that 0 with a 1, changing all 1's to its right to 0's in each case. The series of digits represented by x and y will stay the same in all other regards. A bitwise 'or' between x+1 and y+1 will therefore give us an increase of precisely 1 over the value of the bitwise or between x and y: given a value of n for A, D will take a value of n+1.
Consider secondly the case in which it is B that carries the value n, once again using x and y to represent A's axis values:
| x | |||
| y | A | B | |
| C | D | ||
In this case x and y therefore have the form: x: ... 111 y: ... 011
for some number of 1's (perhaps none) to the right of y's 0. It is clear, therefore, that x +1 and y side by side will have the form:
x+1: ... 000 y: ... 011
since addition of 1 to x will have changed some zero to the left of y's to a 1 with all 1's to its right changed to 0's. B's value is that of a bitwise 'or' between these two. But then it is clear that adding 1 to y will result in an increase of precisely 1 for the bitwise compound (x+1 or y+1). Thus if B is the cell with a value of n, D must again take a value of n+1. A symmetrical argument shows that if it is C that is the single northwest cell with value n, D must again take a value of n+1.
For the case of 'or' we have shown that if precisely one of the cells northwest of any D has a value of n, D must itself take a value of n+1. It suffices for the rest of our justification to show that if a cell D has a value n+1, one and only one of its northwest cells must have a value n.
| x | |||
| y | A | B | |
| C | D | ||
We specify that D has a value n+1, generated as the bitwise compound (x or y). Subtraction of 1 from either x or y amounts to changing its rightmost 1 to a 0 and all 0's from there to the right to 1's.
Suppose now that x and y have a rightmost 1 in the same position. In that case subtracting 1 from each will result in a subtraction of 1 from bitwise (x or y), and thus A-- representing (x-1 or y-1)--will have the value n. Subtraction of 1 from just one of these, however, cannot result in n. In that case a rightmost 1 in either x or y will change to a 0, but the other will have a rightmost 1 which masks that change in terms of the bitwise 'or'. What will change in the bitwise 'or' is that all digits to the right of that place (if any) will change from 0 to 1. Since this can only represent a figure equal to or greater than n+1, however, it cannot equal n. Suppose secondly that x has the furthest 1 to the right: that y has a 0 in that position and at all places to the right. Subtracting 1 from x will then change its rightmost 1 to a 0 and all 0's to its right to 1's. Because y has only 0's from that position to the right, the change from bitwise (x or y) to (x-1 or y) will be precisely the same, representing a subtraction of 1, and thus it will be C that has a value of n.
In this case subtracting 1 from only y or from both x and y could not result in n. Subtraction of 1 from n+1 demands that the rightmost 1 in n+1 be changed to a 0, with all 0's to its right (if any) changed to 1's. Given our hypothesis, however, the rightmost 1 in n+1 must correspond to x's rightmost 1. Because y has 0's from that point to the right, subtraction of 1 from y must result in 1's form that point to the right, which will of course also appear in those positions in any bitwise 'or' involving y-1. Thus neither (x or y-1) nor (x-1 nor y-1) will have a 0 in the position of x's rightmost 1; y-1 will mask anything in that position and to the right with '1's. Since a 0 in that position is what a value of n would demand, neither A nor B can have a value of n.
A similar argument can be constructed for the case in which it is y that is assumed to have the furthest 1 to the right.
To sum up: if a single northwest unit has a value of n, a cell will take a value of n+1, and if a cell has a value of n+1 one and only one of its northwest units will have a value of n. Thus a cell will take a value of n+1 if and only if precisely one of its northwest neighbors carries a value of n.
Similar arguments can clearly be constructed in the case of other connectives. What they demonstrate is in the inevitability of the cellular automata rules outlined for value spaces of any chosen dimension. It must be confessed, however, that despite such an explanation we continue to find something magical in the fact that such simple automata rules can generate a value space appropriate to propositional calculus for any chosen approximation.
In all seriousness we offer this cellular automata generation of value spaces simply as a phenomenon worthy of further study. In passing and in a spirit of wild speculation, on the other hand, we might also note a link to the fictional substance 'computronium', introduced in a review of Margolus and Toffoli's CAM-8 by Ivan Amato.9 As envisaged by Amato, computronium would be a 'computing crystal'--a natural substance capable of functioning as a ready-made CPU.
The speculation which the work above invites is that there may be natural processes which follow something akin to the simple cellular automata rules above and which thereby 'grow' units instantiating value spaces appropriate to forms of propositional calculus. If so, there may be natural processes capable of 'growing' something like Amato's computronium. The lattice positions of computronium might be occupied by particular molecules or by molecules in particular states, for example, with the directionality of our rules above corresponding perhaps to magnetic orientation.
