March 1, 2006 - 00:09
Projects:
Here is my attempt to better articulate my argument that agent-based models are representable as CAs (which we already know because a Turing machine can be built in Conway's life... but this shows that it's not very complicated to do for a simple agent-based model like Langton's Ant):
(also, before the argument, the implication I'm going for--that the distinction between CAs and agent-based models is in fact arbitrary, and although this does not mean that the distinction is not a useful concept, we should recognize its subjectivity)
I think that any agent-based model can be represented as a CA. Granted, the rules will have to be more complex, but it is still entirely possible to rewrite agents and their environments as elements of a single CA. For example, Langton's Ant: (and this is just one of several ways to do it--the added complexity can be represented differently in the rules) can be rewritten as a 2D CA in which each cell has 4 states: on, off, on + Ant, off + Ant. Really this is just two booleans variables per cell instead of the one we are used to. The rules are: A cell maintains its state unless a neighboring cell's ant state is on and the ant is "facing" that cell, in which case that cell's ant state is turned on and it's color switched. The issue of the direction the ant is facing could be dealt with by giving each cell a 4-valued variable (valued up, down, left, or right) and setting all of these initially to whatever direction the ant starts out facing (up). The values change as a function of what direction value the cell that previously "was the ant" had. Clearly, the same rules are applied at each iteration to every cell in this system and to nothing but the cells (no agent), and it gives rise to the exact same behavior as Langton's ant. I challenge anyone to find an "agent" in this CA. There is no agent because there is no encapsulated information that is specially treated. Of course, it is more efficient (and easier to understand, probably) to write this system as an agent-based model, but maybe this example can serve as a reminder that there is nothing that agent-based models can do that CAs can't. A more direct and complete proof of this is the fact that a Turing machine can be built in Conway's life.
Comments
Aye.
Submitted by LauraKasakoff on March 1, 2006 - 00:53 Permalink
CAs not so deterministic
Submitted by Kathy Maffei on March 1, 2006 - 10:45 Permalink
Maybe not ..
Submitted by JoshCarp on March 1, 2006 - 11:19 Permalink
rulesets?
Submitted by Kathy Maffei on March 1, 2006 - 13:00 Permalink
I'm not sure I follow
Submitted by Leslie McTavish on March 8, 2006 - 10:27 Permalink
CA's and Agent Based Models
Submitted by PaulGrobstein on March 1, 2006 - 17:51 Permalink
One is the problem of determinacy and indeterminacy. A CA is by definition a deterministic system. An agent-based model may or may not be. Yes, we normally run them on a deterministic machine and so the model implementation is at at best "pseudo-random". As a result any observed behavior can in principle be simulated using a Turing machine (ie a one dimensional CA). But that leaves entirely open two questions. One is whether that particular Turing machine/CA (of the inconceivably large number of them) would ever have come into existence were it not for the prior existence of the agent-based system. The issue here is not entirely one of "subjectivity". If we take our problem to be accounting for what we observe, then we may have to take seriously that agent-based systems existed prior to there being humans to observe them and that they created phenomena that MIGHT have been created by a Turing machine but not within the span of available to create the phenomena we are trying to make sense of.
The other open question has to do with the possibility that agent-based systems (as opposed to our implementations of them) may in FACT be non-deterministic. As we talked through in connection with Voyage to Serendip, there clearly ARE situations where non-deterministic processes can do things that deterministic algorithms cannot. And, as we also talked about, there clearly are in existence things for which there is no deterministic algorithm (Chaitin's Omega).
An additional reason to suspect that there is something in agent-based modelling that is lacking in CA's has to do with Laura's point that causal bidirectionality between different levels of organization may bring into existence new properties that don't exist in "flat" architectures such as CA's (see also Josh). Here again, one may simulate "computable" characteristics of such systems on deterministic, serial machines but there is an open question as to whether all such characteristics are "computable".
The upshot is that a deterministic universe, (digital or otherwise, may have been the favored default view among scientists for several centuries but there is increasing justification for denying it that status any longer. And, along with that, there are increasing reasons to suspect that the reducibility of agent-based models to CA's may also be a passing phase related not only to our intellectual heritage but also to our current technology (the deterministic serial computer).