GMU:BioArt WS15/Xianzhi Zhang: Difference between revisions

[[File:Sliding block memory Snapshot.png|400px|left|thumb|Sliding block memory snapshot (Hickerson, 1990)]] [[File:Sliding block memory Scheme.png|400px|left|thumb|Sliding block memory schematic (Hickerson, 1990)]]

A sliding block memory pattern was constructed by Hickerson, 1990. It uses several constructions which generate gliders at intervals of 120 generations. This is based on the period 30 Gosper gun. These guns fire salvoes of gliders at a block. The sliding block memory uses a salvo of two gliders to decrement the counter by moving it diagonally one space closer. Three gliders are used to increment it by pushing it further away. An additional glider is sent across the pattern during the decrement. This is deleted by the decrement operation when the block is decremented to zero.

It is possible to construct logic gates such as AND, OR and NOT using gliders. It is possible to build a pattern that acts like a finite state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.

Paul Rendell has implemented a [http://rendell-attic.org/gol/utm/ Universal Turing Machine] in Conway’s Game of Life in 2010. The left picture shows the pattern of it. The right Figure shows the general scheme of this Turing Machine.

The finite state machine part can clearly be seen as the square pattern in the bottom left of the picture. This has an addressing mechanism on the left (state value) and at the bottom (symbol value) and nine memory cells to hold the data table to describe the action for each combination of the internal state and symbol values.

The other item visible is the delay loop for the next state which extends from the centre towards the left top corner underneath the left stack. The next state value is copied from the data read from the finite state machine and sent round this loop to address the finite state machine for the next cycle in conjunction with the symbol popped from one of the stacks.

The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Conway's Game of Life. Also like Life, Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

In an elementary cellular automaton, a one-dimensional pattern of 0s and 1s evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 in the new generation depends on its current value, as well as on those of its two neighbors. The Rule 110 automaton has the following set of rules:

|-

!current pattern

The rightmost structure remains stationary and repeats every seven generations. It comprises the sequence 111 surrounded by the background pattern given above, as well as five different evolutions of this sequence.

Stephen Wolfram, ''A New Kind of Science''<br />