Building a computer in Conway's game of life

A new (and better) version of the GOL computer is available here : 

https://github.com/nicolasloizeau/scalable-gol-computer

The purpose of this page is to describe the functioning of a computer built in Conway’s game of life. An in-detail explanation of all the mechanisms and all the components of the computer would be too long to describe here. Only the fundamental principles and main components are explained here. I think this is enough to permit anyone to recreate a similar computer or reuse it's ideas and components for any other project.

The idea here is to illustrate the Turing completeness of game of life with a more impressive example, closer to our computers and easier to program than a basic Turing machine.

1 Bases

The information is carried by glider beams. Their spatial period is 30, their time period is 60. This allows gilder beam crossings. The 4 basic components of the computer are:

period 60 glider gun

90° glider reflector

glider duplicator

a glider eater

The assembly of these components is made using Golly Python scripts.

2 Logic gates

The fact that two orthogonal glider beams can annihilate each other or form an eater if they intersect with the good phase shift is used to make basic logic gates.

This allows us to control a glider beam with another.

0 OR 0

0 OR 1

1 OR 0

1 OR 1

0 AND 0

0 AND 1

1 AND 0

1 AND 1

NOT 0 

NOT 1

3 Logic gates assembly, adaptators

The assembly of logic gates is possible only if the glider beams are in phase and if the gap between the beams is right. While making the components out of multiple logic gates, I used the following conventions: 

- use a 30*30 grid 

- each glider beam has to match the corners of the grid

- main glider beams come from the high left corner.


According to these rules, these glider beams are well in phase.

A series of 3 reflectors called an adaptator is used to shift the phase or the position of a beam. The folder tools contains two Python scripts to make such adaptators. The scripts decamaker.py is used to translate horizontally a well phased beam by a multiple of 30 pixels. The script delamaker.py makes an adaptator of 3 dimensions D1,D2,D3 :

Adaptators are already included at the inputs and outputs of the logic gates from the folder « logic gates ». All their inputs and outputs are well in phase and it is just required to use the decamaker script to assemble them. I made the main components using these logic gates.

4 Adder

The implementation of the logic gates allows the making of any asynchronous logic circuit

A,B : inputs

Cin : carry input

Cout : carry output

S : output

A ripple-carry-adder can be made by juxtaposing n full adders.

5 Arithmetic and logic unit (ALU)

The ALU is composed of some logic functions and a unit which is composed of AND gates that select the result. The inputs are 8 bit each, the instruction is made of 8 independent bits. The instruction flat returns 11111111 if B≠00000000, the instruction sign selects the most significant bit of B. The most significant bit is at the high left corner. The arrow from the select module to the adder represents the increment instruction.

Instruction codes:

+          00000001

or         00000010

and        00000100

xor        00001000

not        00010000

flat       00100000

sign       01000000

increment  10000000

A, B : inputs

I : instruction

S : output

A, B : inputs I : instruction S : output

6 Memory

Memory unit

A memory unit is composed of an RS latch and logic gates AND to manage reading and writing tasks. The memory is an assembly of 64 memory units in 8 lines and 8 columns thus forming an 8x8 bytes memory.

W : write 1 if set=1 0 if reset=1

R1 : read the state of the memory to the S1 output 

R1 : read the state of the memory to the S2 output 

Memory

The 3 modules at the left of the memory are decoders from 3 bit to 8 for decoding addresses. This memory allows us to read data from two addresses a1 and a2 at the same time. The output is made of 16 bit alternated between S1 and S2.


A : data to write, 1 byte 

a0 : address for writing, 3 bits

a1 : address for reading, 3 bits

a2 : address for reading, 3 bits

S : output, 2 bytes 

W : writes A to address a0 if W=1

7 Program

The program is of a static memory form. The big rectangular module is a decoder from 5 bit to 32 which is used to select a line of the program given the input address. 

Each line is made of 21 bits distributed as follow from the high right corner:

- 8 bits for data

- 3 bits for reading address

