maths

Life

Life is simple, at least in principle. You start with a grid of cells, each of which can be either alive or dead (on or off). Then for each cell you apply the following rules:

  1. If a living cell has less than two living neighbours, it dies
  2. If a living cell has two or three living neighbours, it survives to the next generation
  3. If a living cell has four or more neighbours, it dies
  4. If a dead cell has exactly three living neighbours, it becomes alive

The results are astonishing. From a randomised starting position, Life rapidly develops a rich, complex and structured behaviour. It’s a little like watching time-lapse movies of bacteria growing in a dish. Patterns sweep through the grid, collide, explode, intermingle, and die out. Static structures arise and remain fixed unless something crashes into them, in which case they often explode into another frenzy of activity. Constantly-moving structures (called “gliders”) soon appear which continue migrating in one direction forever (unless they hit something else).

Hundreds of distinct denizens of the Life universe have been identified and named, including boats, toads, blinkers, spaceships, gliders, loaves, beehives, puffers, scrubbers, revolvers, toasters, ships, mangoes, beacons and washerwomen. Although it looks random, Life is completely deterministic - the same starting pattern will always go through the same steps and end up in the same state, no matter how many times you run the program.

Some starting patterns very quickly die out or produce uninteresting static patterns (or oscillating patterns which cycle through some fixed states forever). Others produce enormously long and varied evolutions which sometimes seem to almost die out, then surge back into life with a coruscating display of explosions and recolonisation. Some rare patterns produce activity that never stops. It’s not intuitively apparent which starting configurations will produce interesting results and which won’t.

The point is that this game wasn’t invented, it was discovered. All of this complexity, richness and variety was lying concealed in the simple ruleset above, waiting to be found. If we ever meet aliens, it’s quite likely they will have discovered Life too, and they will be familiar with the same patterns and Life denizens that we are.

There is another mathematical game called Langton’s Ant which in a similar way produces remarkable complexity from almost the simplest imaginable rules, iterated repeatedly. At times its behaviour seems completely chaotic, and at others it settles down to produce straightforward, stable, repeating patterns that look “designed”.

Stephen Wolfram has written a whole book (A New Kind of Science) about such iterative systems, called cellular automata, in which he explores the space of all possible rulesets and what they produce. The interesting thing is that most cellular automata are not interesting. Pick a set of simple rules for the system’s development, and nine times out of ten you get a cellular automaton that just does nothing, or produces very boring patterns like straight lines or checkerboards.

Once in a while you hit on a set of rules that looks very similar to all the others, but inexplicably produces an enormous flowering of complexity and structure, in the same way that the endless beauty of the Mandelbrot set arises from repeatedly iterating a simple mathematical operation. John Conway experimented with several possible Life-like games before finding this one.

Similarly, the game of Go has almost the simplest rules possible for any game, and yet gives rise to a dizzying universe of tactical and strategic complexity which even master players are far from having fully explored. Yet if you try to alter the rules of Go slightly, you mostly end up with dull games like Tic-Tac-Toe which don’t show the same fascinating emergent complexity.

If you have access to a Life program which lets you alter the rules of the game, such as how a cell’s neighbours affect its life or death, you will find that almost any variation in the parameters results in something quite boring. So we have two surprising results:

  1. The universe can produce surprising (to us) complexity from small sets of simple rules, iterated over a long time. Our brains don’t intuitively see how that complexity can arise.
  2. The exact rules that you choose matter very much, as most of the resulting systems are not complex or long-lived enough to be interesting. Our brains can’t see an intuitive difference between the dull rulesets and the ones that have the “magic”.

This matters because many people look at the enormous variety of patterns and rich structure in the universe around us, and don’t see how it can have emerged without intelligent intervention (a Creator). This is quite natural, and stems from the fact that human brains are optimised for catching gazelles, not doing mathematics.

In fact, once you see the emergent complexity of Life or Langton’s Ant, it’s less puzzling. Electrons, photons and quarks are very simple entities, described by just a few numbers, and follow very simple rules for how to behave. Yet from that simplicity emerges a vast array of complex and highly patterned objects: stars, galaxies, flowers, ants, rainbows, computers, bacteria, the rings of Saturn, and mathematicians.

If the numerical parameters of particle physics were slightly different in various ways, they would lead to a very uninteresting universe: one where stars never form, or all the matter clumps into a cold undifferentiated mass, or you don’t have matter - you get the idea. In fact it’s very difficult to tweak the rules of physics even slightly and get a universe that can produce life, or even Life. Understanding why this should be (and consequently, why we should be) is one of the most important problems in physics.

Without doubt, if the rules of the Game of Physics didn’t have the “magic” that they do, we wouldn’t be here to speculate on them. But that isn’t an explanation, merely an observation (the anthropic principle). It may be that there is an infinite multiplicity of universes in which the rules and parameters take all possible values, and the vast majority of such universes are dull, or empty, or short-lived, or otherwise uninteresting. That being so, we naturally would find ourselves in one of the interesting universes. There might be even more interesting ones out there.

Alternatively, there might be a deep and important reason why things have to be the way they are (or very similar to the way they are) which we don’t know yet. I hope the reason is not that we are God’s screensaver.

The Doomsday algorithm

Pointless skills, number 218: calculating the day of the week for any given date. There are a lot of different ways to do it but I like this method, due to John Conway.

The trick involves knowing what day of the week the last day of February was for the year in question. If you know this day (which Conway calls Doomsday), you can get close to the required date by knowing that Doomsday always recurs on the same dates:

  • January 3 (normal years) or January 4 (leap years)
  • February 28 (normal years) or February 29 (leap years)
  • March 0 (in other words, March the Nth will be N days after Doomsday)
  • For the remaining even months, the same day as the month (April 4, June 6, August 8, etc.)
  • For the remaining odd months, use the mnemonic ‘I work 9-5 at the 7-11’. So the 9th day of the 5th month and vice versa, and the 7th day of the 11th month and vice versa.

So if Doomsday for a particular year is Wednesday, and you want the date of the 9th of April, then since Doomsday always recurs on the 4th of April, the 9th is a Monday.

It is a lot easier to do than to read about, try it with a couple of dates from this year and check it against the calendar.

Part 2 of the trick is how to find Doomsday for a given year. Divide the last two digits of the year by 12 (this is taking you back to tens and units at primary school if you remember that. We had little plastic blocks, anyway that is not germaine to the issue.) So 1938 would be 38 / 12 = 3, remainder 2. Now divide that remainder by 4, so 2 / 4 = 0 (ignore the remainder).

Add up the digits you just worked out ( 3 + 2 + 0 = 5 ). This tells you how far away Doomsday is from the ‘anchor day’ for that century, which for the 20th century was Wednesday. So Wednesday + 5 days = Monday. So Doomsday for 1938 was Monday.

Again that is a lot easier to do, after a little practice, than to try and follow someone telling you about it. What’s that? A hand up at the back? How do you know the anchor day for the century? Well that is easy, for this century it is Tuesday (“Y-Tue-K”), and Wednesday for the last century, when most of us were born (“We-in-dis-day”). For the other centuries lookitup boy lookitup lookitup.

Most of the time the only years you will need to remember is this one and next (Doomsday for 2010 is Sunday, and for 2011, Monday).

This is a good skill and once you have done it a few times it is super easy. Obviously once you know the Doomsday for this year and the next you can just remember it. Who is going to ask you what day something was in 1938 anyway, but if they do and you get it wrong, just claim their memory was addled by the 60s.

So have a go. Amaze your friends, if only with how much spare time you seem to have for memorising pointless things.