A speculative simulation

of a self-repairing NAND gate

A project for Professor Dr Christof Teuscher’s ECE 510 course, “Advanced Embedded In-Silico and In-Materio Computing,” in June 2010. The rules of the game are as follows:

Problem statement

A 12 by 12 grid is occupied by 50 particles, each configurable as a horizontal or vertical wire, or a logic gate. These particles are affected by random motion, but not rotation. The grid has a set number of randomly distributed 'defects', which do not move or have any other function. At each discrete motion step, and with a given probability, a randomly selected particle may experience a 'fault', resulting in its removal from the grid. The particles are aware of their four immediate N, E, S, and W neighbors, and may bind together. There may be other forces or gradients introduced into the simulation, but the system must use only local information and interactions to maintain connections between inputs on the N and S walls of the grid, a logic gate particle, and outputs along the E grid wall.

My solution

It is clearly desirable to have the shortest circuit path possible, as this minimizes the probability of the circuit being affected by faults. Because any circuit path must bridge the N and S walls, the shortest possible circuit path is directly along the E wall, unless blocked by a defect. If a redundant path is desired, the second shortest possible is directly to the W of the shortest, the third directly W of that, etc. Therefore, the particles should accumulate along the E wall.

My model uses no particle binding or gradients, only a universally applied biased stochastic motion and a deterministic cellular automaton update rule, with the particles acting as cells. The model is able to make a circuit in about 250 random single-particle motion steps, and attains a theoretically optimum configuration in about 1200 steps, starting from uniformly distributed random initial conditions. It will tend to repair itself while running, as long as there are enough remaining particles to complete a circuit. The particle movement distribution is biased toward the E to simulate a physical force of some kind (e.g. magnetic or electrostatic) which tends to pull the particles toward the E wall of the circuit.

It’s not an especially realistic simulation of any physical system for several reasons, but it was a fun programming challenge, incorporating several important concepts for scalable distributed systems. More in-depth analysis is embedded as comments in the Haskell source code: [SelfRepair.hs]. But if you don’t want to run the program yourself, here's a video of it in action.

(If that doesn't work, you might need a .webm video extension for your browser. Or, here’s a M4V download instead.)

Notice that I keep switching the [0/1] inputs on the N and S walls, to show that the NAND gate is indeed functioning as specified.