- 3 bits for reading address

- 3 bits for writing address

The script assembly.py contains more information on computer programming.


A : address of the line to be read: 5 bits

S : output: 21 bits

8 Architecture

Diagram of the computer architecture. Only the main information channels are represented. The module “line” is a 5 bit memory for writing the address of the line which is running (PC). The module “control” is principally a decoder which takes as input an instruction code of 4 bits, decodes it into 16 independent bits and communicates with all the other modules to execute the instruction.

Elements which are not represented in this diagram:

- the control channels from the control module to other modules

- the clock

- the control channels from the clock to the other modules

Color code:

Green: 8bit data bus 

Red: 3bits address

Yellow: 4bits instruction

Pink: 5bits address


9 Detail of a clock cycle

The clock is constituted of 4 loops, formed by glider reflectors in which glider beams rotate. In each loop, a glider duplicator is placed on the glider beam path. This makes it possible to extract the signal from the clock. The 4 loops give rhythm to: the execution of an instruction, the writing in the memory, the incrementation of PC, the writing of PC in the memory.

PC is stored in memory at address 000, however, it is needed to read it all along the execution of an instruction. It is therefore copied into the Line module on each cycle. The following table summarizes a clock cycle.

Generation  Clock loop  Signal edge  Action


0           0           Rising       Reading of an instruction, 

                                     execution of it by the ALU without writing on the memory

590 000     1           Rising       Writing of the ALU’s output on the memory

650 000     1           Falling      End of the writing on the memory

860 000     0           Falling      End of the reading of the instruction

1 100 000   2           Rising       Reading PC from address 000 to the ALU for incrementation 

                                     Copy of PC from 000 to the Line module

1 440 000   3           Rising       Writing of the ALU’s output (PC+1) to the address 000

1 480 000   3           Falling      End of the writing of PC+1 to the address 000

1 600 000   2           Falling      End of reading from the address 000 and end of copying from 000 to the Line module 

                                     At this time, PC+1 is written at 000 and on the module Line

The column “clock loop” gives he position of the clock loop which generates the signal. The index rises from the high left corner. Generation gives the time at which the signal leaves the clock loop. Each cycle is made of two parts: the execution of the instruction (loops 0 and 1) ant the incrementation of PC (loops 2 and 3). Each cycle has a period of 2,003,880 generations.


10 Programming

The Golly Python script assembly.py helps to program the computer. 8 variables can be used: a,b,c,d,e,f,g,h. h is at the address 000 and is used for storing PC.

Instruction    Effect

write a n      Write the number n in to the variable a

goto n         Go to line n

move a b       b=a

jumpif a       Jump the next line if a!=0

print a        Display a

add a b c      c=a+b

or a b c       c=(a or b)

and a b c      c=(a and b)

xor a b c      c=(a xor b)

not a b        b=not(a)

flat a b       B=0 if a=0 ; b=11111111 else

sign a b       Write the most significant bit of a to b 

               (sign of a if a is written in 2’s complement)

increment a    a=a+1


Examples :

Display a modulo b


Line    Instruction    Pseudo-code

0       write a 8      a = 8 

1       write b 3      b = 3 

2       write e 1      d = -b

3       not b d         |

4       add d e d       |

5       add a d a      a = a+d

6       sign a c       if a>=0

7       jumpif c        |

8       goto 5         go to line 5

9       add a b        a a = a+b

10      print a        print a

11      goto 11        end


Display GCD(a,b) (Euclid's algorithm)


Line    Instruction    Pseudo-code

0       write a 8      a = 8 

1       write b 6      b = 6

2       write e 1      c = a modulo b

3       not b d           |

4       add d e d         |

5       add a d a         |

6       sign a f          | 

7       jumpif f          |

8       goto 5            |

9       add a b c         |

10      jumpif c       if c = 0

11      goto 15        go to line 15

12      move b a       a = b

13      move c b       b = c

14      goto 3         go to line 3

15      print b        print b

16      goto 16        end