Left-to-Right State Listing for one generation of 1-D Life

Consult jonmillen.com/1dlife for the story on 1-D Life.


State Design Summary: 

Five state types: a, b, c, d, e.

The five-cell neighborhood of a cell x is symbolized u, v, x, y, z,
for the purpose of specifying the transitions that rewrite x.

Each cell contains one bit. The 1-D generation rule for the 
center cell x to be rewritten to x' is:

   if x = 1 then x' = 1 if u+v+y+z = 2 or 4, else x' = 0;
   if x = 0 then x' = 1 if u+v+y+z = 2 or 3, else x' = 0.

The rule is implemented with five state types, parametrized by local cell values.
Individual states are symbolized a(u,v), b(u,v), c(u,v), d(u,v,z), e(v,s1,s0)
where s1,s0 is the binary encoding of u+y+z. This is possible since the sum
is a number from 0 to 3. The arguments carry the memory of previous cell values.

There is a cycle of five transitions, summarized below, starting with the head at x.
The transition label (x,x',R) means that the head reads x, writes x', and
goes Right to the next state. Similarly for L.

Here is the five-state cycle, taking the head from x to y after rewriting x to x'
at the end of the cycle. The cycle is repeated left to right to generate one evolution.

	a(u,v) 
	(x,x,R) b(u,v) 
		(y,y,R) c(u,v) 
			(z,z,L) d(u,v,z) 
				(y,y,L) e(v,s1,s0)	where s = u+y+z
					(x,x',R) a(v,x)

AlterTM states are encoded with two consecutive instructions, one
to use when a bit value of 0 is read, and the next if 1 is read.

An instruction has eight bits. The first is the bit value to
be written. The second is the direction to move the head: 1 for Left,
or increasing data address, and 0 for Right, or decreasing data address.

The final six bits identify the next state. A state is identified by
the word address of its Read-0 instruction. Word addresses have seven
bits, but the Read-0 instruction addresses are always even, so the last 0 is
unnecessary to identify the state.

The six-bit state identifier encodes the state stype and parameters. 
The first three or four bits give the state type: 

	 a = 0000, b = 0001, d = 001, e = 010, c = 0110.  

Type a is placed first because state 0 is always the initial state.

Type c is last because d and e have 8 states each, while c has only 4, 
we want simple state type identifiers, and
we don't want gaps in the instruction addresses.

The last two or three bits give the arguments u, v, etc. as needed. 

We can now instantiate the state cycle for all possible values of u,v,x,y,z.

The table below shows each symbolic instruction followed by 
the bit read, its 8 bits, its int value and its
binary state number. The state address doubles this (append 0) for read-0 
and the read-1 instruction is at the next address (append 1).

STATE		READ W D NEXT-STATE	Int	STATE

a(u=0,v=0), 	x=0: 0 0 0001 00	  4	0000 00	0
a(u=0,v=0), 	x=1: 1 0 0001 00	132
a(u=0,v=1), 	x=0: 0 0 0001 01	  5	0000 01
a(u=0,v=1), 	x=1: 1 0 0001 01	133
a(u=1,v=0), 	x=0: 0 0 0001 10	  6	0000 10
a(u=1,v=0), 	x=1: 1 0 0001 10	134
a(u=1,v=1), 	x=0: 0 0 0001 11	  7	0000 11
a(u=1,v=1), 	x=1: 1 0 0001 11	135

b(u=0,v=0), 	y=0: 0 0 0110 00	 24	0001 00 4 
b(u=0,v=0), 	y=1: 1 0 0110 00	152
b(u=0,v=1), 	y=0: 0 0 0110 01	 25	0001 01
b(u=0,v=1), 	y=1: 1 0 0110 01	153
b(u=1,v=0), 	y=0: 0 0 0110 10	 26	0001 10
b(u=1,v=0), 	y=1: 1 0 0110 10	154
b(u=1,v=1), 	y=0: 0 0 0110 11	 27	0001 11
b(u=1,v=1), 	y=1: 1 0 0110 11	155
		
d(u=0,v=0,z=0), y=0: 0 1 010 000	 80	001 000	8
d(u=0,v=0,z=0), y=1: 1 1 010 001  	209
d(u=0,v=0,z=1), y=0: 0 1 010 001   	 81	001 001
d(u=0,v=0,z=1), y=1: 1 1 010 010  	210
d(u=0,v=1,z=0), y=0: 0 1 010 100   	 84	001 010
d(u=0,v=1,z=0), y=1: 1 1 010 101  	213
d(u=0,v=1,z=1), y=0: 0 1 010 101   	 85	001 011
d(u=0,v=1,z=1), y=1: 1 1 010 110  	214

d(u=1,v=0,z=0), y=0: 0 1 010 001   	 81	001 100	12
d(u=1 v=0,z=0), y=1: 1 1 010 010  	210
d(u=1,v=0,z=1), y=0: 0 1 010 010   	 82	001 101 
d(u=1,v=0,z=1), y=1: 1 1 010 011  	211
d(u=1,v=1,z=0), y=0: 0 1 010 101   	 85	001 110
d(u=1 v=1,z=0), y=1: 1 1 010 110  	214
d(u=1,v=1,z=1), y=0: 0 1 010 110   	 86	001 111
d(u=1,v=1,z=1), y=1: 1 1 010 111  	215

e(v=0,s=0), 	x=0: 0 0 0000 00	  0	010 000	16
e(v=0,s=0), 	x=1: 0 0 0000 01	  1
e(v=0,s=1), 	x=0: 0 0 0000 00	  0	010 001
e(v=0,s=1), 	x=1: 0 0 0000 01	  1
e(v=0,s=2), 	x=0: 1 0 0000 00	128	010 010
e(v=0,s=2), 	x=1: 1 0 0000 01	129
e(v=0,s=3), 	x=0: 1 0 0000 00	128	010 011
e(v=0,s=3), 	x=1: 0 0 0000 01	  1

e(v=1,s=0), 	x=0: 0 0 0000 10	  2	010 100	20
e(v=1,s=0), 	x=1: 0 0 0000 11	  3
e(v=1,s=1), 	x=0: 1 0 0000 10	130	010 101
e(v=1,s=1), 	x=1: 1 0 0000 11	131
e(v=1,s=2), 	x=0: 1 0 0000 10	130	010 110
e(v=1,s=2), 	x=1: 0 0 0000 11	  3
e(v=1,s=3), 	x=0: 0 0 0000 10	  2	010 111
e(v=1,s=3), 	x=1: 1 0 0000 11	131		

c(u=0,v=0), 	z=0: 0 1 001 000	 72	0110 00	24
c(u=0,v=0), 	z=1: 1 1 001 001	201
c(u=0,v=1), 	z=0: 0 1 001 010	 74	0110 01
c(u=0,v=1), 	z=1: 1 1 001 011	203
c(u=1,v=0), 	z=0: 0 1 001 100	 76	0110 10
c(u=1,v=0), 	z=1: 1 1 001 101	205
c(u=1,v=1), 	z=0: 0 1 001 110	 78	0110 11
c(u=1,v=1), 	z=1: 1 1 001 111	207