1. 3. What is complexity?
Such is the appeal of the word “complexity” that it comes in
at least four distinct flavors.
• Semantic: What is hard to understand. For 99.99% of
mankind, complex means complicated.
• Epistemological: What is hard to predict. An independent notion altogether: complex chaotic systems can
be simple to understand while complicated mechanisms can be easy to predict.
• Instrumental: What is hard to compute, the province of
theoretical computer science.
• Linguistic: What is hard to describe. Physics has low
descriptive complexity—that is part of its magic.a By
contrast, merely specifying a natural algorithm may
require an arbitrarily large number of variables to
model the diversity present in the system. To capture
this type of complexity is a distinctive feature of natural
1. 4. beyond simulation
Decades of work in programming languages have produced
an advanced theory of abstraction. Ongoing work on reactive
systems is attempting to transfer some of this technology to
biology9. Building on years of progress in automata theory,
temporal logic, and process algebra, the goal has been to
build a modeling framework for biological systems that
integrate the concepts of concurrency, interaction, refinement, encapsulation, modularity, stochasticity, causality,
and so on. With the right specifications in place, the hope is
that established programming language tools, such as type
theory, model checking, abstract interpretation, and the pi-calculus can aid in verifying temporal properties of biosys-tems. The idea is to reach beyond numerical simulation to
analyze the structure and interactions of biological systems.
Such an approach, however, can only be as powerful as
the theory of natural algorithms behind it. To illustrate this
point, consider classifying all possible sequences x, Px, P2x,
P3x, and so on, where x is a vector and P is a fixed stochastic matrix. Simulation, machine learning, and verification
techniques can help, but no genuine understanding of the
process can be achieved without Perron–Frobenius theory.
Likewise, natural algorithms need not only computers but
also a theory. The novelty of the theory will be its reliance on
algorithmic proofs—more on this below.
1. 5. algorithms from nature
If living processes are powered by the “software” of nature,
then natural selection is the ultimate code optimizer. With
time and numbers on their side—billions of years and 1030
living specimens—bacteria have had ample opportunity to
perfect their natural algorithm. No wonder computer scientists are turning to biology for algorithmic insight: neural nets and DNA computing, of course, but also ant colony
optimization3, shortest path algorithms in slime molds2;
a Descriptive complexity is an established subfield of theoretical computer
science and logic. Our usage is a little different, but not different enough to
warrant a change of terminology.
maximal independent sets in fly brain development1, and
so on. Consensus, synchronization, and fault tolerance are
concepts central to both biology and distributed computing15, 17. The trade of ideas promises to be flowing both ways.
This article focuses on the outbound direction: how algorithmic ideas can enrich our understanding of nature.
2. infLuence s Ystems
A bad, fanciful script will make a good stage-setter. One fateful morning, you stumble out of bed and into your kitchen
only to discover, crawling on the floor, a swarm of insects
milling around. Soon your dismay turns to curiosity, as you
watch the critters engage in a peculiar choreography. Each
insect seems to be choosing a set of neighbors (living or inert)
and move either toward or away from them. From what you
can tell, the ants pick the five closest termites; the termites
select the nearest soil pellets; the ladybugs pick the two ants
closest to the powdered sugar that is not in the vicinity of any
termite; and so on. Each insect seems equipped with its own
selection procedure to decide how to pick neighbors based
on their species and the local environment. Once the selection is made, each agent invokes a second procedure, this
time to move to a location determined entirely by the identities and positions of its neighbors. To model this type of
multiagent dynamics, we have introduced influence systems6:
the model is new, but only new to the extent that it unifies
a wide variety of well-studied domain-dependent systems.
Think of influence systems as a brand of networks that perpetually rewire themselves endogenously.
2. 1. Definition and examples
An influence system, is specified by two functions f and G: it is
a discrete-time dynamical system,b x f (x) in (Rd)n, where n
is the number of agents, d is the dimension of the ambient
space (d = 2 in the example above), and each “coordinate” xi
of the state x = (x1, . . . , xn) ∈ (Rd)n is a d-tuple encoding the
location of agent i in Rd. With any state x comes a directed
“communication” graph, G (x), with one node per agent. Each
coordinate function fi of the map f = ( f1, . . . , fn) takes as input
the neighbors of agent i in G (x), together with their locations,
and outputs the new location fi(x) of agent i in Rd. The (action)
function f and (communication) function G are evaluated by
deterministic or randomized algorithms. An influence system is called diffusive if f keeps each agent within the convex
hull of its neighbors. Diffusive systems never escape to infinity and always make consensus (x1 = . . . = xn) a fixed point. The
system is said to be bidirectional if the communication graph
always remains undirected.
While f and G can be arbitrary functions, the philosophy
behind influence systems is to keep f simple so that emergent phenomena can be attributed not so much to the power
of individual agents, but to the flow of information across the
communication network G(x). By distinguishing G from f,
the model also separates the syntactic (who talks to whom?)
b A dynamical system generates an orbit by starting at a point x and iterating
the function f to produce f (x), f 2(x), and so on. The goal is to understand the
geometry of these orbits. We write the phase space Rdn as (Rd)n to emphasize
that the action is on the n agents embedded in d-space.