Self Reproducing Loops

Langton loops

HAL was vaguely inspired by the self-reproducing loops of Chris Langton.

Langton's loops (1079) were themselves inspired by the "Cellular Automata" work of E. F. Codd (1968) which extended the work of John von Neumann as presented in his "Theory of Self-Reproducing Automata" (1966).

In fact it may be more historically accurate to say that HAL arose out of work on diffusion-limited growth, which itself arose out of a spatialised "genetic programming"-style finite-state machine approach, slightly related to "Avida".

HAL has a large number of differences from Langton's original loops:

Langton's loops were "sheathed". The sheaths kept down the number of states required to implement the automata, but they did this by wasting cellular space in the resulting universe.

As our plans involved etching two-dimensional circuitry onto the 'upper surfaces' of the automata, sheaths would only get in the way and they were rapidly discarded.

Langton's loops were brittle and it was difficult to transmit heritable information from one loop to another by their 'arms' crossing one another - as any such interaction was likely to destroy both the cells involved.

Removing the sheaths of the automata allows significant heritable information to be transferred from a 'father' organism who partly intersects a 'mother' organism who is in the process of giving birth. Although the mother will probably not survive being physically overwritten in this way her offspring may survive the interference. While such crossing over can in no way be mistaken for sex, it is hoped that such dynamics have led to a less brittle environment.

Langton's automata could only execute left-turns. As it was fundamental to our design that the upper surfaces of the automata be space-filling, we introduced right turns to allow our organisms to assume arbitrary connected shapes.

It's fundamental to HAL's design that neighbouring organisms actually touch one another, allowing information to be transferred between the organisms' calculation layers. With this in mind the gap caused by the initial extension of the construction arm in Langton's original loops was eliminated.

Most of HAL's other design considerations involve aspects which were beyond the scope of Langton's original loops - and hopefully have been better covered elsewhere.


Index | HAL | HALcell | Parallel | Hardware | Future | Problem | Limits | Automata | Questions | Links
tim@tt1.org | http://www.alife.co.uk/