COMPUTING SCIENCE

# The World in a Spin

# The Blinking Checkerboard Catastrophe

Subjecting the Ising model to all this industrial-strength mathematics—from Onsager's algebra down through the renormalization group—has produced a wealth of useful answers, and yet it seems rather remote from Laplace's simple notion of understanding nature by following the microscopic events as they unfold. Isn't there a more direct way to learn what happens in the lattice? Can't we just program the system into a computer and let it evolve under its own internal rules?

As it happens, the first computer program I ever wrote was a naive attempt to do just that. It was a two-dimensional Ising model implemented in an early version of the spreadsheet Lotus 1-2-3. Each cell of the spreadsheet held an identical evaluation rule, which examined the four surrounding cells and calculated its own next state accordingly. As I gradually cooled the model, I expected to see a magnetized phase spread across the array. What I saw instead was perplexing. Although some areas were magnetized, other regions were taken over by a blinking checkerboard pattern, with alternating up and down spins that flipped at every time step. This pattern should be the least favorable of all configurations. I suspected some elementary bug, such as a missing minus sign, but I wasn't able to track it down.

The problem was quickly diagnosed by more experienced friends: Tommaso Toffoli, Norman Margolus and Gérard Vichniac, who were then all at MIT. Without even looking at my code, they recognized the symptoms. The bug was in fact a fairly interesting one. Imagine you are an *up* spin somewhere in the middle of a blinking-checkerboard area. Your four neighbors are all *down*, and so you are strongly inclined to flip to the *down* state and join them. But each of those neighbors is surrounded by four *up* spins, and so they too flip. Thus all the spins reverse on each step, and the pattern is perpetuated.

Whether or not this bug appears depends on fine details of implementation, in particular on the sequence in which the spins examine their neighbors' states and make decisions about their own next state. My mentors suggested a remedy for my particular situation: The problem would go away if I updated the spreadsheet array in a checkerboard sequence, first all the black squares and then the white. It was an ingenious trick, and it worked like a charm—but what would Laplace think about such stratagems? Does a real ferromagnet require careful sequencing of operations to avoid falling victim to a subtle bug? I find it hard to believe that alternate iron atoms politely take turns updating their spin states. And if nature can get along without such artifice, why should it be needed in a computer simulation of nature?

One answer to this question is that nature has a better computer than we do. In particular, the checkerboard bug might be seen as an artifact of mapping a parallel process onto a sequential machine. If we ran the program on a computer with one processor per spin, the question of how to sequence the updates wouldn't arise at all; the spins would all be updated at once. But I'm not convinced that parallelism solves the problem; rather, it just converts a problem of sequencing into a problem of synchronization. Figuring out what's supposed to happen when all the spins interrogate their neighbors at exactly the same instant they are themselves being interrogated is an even deeper conundrum than the sequential case.

The Monte Carlo method evades problems of sequencing and synchronization by introducing randomness. Each iteration of the algorithm selects a single spin and looks at the effect of reversing it. If flipping the spin would lower the system's overall energy, the change is made. If the energy would be increased, the spin may or may not be flipped; the choice is made randomly, with a probability determined by the change in the Boltzmann weight. Repeating this process many times should produce a statistical sample of spin configurations whose frequencies are proportional to their Boltzmann weights.

Most practitioners look upon the Monte Carlo method as a tool for estimating the partition function, and by this criterion all that matters is that it produces correct answers. But the algorithm seems so physical and mechanistic that it's tempting to view the Monte Carlo process as a simulation of what might actually go on inside an Ising system. Does this view stand up to scrutiny? Laplace might raise an eyebrow at the presence of random numbers in the algorithm, but modern sensibilities seldom take offense at a little randomness. What I find more unsettling is the explicit use of Boltzmann weights to calculate probabilities. I don't want to have to imagine that individual atoms know how to evaluate *e*^{–H/T}. Ideally, the Boltzmann probability distribution would not be built into the model but would emerge from some simpler rule for strictly local interactions of spins.

Among all the computer implementations of the Ising model, my personal favorite is one devised in 1985 by Michael Creutz of Brookhaven National Laboratory. It is strictly deterministic—no random numbers are needed, except perhaps to set the initial conditions—and individual spins know only their energy, not their Boltzmann weight. The model works by giving each spin a kinetic energy as well as the energy associated with nearest-neighbor interactions. The kinetic term acts as a reserve, absorbing excess energy and giving it back when needed. On each update step, each spin is flipped if and only if the corresponding kinetic reserve can accommodate the change in the interaction energy. But even this model is marred by the blemish of the blinking-checkerboard bug, which Creutz avoids by imposing a checkerboard update sequence. Again: Why should such strange and unphysical contortions be necessary?

In a sense, asking a computer program to show us what "actually" happens inside an Ising model is rather silly, because no one will ever build a physical Ising system. The model is an idealization. Everything about it is perfectly discrete and symmetrical. In such a world of mathematical exactitude, the blinking checkerboard may not be a bug at all; it may be a genuine state of the system, which we don't see in real ferromagnets only because there are no perfect ones. Vichniac showed that when Ising spins are allowed to wiggle even slightly, the checkerboard bug is eradicated. Breaking the spatial or the temporal symmetry would surely have the same effect. In other words, maybe what the model needs most is a little imperfection, but I don't think Laplace would be pleased with this thought.

© Brian Hayes

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Technologue**: The Quest for Randomness

**Feature Article**: Simulating Star Formation on a Galactic Scale

**Computing Science**: New Dilemmas for the Prisoner