Introduction: The lost immortals
The book What If?1, by Randall Munroe, compiles a collection of crazy scientific hypotheticals, paired with thorough discussions of what might happen if these situations occurred. Here is an example, called “Lost Immortals”.
If two immortal people were placed on opposite sides of an uninhabited Earth-like planet, how long would it take them to find each other? 100,000 years? 1,000,000 years?
One could imagine many ideas for how the immortals could reunite. For example, they could avoid the interiors of continents by moving to the coastlines. If they are allowed to discuss how to find each other in advance, then they could agree to meet at the planet’s North Pole — assuming that the planet lacks polar bears.
But Munroe provides a solution that is both sophisticated and elegant, quoted below.
If you have no information, walk at random, leaving a trail of stone markers, each one pointing to the next. For every day that you walk, rest for three. Periodically mark the date alongside the cairn. It doesn’t matter how you do this, as long as it’s consistent. You could chisel the number of days into a rock, or lay out rocks to plot the number.
If you come across a trail that’s newer than any you’ve seen before, start following it as fast as you can. If you lose the trail and can’t recover it, resume leaving your own trail.
You don’t have to come across the other player’s current location; you simply have to come across a location where they’ve been. You can still chase one another in circles, but as long as you move more quickly when you’re following a trail than when you’re leaving one, you’ll find each other in a matter of years or decades.
And if your partner isn’t cooperating—perhaps they’re just sitting where they started and waiting for you—then you’ll get to see some neat stuff.
In the previous two modules, we have harnessed the power of randomness to answer to practical questions. Munroe’s approach exemplifies a randomized algorithm, or a method that uses randomness to solve a problem.
In fact, Munroe’s randomized algorithm for Lost Immortals is inspired by nature; he calls his approach “be an ant” because it mimics how ants explore their environment for resources. However, in this module, we will see that this algorithm is also similar to the method of exploration taken by a much smaller organism: our old friend E. coli.
Like other prokaryotes, E. coli is tiny, with a rod-shaped body that is 2µm long and 0.25 to 1µm wide.2 In exploring a vast world with sparse resources, E. coli finds itself in a situation comparable to Munroe’s immortals.
The video below shows a collection of E. coli surrounding a sugar crystal. Think of this video the next time you leave a slice of cake out overnight on the kitchen counter!
The movement of organisms like the bacteria in the above video in response to a chemical stimulus is called chemotaxis. E. coli and other bacteria have evolved to move toward attractants like glucose and electron acceptors and move away from repellents like Ni2+ and Co2+.
In this module, we will delve into chemotaxis and ask a number of questions. How does a simple organism like E. coli sense an attractant or repellent in its environment? How does the bacterium change its internal state accordingly? How can we model the bacterium’s response? And how does the bacterium’s behavior translate into an “algorithm” that it uses to explore its environment?