Friday, April 6, 2007
Deus Ex Automatis, Part IV
When I got to this stage in the talk at the emerging technology conference, I glossed over a few of the finer points of mechanics, in hopes that diving right into code would be a better way for most the audience to understand what I was talking about. In retrospect, I think I would have been better served to dig a bit deeper into the mechanics, which is what this article will do.
The grid of cells we looked at in yesterday's segment is incomplete. There are cells of the grid that only have a single neighbor- namely those on the right and left. In fact, the top cell has no neighbors at all. Whereas the rule we outlined needs to look at two neighbors.
There are at least a half-dozen ways around this problem.
Note that I have started with the top cell labeled "A0," I have taken each right-hand neighbor, and when I reached the end, I made the last cell neighborly with the first cell. Think of this as wrapping the grid around on itself.
The cellular automaton now has a new property: diameter.
Which brings us to the all-important question: which kind of grid is simpler- infinite or finite?
Well, who knows? I think the finite grid is simpler, because even though it has a new property (namely, diameter), it's smaller and it's calculable. In addition to that, using this kind of a finite grid causes the cellular automaton we've been discussing here to exhibit interesting properties. If you look again at the previous section, note that even with a diameter of 25, there is a great deal of complexity to the structure.
It may even be universal, in the same sense that Wolfram's Rule 30 and Conway's Game of Life have already been proven to be.
With that last addition to the mechanical overview, we're now going to commit our lengthy explanation into some extraordinarily concise code.
The grid of cells we looked at in yesterday's segment is incomplete. There are cells of the grid that only have a single neighbor- namely those on the right and left. In fact, the top cell has no neighbors at all. Whereas the rule we outlined needs to look at two neighbors.
There are at least a half-dozen ways around this problem.
- Make the grid of cells big enough that on need never reach the edge.
- Simulate an infinite grid by doing lazy evaluation at the edges (more on this later).
- "Wrap" each dimension of the grid, making an end neighbors with its opposite.
- Use a lower-dimensional cellular automaton to specify values on the edges.
- Assign a static value to every cell on the edge of the grid.
- Combine one or more of these approaches.
Note that I have started with the top cell labeled "A0," I have taken each right-hand neighbor, and when I reached the end, I made the last cell neighborly with the first cell. Think of this as wrapping the grid around on itself.The cellular automaton now has a new property: diameter.
Which brings us to the all-important question: which kind of grid is simpler- infinite or finite?
Well, who knows? I think the finite grid is simpler, because even though it has a new property (namely, diameter), it's smaller and it's calculable. In addition to that, using this kind of a finite grid causes the cellular automaton we've been discussing here to exhibit interesting properties. If you look again at the previous section, note that even with a diameter of 25, there is a great deal of complexity to the structure.
It may even be universal, in the same sense that Wolfram's Rule 30 and Conway's Game of Life have already been proven to be.
With that last addition to the mechanical overview, we're now going to commit our lengthy explanation into some extraordinarily concise code.
Labels: cellular automata, deusexautomatis, etech
¶ 5:59 AM
