var cnt = 0; for (var i = -3; i <= 3; ++i) { if (this.neighbours[i].isOn()) { ++cnt; } } if (cnt > 3) { this.turnOn(); } else { this.turnOff(); } On-rate (0-1): Step speed (s/step): Succes rate:

Local majority Rule 184 var cnt = 0; for (var i = -3; i <= 3; ++i) { if (this.neighbours[i].isOn()) { ++cnt; } } if (cnt > 3) { this.turnOn(); } else { this.turnOff(); } if (this.isOn()) { if (this.neighbours[1].isOn()) { this.turnOn(); } else { this.turnOff(); } } else { if (this.neighbours[-1].isOn()) { this.turnOn(); } else { this.turnOff(); } }

Ring of Light

The ring of lights shown above is a one-dimensional cellular automaton. Each light follows a certain transition rule to determine whether to switch on or off at each time step. To make this decission, each light only has local information about the state of its neighbours: it can see the state of its three neighbours on both sides (in addition to its own state). The lights have no global knowledge, like how many lights there are in total and the states of the lights outside of its direct neighbourhood. Also, they have no memory.

Majority Problem

One problem for such a cellular automata is known as the Majority Problem, or Density (Classification) Problem. In this problem, the lights are switched on or off randomly at the start of a run. Then, at each time step, all lights ar updated simultaniously, following a single transition rule. Their task is then, for each possible starting state, to converge to a state where all lights are on when the majority of them was on at the start and where all lights are off when the majority was off. The best currently known rules have a succes rate between 80 and 90%.

How to Try it Yourself

On this page you can try making your own transition rules for the ring of light by typing it in the box next to the ring. The language used is JavaScript and the code you write is inserted into the update function of each light. The sample rules available in the list to the right show you the objects and functions you can use:

this

You can use this to get access to the current light itself.

this.neighbours

A light can access its neighbours, numbered from -3 to 3, through this array. Number 0 is the light itself. For instance, this.neighbours[-2] gives the second light to the left.

isOn()

Check whether a light is currently on. Works on this and on a neighbour.

this.turnOn()/this.turnOff()

Turn on or off the light.

After creating a rule it is time to test it. First, determine some settings:

On-rate

The probability that a light is switched on at the starting state.

Step speed

The number of seconds between two time steps.

Next, use the buttons underneath the rule editor:

Reset

Set all lights to a random starting state.

Step

Execute the transition rule to update the lights once.

Run

Subsequently run the transition rule until the ring has converged to a stable state.

Stop

Halt the current run.

Start test

Perform multiple runs. At the beginning of each run the on-rate is selected randomly and the step speed is set to 0. After each run it is checked whether the ring converged to the right state and the succes rate of the rule over all runs is reported. A run is ended if the ring hasn't converged after 200 steps, which can take quite a bit of time. Therefore it is probably better not to run a test with a non-converging rule (like the example Rule 184).

Stop test

End the current test.