1. Introduction
Defining emergence in philosophy of science has to fulfill two requisites: first, the concept has to match a great deal of the scientific practice (i.e., the “scientific adequacy requirement”) and cover some of the uses of the term; second, the concept has to be such that not too many things will fall under it (i.e., the “nontriviality requirement”). The latter is obvious since, if “emergent” actually means something, it is regarding issues about novelty, so the concept should not be trivially instantiated.
In the literature, emergence is often addressed through the question of emergence of properties (O’Connor Reference O’Connor1994; Newman Reference Newman1996; Crane Reference Crane, Gillett and Loewer2001; Silberstein Reference Silberstein, Silberstein and Machamer2002; Chalmers Reference Chalmers, Clayton and Davies2006).Footnote 1 Another trend in approaches is the focus on whole-parts relationships. Emergence is often considered to be the problem of understanding properties of the wholes that are irreducible to properties of the parts, which I call combinatorial emergence. In this article I challenge the property approach and the dominant combinatorial understanding of emergence by focusing on the computational definition of emergence. I argue that this approach (focusing on what is an emergent process, rather than on the emergence of properties) fulfills the initial requisites better than the combinatorial/property approach.
2. The Whole-Parts Approach of Emergence and Its Flaws
Traffic jams (Nagel and Rasmussen Reference Nagel, Rasmussen and Brooks1994), fads (Tassier Reference Tassier2004), temperature, and chromosomes at the time of meiosis exhibit a behavior that is not understandable by adding up the considerations of the behavior of their parts. Hence, one considers them emergent behaviors: this emergence is thought to be something proper to the whole and irreducible to the parts. Philosophers such as Bechtel and Richardson (Reference Bechtel, Richardson, Beckermann, Flohr and Kim1992), O’Connor (Reference O’Connor1994), and Silberstein (Reference Silberstein, Silberstein and Machamer2002) addressed the issue of emergence through this scheme of wholes and parts. Dessalles and Phan (Reference Dessalles, Phan, Mathieu, Beaufils and Brandouy2005) see emergence as a drop in complexity, and Wilson (Reference Wilsonforthcoming) sees it as a decrease in the degrees of freedom—contrary to the simple product of the properties of the parts (where there would be additivity of degrees of complexity/degrees of freedom; see also Atay and Jost Reference Atay and Jost2004, 18).
But take Schelling's model of segregation (Reference Schelling1969): in this model, according to their color, agents will arrange themselves into some homogenous clusters. The behavior “join the cluster” is surely not given in the rules of behaviors of the agents, but the clusters are not exactly composed of the agents, since they remain themselves even if some agents are added and some “die” (Gilbert Reference Gilbert2002). So, since the parts are transient relative to the whole, a simple view of emergence as irreducibility of properties of the whole to properties of the parts is misguided.
Wimsatt (Reference Wimsatt1997, Reference Wimsatt2007) defined emergence as the failure of aggregativity; the point is thereby to provide some criteria of aggregativity—this definition addresses the emergence problem the other way around. Wimsatt's criteria of failure of aggregativity are a more sophisticated formalization of what is the case when we say that we cannot reduce properties of the parts to properties of the whole. These criteria are: invariance through intersubstitution of parts; qualitative similarity under addition/withdrawal of parts; invariance regarding decomposition/reaggregation of parts; no cooperative/inhibitory interactions. They are general criteria of invariance; hence they take into account the case of alternating and changing parts within a whole. However, it appears that, except for mass, almost nothing is really aggregative, that is, nothing satisfies all the criteria, for example, of invariance regarding permutation of parts, and so on. This surely is a problem if one wants to capture the meaning of emergence by this perspective—emergence should surely apply to fewer properties than “everything but the mass,” so it would then need a supplementary criterion that is not provided in this analysis. Hence, we are just left with the idea that emergence comes in degrees (see also Bechtel and Richardson Reference Bechtel, Richardson, Beckermann, Flohr and Kim1992). However, in this view the meaning of emergence is quite superfluous; that is, we could talk merely of degrees of aggregativity, but it would make sense only if we already have this criterion that determines how emergence is more than some lack of aggregativity—but our combinatorial analysis will not provide it.
Actually, emergence is supposed to cover several features: unpredictability, novelty, and irreducibility (Klee [Reference Klee1984], O’Connor [Reference O’Connor1994], Humphreys [Reference Humphreys1997], Crane [Reference Crane, Gillett and Loewer2001], Silberstein [Reference Silberstein, Silberstein and Machamer2002], Seager [Reference Seager, Erneling and Johnson2005], and Chalmers [Reference Chalmers, Clayton and Davies2006] largely agree on those features). Irreducibility construed as irreducibility of the properties of wholes regarding properties of parts appears now quite trivial and is too frequent to yield something as “emergence” (see also Bar Yam Reference Bar Yam2004). Concerning novelty, since properties of the wholes are quite always novel regarding the properties of the parts—think of color, or mass, or volume—the problem is to choose which novelty should count as emergent. We are left here with no objective criterion. Novel means most of the time something that has yet to be named (Epstein Reference Epstein[1999] 2007). So this inevitably leads to a widely shared conclusion: if emergence means something, it is restricted to epistemological emergence, that is, relative to a set of theories and of cognitive abilities—apart perhaps from the exceptional case of qualia (O’Connor Reference O’Connor1994; Silberstein and McGeever Reference Silberstein and McGeever1995; Crane Reference Crane, Gillett and Loewer2001; Seager Reference Seager, Erneling and Johnson2005; Chalmers Reference Chalmers, Clayton and Davies2006).
3. The Incompressibility Criterion and Emergent Processes
In the framework of computer simulations some people have been able to define what Mark Bedau (Reference Bedau and Tomberlin1997, 375) called “weak emergence.” According to this criterion, a state of a computation process is weakly emergent iff there is no shorthand to get to it except by running the simulation (this defines an incompressibility criterion of emergence; see Huneman and Humphreys Reference Huneman and Humphreys2008).
Such an approach avoids the subjectivity problem proper to the novelty issue in the previous approach. Hence we would have a major clue about an emergence that would be, if not ontological, at least objective in the same way that conceptual truths in mathematics are objective, independent of our cognitive abilities or epistemic choices. But one could object that our incompressibility criterion is only provisory, since we cannot assert that in a distant future, with enlarged computational abilities, we will still be unable to find analytical shortcuts to get to a final state faster than by simulation. Yet, there is some evidence that this objection fails.
I will extract arguments for the objectivity of computational criteria from Buss, Papadimitriou, and Tsisiklis (Reference Buss, Papadimitriou and Tsisiklis1992). The basic idea is to construe a set of automata whose values change according to a global rule
R. Each automaton transforms the value of its cells according to an input, 0 or 1. The application of the global rule
R is itself dependent on the numbers of each value (q 1, q 2, …) in the set of automata at step n; the input function that will determine the input to all automata at step 
$n+1$ is determined by the global rule. Hence the system is perfectly deterministic.
Input function: If 
$Z_{n}=0,\,\mathrm{then}\,\,F( n+1) =g_{0}( F( n) ) $, and if 
$Z_{n}=1,\,\mathrm{then}\,\,F( n+1) =g_{1}( F( n) ) $, where functions g 0 and g1 take their values in 
$\{ q_{1}\,\ldots \, q_{j}\,\ldots \, q_{n}\} $.
Global rule
R: Z i takes its values in {0, 1}. 
$Z_{i}=M( N_{i}( q_{1}) \,\ldots \,N_{i}( q_{j}) \,\ldots \,N_{i}( q_{n}) ) $, where 
$N_{i}( q_{j}) $ is the number of times value q j is taken at step i (see table 1).
| Step 0 | F 1(0) | F 2(0) | F i(0) | F m(0) | ||||
| Step 1 | F 1(1) | F 2(1) | F i(1) | F m(1) | ||||
| Step k | F 1(k) | F 2(k) | F i(k) | F m(k) | ||||
| Step n | F 1(n) | F 2(n) | F i(n) | F m(n) |
Some global rules are constant free, meaning that they can be enunciated with no reference to some of the actual values q i … of the constants, and others are not. “If there is as much 
$q_{i}$ as 
$q_{j}$, for each value of i and j, 
$Z=0$; else 
$Z=1$” would be an example of a constant-free rule. Buss et al. (Reference Buss, Papadimitriou and Tsisiklis1992) show that if the global rule is non–constant free, then the problem of predicting the state of the system at time T is PSPACE complete; hence the problem cannot be solved in polynomial time (since we assume that no 
$P=NP$Footnote 2 and NP problems are included in PSPACE problems, so that being PSPACE complete entails being such that all NP problems can be translated into that problem, which makes it at least harder than NP complete). The detail of the proof relies on the fact that constant-free global rules are preserved through permutation of the q i, which makes a major difference concerning the pattern of computation of the prediction.
This result perfectly illustrates the fact that some computational devices are objectively incompressible. As the authors write: “If the prediction problem is PSPACE complete, this would mean essentially that the system is not easily predictable, and that there seems to be no better prediction method other than simulation” (Buss et al. Reference Buss, Papadimitriou and Tsisiklis1992, 526). Even with infinite cognitive abilities, there would still be a genuine difference between PSPACE complete prediction problems and others, so the computational definition of emergence is objective.
Weak emergence defined as inaccessibility except by simulation is thereby not something trivial, since, in this framework, all global rules that are constant free are computable in polynomial time, so we have a clear delimitation between some weakly emergent cases and some other cases.
4. Patterns, Order, and Unpredictability
Now, speaking of computational emergence, what precisely is emergent? Humphreys (Reference Humphreys2004, Reference Humphreys2008) talks about emerging patterns in cellular automata; the robust pattern, not computable except by simulation, is then an emergent property in a cellular automaton (CA). But for Dennett (Reference Dennett1991), a pattern is an array of traits that can be easily distinguished from others and recognized; hence it should have a high level of redundancy. A pattern (D-pattern) in this sense is easily deducible from one of its parts (contrary to Humphreys [H-patterns]). So defined, D-patterns seem rather mind-dependent, since Dennett addresses patterns through their recognition, while recognition is linked to our cognitive abilities. Nevertheless, we can specify those redundancy patterns by some purely internal properties, like redundancy, symmetry, or any case of invariance through homeomorphisms: this renders D-patterns mind-independent.
It seems that there will be no way to understand through the computational approach some of the instances of “emergent D-patterns” identified by combinatorial approaches. Basically, if someone draws a D-pattern on an 
$n\times n$ grid, there will be some symmetries, and so forth, so it will need less than n 2 pieces of information to be described. Thereby, the whole is not the aggregation of the parts. But in precisely this case the final pattern seems to contradict the incompressibility criterion, because the symmetries provide shorthand to figure out the total pattern.
Therefore, there are two poles included in the vernacular idea of emergent patterns: order (mostly instantiated by D-patterns) and unpredictability. Segregation clusters, traffic jams, and fads (Nagel and Rasmussen Reference Nagel, Rasmussen and Brooks1994; Gilbert Reference Gilbert2002; and Tassier Reference Tassier2004) reveal some order instead of the pure heterogeneity that we should have expected. They exhibit a clear drop in complexity (e.g., a segregation cluster can be defined in n zones rather than 
$p> > > n$ points). This “order” aspect easily raises the objection that it is epistemological (Dessalles and Phan Reference Dessalles, Phan, Mathieu, Beaufils and Brandouy2005): emergent orders always depend on our epistemic abilities since they are relative to an “expected” complexity.
On the other hand, the “unpredictability” aspect is captured by the incompressibility criterion. Yet there is a similarity between Chaitin's definition of randomness of a random sequence of numbers and the incompressibility criterion of weak emergence, but if this criterion includes randomness, how could weak emergence be reconciled with the “order” aspect? I must now explicate such a similarity.
In a random sequence, the nth digit and its precursors do not give any information regarding the 
$n+1\mathrm{th}\,$ digit, x, and this is of course the intuitive idea of randomness; that is, there is no reason for x to be something rather than something else. Chaitin's idea of the lack of an algorithm that would save us from this step-by-step examination of the sequence formally captures this naïve understanding. Hence x is unpredictable relative to the previous sequence: so if you want to know x you have to read all the 
$n+1$ first digits. On the other hand, the incompressibility criterion of emergence formulates the unpredictability of a given state from the knowledge of the rule and initial state—but of course, not of step 
$n+1$ relative to step n, since this is perfectly deterministic and determined. Briefly said, Kolmogorov/Chaitin randomness requires that there not be a program whose length is significantly shorter than the length of the sequence of states. But there can be a short program—the rules of the CA—that produces an incompressible sequence of states.
The order and the unpredictability aspects seemed to contradict one another, precisely because we implicitly oppose order and randomness here. However, given the aforementioned crucial difference between randomness incompressibility criterion and emergence incompressibility criterion, there is no genuine opposition between a computational criterion of emergence, and order—so that some usual meanings of emergence that connote “order” are not in principle excluded by the computational view. The problem is then to make sense of those connotations within computational emergence.
5. Triviality and the Randomness Exclusion Issue
The two approaches—emergence through order in a combinatorial perspective, and computational emergence—radically diverge on some simple cases. For instance, take the CA defined by 
$C_{0}=1,\, 0,\, 1,\, 0,\,\mathrm{etc.,}\,\, 0$, and the rule: “if at least one neighbor is 1, turn 0 and reciprocally.” The outcome will clearly be the blinking pattern b shown in Figure 1.
Blinking pattern b.
Here, we have a kind of pattern that is not included in each of the cells, but that can only be given through their relations. No descriptions of the parts (black, white, etc.) include the figure of the whole, which clearly exhibits a failure of aggregativity. But there is no incompressibility: to know the state of the CA at step n, I just need to check whether n is odd or even.
The computational notion of emergence does not precisely exclude this pattern as such, but only the CA (rule + initial state) so described. Yet, in some cases we could consider that this precise pattern emerges; for example, in Burke, Furnier, and Prasad's (Reference Burke, Furnier and Prasad2006) study about local norms, we are shown that with simple rules of imitation and fitness enhancement, and some specific initial patterns of distribution, in an agent-based model local norms will emerge. A blinking pattern b′ eventually appears as a final stable state in several configurations when some parameters concerning the initial distribution of signals and the choosing dispositions of the agents are settled.
Thus, according to the computational view it is never the pattern as itself that is emergent (since patterns b and b′ are identical), but emergence is a feature of the whole agent-based simulation process—otherwise there would be no difference between blinking patterns b and b′. (This makes the computational view immune to the triviality proper to the combinatorial view.) As Humphreys (Reference Humphreys2008) points out, emergent patterns are always token patterns (and not types) since other tokens of the same types, for example, a photo of our blinking pattern b′, would not be emergent. What clearly individualizes the pattern token as a token is the CA process in which it is a part.
Such a consideration allows this approach to meet our initial scientific-adequation requisite. Actually, if X incompressibly results from an initial state X 0 in a CA, nothing prevents it to be a random number (“randomness exclusion issue”). In effect: suppose that 
$X=\Sigma _{( i=0,\,\ldots ) }X_{i}$ 10−i is a random number. Since class IV CA are universal Turing machines (see Wolfram Reference Wolfram1984), there must exist a CA noted H with a given rule R and an initial state X 0 whose final state is X. So, given that there are so many CAs whose outcome is random, we can assume there will be plenty of “emergent states” according to the incompressibility criterion that are random sequences. Basically, there is no way to warrant that random patterns are precluded as such to be counted as emergent patterns, since nothing in the computational definition of emergence distinguishes between random and nonrandom patterns. Moreover, fishy properties like P “being in state X, Y, or Z,” where X, Y, and Z are random numbers, are trivially emergent properties of H.
If our definition allows all those random numbers to count as emergent, we will lose its connection with the usual meaning of “emergence,” which seems too high a cost to pay. In this case we should keep calling those patterns “incompressible” and not mess with emergence any more.
But since emergence is a predicate of processes rather than of properties, what is primarily said to be emergent is the process, and only secondarily some properties (states of an emergent process) will be said to be emergent. So fishy properties (like P) that are not individualized outcomes of a process cannot satisfy the predicate “emergent.” And since we individualize the emergent items through the processes, if there exist descriptions allowing us to distinguish various classes of processes, this would involve a principled distinction—in the set of processes fulfilling the incompressibility criterion—between the noninteresting random patterns and other ones that better match the usual meaning of emergence.
This is available through the computational mechanics description language initiated by Crutchfield and Hanson (Crutchfield and Hanson Reference Crutchfield and Hanson1993; Hordijk, Crutchfield, and Mitchell Reference Hordijk, Crutchfield, Mitchell, Toffoli, Biafore and Leao1996; Hanson and Crutchfield Reference Hanson and Crutchfield1997; Crutchfield and Shalizi Reference Crutchfield and Shalizi2001). The basic idea is that we can filter out any CA in such a way that “domains,” “particles,” and “frontiers” will naturally appear. Processes in the CA can then be described as interactions between particles, openings, and collisions of domains, and so forth. As some authors write:
The early empirical categorization of space-time patterns into four “classes” [reference to Wolfram]—loosely based on an analogy with those found in continuous state dynamical systems—has resisted numerous attempts at formalization. In many CA, it is immediately evident that the system self-organizes into some type of emergent pattern. In other CA, the structure or even existence of an emergent pattern is less clear. The question that naturally arises therefore is how to characterize the spatiotemporal patterns that emerge during the CA's evolution. If such a characterization is possible, it can be used as a basis for numerical and analytical tools that discover, analyze, and filter patterns that emerge in CA. (Hanson and Crutchfield Reference Hanson and Crutchfield1997, 170)
In any case, we can define some sets of particles and domains: those sets will be proper to a CA, and defined by their generative structure (Figure 2, 1). “Computational mechanics attempts to discover and characterize the typical patterns occurring in a given CA,” wrote Crutchfield and Hanson (Hanson and Crutchfield Reference Hanson and Crutchfield1997, 171). Delimitating the domain patterns that several CAs use as “building blocks,” and then expressing them as finite automata, amounts to a possible typology of CAs. Hence we will get types of elementary processes, which will allow us to define classes of emergent processes. Thus, as soon as there is a periodic “domain,” we are ensured that it will display some regularities, and this prevents pure randomness; the range of periodic “building blocks” and their types of entanglement in CAs can thereby be the basis of a characterization and typology of incompressible processes that allows us to reliably exclude a large class of purely random patterns (not necessarily all) from what is likely to be emergent according to the mere incompressibility criterion. This amounts to integrate the usual “order” connotation of emergence into computational emergence. Accordingly, Shalizi et al. (Reference Shalizi, Haslinger, Rouquier, Klinkner and Moore2006) designed automatic filters that allow us to characterize processes with no domains and walls, and hence purely chaotic, and whose outcomes are random (e.g., in rule 22 the local sensitivity filter makes no pattern salient; see Figure 2). Computational mechanics hence provides a set of tools—filters—that help us to answer the randomness exclusion problem (Figure 2).
(1) After filtering, the types of particles (shown by Greek letters) and their interactions appear in a CA, whose final pattern seems to result from those “mechanics” (from Crutchfield and Hanson Reference Crutchfield and Hanson1993). (2) A CA (rule 22, random initial configuration) (a) without and (b) with automatic “local sensitivity” filtering—then displaying no real domains and thereby appears chaotic (from Shalizi et al. Reference Shalizi, Haslinger, Rouquier, Klinkner and Moore2006).
In the right column of Table 2, labeled B.2, we get an objective, non epistemological meaning of emergence in CA (at least) that fulfills the nontriviality requirement and that is able to confront correctly the usual meaning of “emergence” (see also Huneman Reference Huneman2008 for biology).
| Class: Computational Incompressibility | |||
|---|---|---|---|
| Emergence of Properties: | |||
| Kind | A. Fishy properties (disjunctive, etc.) | B. Emergent processes | |
| Species | B.1. Random patterns | B.2. “Interesting” patterns (specific subclasses characterized by proper particles-domains geography, measurable in complexity) | |
6. Agent-Based Models and the Triviality Issue
Let's now widen the scope of computational emergence by considering simulations other than CAs. Epstein concludes his (Reference Epstein[1999] 2007) investigation with a critique of the popular use of “emergence” in the discourse of people doing social simulations. His argument holds against a naïve version of the part-whole approach of emergence. Concerning social agent–based modeling, the dilemma he displays goes against any formulation of weak emergence. He formulates a comparison with the bee/beehive structure. “Typical of classical emergentism would be the claim: No description of the individual bee can ever explain the emergent phenomenon of the hive. … The mischievous piece of the formulation is the phrase ‘description of the individual bee.' … Does ‘the bee's' description not include its rules for interacting with other bees? … My ‘rules of social interaction' are, in part, what make me me. And, likewise, the bee's interaction rules are what make it a bee—and not a lump. When (as a designer of agent objects) you get these rules right—when you get ‘the individual bee' right—you get the hive, too. … Unless the theoretical (model) bees generate the hive when you put a bunch of them together, you haven’t described ‘the bee' adequately. Thus, contrary to the opening emergentist claim, it is precisely the adequate description of ‘the individual bee' that explains the hive” (Epstein Reference Epstein[1999] 2007, 36–37). So, reciprocally, if you say that the beehive “emerges,” you must say that any outcome of a complete description of a set of entities is emergent.
Basically, Epstein argues against emergentists that either
A. There is no emergence since the outcomes of any agent-based model—although they are obviously not aggregative—are always proceeding from the behavior of the agents, so there is no novelty in their so-called emergent pattern compared to the ensemble of all the behaviors and their consequences (regarding to what this final state could count as novel since there is no other collective outcome expected?); or
B. Everything is emergent, since “to emerge from the initial rules and configurations” in an agent-based model means to be “generated,” which amounts to proceeding from the activation of the rules of all the agents, and this is the case of any final state in any agent-based model.
The trouble here is what “deduction” means: to “deduce” the final state of a set of agents, according to Epstein, is only to let all those agents act according to their rules. But “deducibility” in this sense is taken for granted by everybody, since the very definition of a computer simulation implies that all the agents behave according to their rules, so the final state can always be said to be deduced from the initial conditions. Yet, defending an idea of computational emergence that should contrast with deducibility, one will highlight another sense of deduction (noted deduction*), namely, the deduction of one final global state of the system from previous global states: the incompressibility criterion means precisely that there is no possibility of such a deduction*. Using the work of Buss et al. (Reference Buss, Papadimitriou and Tsisiklis1992), we just saw (in Section 3) that such cases in general exist.
So all states are trivially deducible, and therefore, in agreement with Epstein's claim A, that there is no emergence if emergence means the opposite of deducibility. But emergence computationally understood excludes only deducibility*. In essence, Epstein argues: either 
$\mathrm{emergent}\,=\mathrm{generated}\,=\mathrm{deducib}\,\mathrm{le}\,$, or emergent is opposed to deducible; because everything is generated in agent-based models, emergence is either trivial or impossible. But since “emergent” is indeed only opposed to “deducible*,” which is a subset of “deducible,” the alternative fails. It is possible that some phenomena might be 
$\mathrm{deduced}\,=\mathrm{generated}\,$, but not deducible*, and are thereby emergent; indeed it is the case of many agent-based models encountered up to now—fashion cycles (Tassier Reference Tassier2004), traffic jams (Rasmussen and Nagel Reference Nagel, Rasmussen and Brooks1994), and local norms (Burke et al. Reference Burke, Furnier and Prasad2006). Thus, emergence in the sense of the incompressibility criterion can be applied in agent-based modeling.
Reciprocally, if “emergent” were a trivial category, all that in agent-based models is deducible would be not-deducible*; but this is false. Suppose, for instance, that we have an initial blinking distribution, and a rule that states “do the opposite of what your immediate horizontal neighbors do (and in case they have between them opposite behaviors, don’t move).” It is clearly the previous case of blinking pattern b (Figure 1)—and so there exists a shorthand to compute the state of the system at n, which makes this state deducible*. Thereby, emergence in ABM—deducibility with no deducibility*—is not trivial.
7. Conclusion
The computational notion of emergence, embedded in the incompressibility criterion and naturally focusing on processes rather than properties, meets the two requirements of nontriviality and of scientific adequacy better than combinatorial views. In both fields of agent-based modeling and cellular automata, one can formally describe a class of emergent processes that is limited and broadly corresponds to our linguistic inclination to talk of emergence in those cases.
