Langtons Self-Reproducing Loop

Recall our outline of the von Neumann construction, and the subtlety involved in eliminating what at first sight appears to be an inevitable infinite regress. The subtlety arises essentially because we are forced to think of our blueprint data as both (i) consisting of active instructions that must be executed and (ii) as an assemblage of passive information that is merely a part of the overall structure that must be copied and attached to the offspring machine. 

Using this looser criterion of self-reproduction - it is looser since, unlike von Neumann s requirement, it does not force the self-reproducing structure to be capable of universal construction - Langton discovered a relatively simple self-reproducing structure embedded within a two-dimensional CA that we will refer to as Langton s Loop figure 11.4 shows a few snapshots of its 151 time-step reproduction cycle. 

Consider a two-dimensional array of sites, where each site oij 0,1. 7 and evolves according to the four-neighbor von Neumann neighborhood rule defined in table 11.1. Each of the eight states has a specific function to perform. The state 

When a signal reaches a T junction it splits into two copies of itself, one copy traveling along each path. Whenever a 7-0 signal reaches the end of its data path, the path is extended by one site. 

Whenever two 4-0 signals reach the end in succession, a left-hand corner is created. The state cr = 3 is used as an intermediate state while a signal is turning a left comer states cr = 5 and a = 6 separate the offspring loop from its parent. 

---

Table ll.f Transition function table for Langton s self-reproducing loops (taken from table... 

---