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 algorithms.

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.