## von Neumann inspired, 5-state CA

For discussion of other cellular automata.
Keiji
Posts: 58
Joined: May 11th, 2010, 5:32 pm

### von Neumann inspired, 5-state CA

I've been working on another new CA, loosely based off von Neumann's 29-state one. Mine however has only 5 states - just over a sixth. It basically works as follows:

State 0: empty
State 1: wire ("wall")
State 2: pulse
State 3: construction node
State 4: logic node

The ruletable (which I'll post later) is rotate4 symmetry, without reflection, compared to no symmetry at all. That way parts can be rotated 90 degrees and still work correctly. Pulses will move forwards along any wire to their right - you can therefore think of the wire as the centre of a two-way road where the pulses "drive" on the left. When a pulse reaches the end of a one-cell-thick wire (as opposed to a right turn), depending on the binary code of pulses in the vicinity, it will construct a piece of the network. Here's a list of the possible combinations (leftmost digit arrives at the end of the wire first):

- 1000 -> grow by 1 cell
- 1010 -> turn left, or if the wire is 3 cells below another, delete 2 cells from both wires (can trigger other behaviour too)
- 1011 -> turn right
- 1001 -> change end to logic node
- 10101 -> delete 2 cells
- 10111 -> unused/makes a mess
- 10011 -> unused/makes a mess

Adding extra ones to the start of any code lengthens the wire by one cell per bit, e.g. 110101 lengthens by 1 cell and then deletes 2 cells, effectively deleting a single cell from the end of the wire. Adding copies of 11 in a row in a certain position after deletion is invoked (10101001111... or 101000001111...) deletes an extra cell per 2 bits. Deletion doesn't work around corners, so to delete a line with lots of corners you need one delete instruction for each straight line; also, deletion of exactly three cells immediately after a corner requires the sequence 110101000010101 (i.e. grow by 1, delete 2, separately delete 2) rather than the more obvious 101010011.

I conjecture that this CA supports a universal constructor of any pattern meeting certain requirements. Mainly, it cannot construct parallel wires with less than two blank cells between them - this is the minimum distance necessary for a pulse to be along down the "inside", and wire cells closer than this are only useful for making compact components, though given the restriction, constructed components do require far more space and a higher clock speed. However, most importantly, constructible patterns should be capable of universal unbounded computation.

I plan to make a six-state version as well, which makes use of the 10111 and 10011 codes to allow construction of any desired combination of states 0 and 1 with a sprinkling of 4 to allow the construction of these compact components.

The logic node, state 4, is used for six fundamental components, which can be combined as necessary for any computation. These six are:
- Splitter (duplicate each pulse; outputs are ahead and right)
- A OR B gate (A-output is ahead, B-output is left turn)
- A AND NOT B gate (same orientation as above)
- Crossover (allow two perpendicular one-way streams to cross)
- Combo crossover (allow a one-way and a two-way stream to cross; or two two-way streams)
- Phase flipper (delays pulse by one generation; necessary because delaying pulses via sending them around "mazes" can only delay by a multiple of 2 generations).

I have already created an AND gate, an XOR gate, and a tape reading mechanism. Unfortunately the tape design I am using at the moment takes a whopping 6x9 rectangle per bit, but I might possibly find a way to reduce this, especially in the six-state version.

The construction arm uses two parallel wires with exactly two blank cells between them (the minimum separation). Instructions are received simultaneously on both wires, and this should allow universal construction.

I'll post the ruletable and a demonstrative .rle when I finish making constructions for all the fundamental components and possibly other things.
Last edited by Keiji on May 18th, 2010, 8:17 am, edited 1 time in total.

This is why signature character limits are pointless.

Keiji
Posts: 58
Joined: May 11th, 2010, 5:32 pm

### Re: von Neumann inspired, 5-state CA

As promised:

.table
.colors
.rle

There are three full constructions in the RLE, for the splitter, 4-crossover and phase flipper. The 2- and 3-crossovers have the same construction as the 4-crossover with a few bits changed. The OR and AND NOT have the same construction as the phase flipper, again with a few bits changed. So construction cost is as follows:

OR/AND NOT/PF: 153
Splitter: 269
n-crossover: 277

There are also, as you can see, lots of primitive constructions, and several nonsense ones just for completeness to show what happens given a certain bit combination.

Finally, there is an AND gate, an XOR gate, a period-24 R/S flipflop, and a tape reader.

I hope someone finds this interesting!

This is why signature character limits are pointless.

Extrementhusiast
Posts: 1796
Joined: June 16th, 2009, 11:24 pm
Location: USA

### Re: von Neumann inspired, 5-state CA

Probably a bit more like a loop rule than von Neumann, but that's OK. I'm thinking of making one myself, based perhaps on Codd.
I Like My Heisenburps! (and others)

ebcube
Posts: 124
Joined: February 27th, 2010, 2:11 pm

### Re: von Neumann inspired, 5-state CA

Code: Select all

``````x = 713, y = 156, rule = qsvn
13\$101.19A\$101.A17.A\$101.A17.A\$101.A2.3A4.A4.A2.A\$101.A2.A.A2.4A3.A2.
A169.AB147.AB\$101.A2.A.A2.5A2.C2.A169.AB147.A\$101.A2.A.A2.4A3.A2.A
169.A68.AB78.A\$101.A2.3A4.A4.D2.A169.A68.AB78.A\$101.A17.A169.A68.A79.
A\$101.A17.A169.A68.A74.6A\$101.A17.A169.D68.A74.A4.A78.D12A\$101.A17.A
238.A74.A4.A90.A13.2A4.A3.2A2.3A12.2A2.3A3.A3.2A12.5B22.2A4.A3.3A.3A.
15.A2.A3.4A3.A12.B3AB23.A2.4A4.A.A3.A\$101.A3.A3.4A3.A2.A166.BA13.A2.
2A119.3A10.A47.D34.A3.5A14.A2.A.3A2.A2.3A13.A2.3A.A.3A2.A12.BA.AB23.A
45.B36.A3.A18.A2.4A3.A2.A.A13.A2.A.A.4A3.A12.B3AB23.A2.4A2.A5.A.A.A\$
101.A3.A3.4A3.A2.A166.BA2.9A2.A2.A50.BA7.A2.A2.A24.5A3.3A.3A23.A47.4A
101.A2.3A4.A4.D2.A20.3B3.3A137.BA2.A7.A2.A2.A25.A24.BA7.A2.A2.A24.A3.
A3.A.A.A25.A29.3A3.2A13.A7.A44.A65.D.D\$101.A17.A19.2BA2B2.A.A5.A2.10A
.A97.A20.A2.A7.A2.A2.A23.5A3.2A2.3A.3A8.BA2.3A2.A2.4A23.3A.3A2.3A.3A
15.9A28.A.A.A3.A13.A7.A30.D7.D5.A65.A48.24A\$101.A17.A19.BA3B2.3A6.A.A
.B2.B.2BA2.A94.5A3.3A.3A.3A4.A2.A2.3A2.A2.A2.A23.A3.A4.A4.A.A.A8.BA2.
3A2.A2.A27.A3.A5.A.A.A15.A36.A.A.A3.A13.A3.2D2.A25.B12.A3.3A65.A48.A
22.A\$101.19A19.5B2.A.A5.A2.10A.A95.A3.A5.A.A3.A6.A2.A2.3A2.A2.A2.A22.
3A.3A3.A2.3A.3A9.A2.AB3.A2.A27.5A5.A.3A15.A36.A2.2A3.A13.A4.D2.D24.5A
.D5A2.A3.A67.A48.A22.A\$140.3B3.3A114.3A.3A2.3A.3A.3A4.A2.A2.AB3.A2.A
67.A48.4A5.4A5.3A2.A\$14.3B3.3A.A.A5.A2.35A194.A3.A3.A5.A.A.A4.A2.A2.A
A41.D27A2.A\$13.2BA2B2.A3.A.A6.A.AB.B.B3.2B.B3.BA2B3.2B.B3.B3.A194.5A
3.3A.3A.3A4.A2.A2.6A2.A2.A51.A10.A52.A4.D95.A2.2D2.A10.A44.2A17.D63.
2A6.A\$13.BA3B2.3A.3A5.A2.35A.A215.A2.A10.A2.A51.A10.A52.A4.A7.D.D85.A
3.D2.D4.D5.A44.A2B69.D10.2A6.A\$13.5B2.A.A3.A8.AB.B.B3.B.B3.B.AB.B3.4B
116.A2.6A2.2A2.2A2.A\$287.A16.A53.D8.D.D63.A97.A4.A2.A116.A7.A2.2A2.2A
2.A\$287.A16.A53.A6.D.A65.A55.D41.A4.D2.A116.A7.A2.2A2.2A2.A\$287.18A
52.BA8.A65.D50.B46.A7.A116.A3.5A6.2A2.A\$357.BA8.A95.3A3.3A11.5A.D3A
38.A2.6A116.A3.A3.A6.2A2.A\$289.D14.D.D51.A8.A94.A.A.A4.A14.2A4.A38.4A
A8.D94.A2.2A2.A16.A5.D165.D18.A\$44.D6.D6.D6.D6.D6.D6.D6.D194.BA14.A
13A147.B21.A8.A\$13.30A.D5A.D5A.D5A.D5A.D5A.D5A.D5A.D6A39.B149.A14.A
340.4A.D6A9.D.D8.A\$42.A6.A6.A6.A6.A6.A6.A6.A7.A39.25A.D5A.D5A.D5A.D5A
.D5A.D5A.D5A76.A14.D343.A7.A16.2A2.A\$38.3A.A6.C6.A6.C6.A6.C6.C6.C7.A
63.A6.A6.A6.A6.A6.A6.A6.A435.A7.A11.3A2.2A2.A\$38.A.A.A2.2D2.A2.2D2.A
2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A7.D59.3A.C6.A6.C6.C6.A6.C6.A6.A
435.A3.2D2.A11.A.A2.2A2.A\$38.A.A.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.
D3.D2.D67.A.A.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A225.A
2.D3.D2.D3.D2.D3.D2.D3.D2.D225.A51.D53.2A4.A3.3A20.3A3.A3.2A13.4B42.A
23.A.A.A2.A.A14.A.A3.A52.A2.4A2.A.A20.A.A.4A3.A12.B3AB36.6A2.D6.2A4.A
4.A8.A\$26.A11.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D342.6A23.
A.A.A2.3A14.3A3.A25.D20A5.3A3.A3.3A20.3A3.A3.3A11.4B37.A2.A.A2.A4.3A
5.D4.A2.10A\$26.A2.6A3.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D
2.A2.2D7.D333.A4.A23.A2.2A4.A14.A5.D45.A65.D.D35.A2.A.A2.A4.A.A10.A2.
7A2.A\$26.A2.A4.A3.A6.C6.C6.C6.A6.C6.A6.A11.A333.A4.A24.3A5.A14.A37.D
A11.A188.5A140.D4.A47.13A20.B12.A3.3A65.A37.A2.3A16.2A2.A11.A\$26.A2.A
37.A10.D14.13A\$26.A2.A258.A3.A60.20A56.5A.D3A83.A6.A2.A3.A67.A37.A4.D
.D18.A\$26.A2.A6.D6.D6.D6.D6.D6.D6.D6.D6.D181.16A2.A60.A18.A22.5A3.3A.
A3.D6.D7.A22.A3.A3.A3.A.A19.A3.A88.A2.2D2.A10.A44.2A17.D37.A.D3A19.A\$
26.A2.A2.10A.D5A.D5A.D5A.D5A.D5A.D5A.D5A.D6A162.14A2.D10.2A2.A60.A10.
2.A4.A6.A6.A6.A6.A6.A6.A6.A6.A7.A162.A12.A2.A2.6A2.2A2.A58.5A.D2A4.A
2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A7.D162.A2.2A2.7A
2.A7.A2.2A2.A58.5A3.A14.A50.A3.A33.3A3.3A11.8A.D2A37.A4.A2.A104.A3.A
3.A13.A\$26.A11.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D170.A2.
2A2.7A2.A7.A2.2A2.A58.A7.A6.D7.A50.A3.A32.A.A.A2.A.A14.A3.A3.A37.A4.D
.B.B3.2B.B3.BA82.A3.A8.A2.A3.A3.A6.A49.A8.5A3.A9.A4.A45.A41.A2.2A2.A.
36.5B4.A.A10.A2B3.2B.B3.B3.A2.A79.A3.7A2.A19.14A34.A2.7A7.D14.A45.A4.
A.D.A56.13A146.5A3.A4.7A2.A\$25.A11.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D
3.D2.D3.D2.D50.3B3.3A.3A8.18A.A80.A3.A8.A4.D27.A34.A2.2A2.A.A17.3A2.A
45.A4.A3.A215.A7.D4.A8.A\$25.A2.6A3.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D
2.A2.2D2.A2.2D2.A2.2D7.D162.A3.A8.A15.2A4.D10.A34.A2.2A2.A.11A7.A.A2.
A45.6A3.A215.A12.A8.A\$25.A2.A4.A3.C6.C6.C6.A6.C6.C6.C6.A11.A162.A2.2A
2.7A15.2A4.A4.4A2.A34.A2.2A2.A.A8.2A7.6A54.A215.23A\$25.A2.A4.A3.A6.A
A.A10.A4.A5.A7.A2.A34.A21.A4.A122.D\$25.A2.A232.A2.2A2.2A2.A.A10.A4.A
5.A7.A2.A34.A8.D.D10.A4.A117.B\$25.A2.A6.D6.D6.D6.D6.D6.D6.D6.D6.D78.D
6.D6.D6.D6.D6.D6.D6.D41.A3.A2.2A2.3A8.D.D4.A5.A3.5A2.A34.A8.A10.D.D4.
A113.8A.D2A\$25.A2.A2.2A106.B121.A3.A2.2A20.A5.A3.A3.A2.A34.A.D7A17.A
116.A3.A3.A28.4A\$25.A2.A2.10A.D5A.D5A.D5A.D5A.D5A.D5A.D5A.D6A41.30A.D
91.3A3.2A2.3A12.5A3.A23.D5A2.A17.2A4.A3.A.A20.A.A3.A3.2A13.3B\$25.A2.A
4.A6.A6.A6.A6.A6.A6.A6.A6.A7.A70.A6.A6.A6.A6.A6.A6.A6.A7.A35.A3.A8.A
10.6A16.A34.A4.D16.6A90.A.A.A3.A2.A14.A7.A31.A18.A2.4A2.A.A20.A.A.4A
3.A12.B3AB\$25.A2.A4.A6.A6.C6.A6.C6.A6.C6.C6.C7.A66.3A.A6.C6.A6.C6.A6.
26.D4.A18.A2.A.3A.3A20.3A.A.3A2.A12.BA.AB\$25.A2.6A2.2D2.A2.2D2.A2.2D
2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A7.D66.A.A.A2.2D2.A2.2D2.A2.2D2.
A2.2D2.A2.2D2.A2.2D2.A2.2D2.A7.D35.A2.2A13.A5.A2.3A16.A26.12A.D2A8.4A
D.A95.A2.2A3.A2.A.A12.5A3.A26.A4.A18.A2.4A4.A22.A.4A3.A12.B3AB\$25.A
11.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D74.A.A.D3.D2.D3.D2.D
3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D43.A2.2A13.A5.A21.A26.A6.A3.A3.A8.A5.A
26.A2.2A2.6A2.A8.A5.A153.5A.D5A2.A71.A\$24.A11.D2.D3.D2.D3.D2.D3.D2.D
3.D2.D3.D2.D3.D2.D3.D2.D63.A11.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D
2.D3.D2.D48.A19.A7.D4.3A2.2A2.A26.A2.2A2.6A2.A6.D.D5.A157.A6.A2.A71.A
\$24.A2.6A3.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D7.D
54.A2.6A3.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D7.D
39.A13.7A12.A.A2.2A2.A26.A2.2A10.D14.A71.AB84.A6.A2.A71.A\$24.A2.A4.A
3.C6.A6.C6.C6.C6.A6.C6.A11.A54.A2.A4.A3.A6.C6.C6.C6.A6.C6.A6.A11.A39.
A13.A5.7A.D2A2.A.A2.2A2.A26.A2.2A19.7A71.A85.A2.2D2.A2.A52.2A17.D\$24.
A2.A4.A3.A6.A6.A6.A6.A6.A6.A6.A11.A54.A2.A4.A3.A6.A6.A6.A6.A6.A6.A6.A
11.A39.A13.A7.A3.A3.A2.A.A2.2A2.A26.A2.17A4.A77.A85.A3.D2.D2.A52.A2B\$
D6A144.2A4.A3.2A2.3A.3A\$24.A2.A6.D6.D6.D6.D6.D6.D6.D6.D6.D61.A2.A6.D
6.D6.D6.D6.D6.D6.D6.D6.D46.A21.A10.A35.5A14.A4.A72.6A43.11A.D2A177.A
5.A2.4A3.A4.A.A.A\$24.A2.A2.2A120.A2.A2.2A105.D21.12A54.A4.14A59.A4.A
46.A2.A3.A3.A165.13A5.A2.A.3A2.A2.3A.3A\$24.A2.A2.10A.D5A.D5A.D5A.D5A.
D5A.D5A.D5A.D6A55.A2.A2.10A.D5A.D5A.D5A.D5A.D5A.D5A.D5A.D6A62.A65.A
17.A59.A4.A24.3A3.3A.3A9.A2.5A3.A165.A11.A5.A2.4A3.A2.A3.A.A\$24.A2.A
4.A6.A6.A6.A6.A6.A6.A6.A6.A7.A55.A2.A4.A6.A6.A6.A6.A6.A6.A6.A6.A7.A
165.A11.A4.3A3.A3.3A.3A.3A\$24.A2.A4.A6.A6.C6.A6.C6.C6.C6.A6.A7.A55.A
2.A4.A6.A6.A6.C6.C6.C6.A6.A6.C7.A38.A8.B4.A2.2A5.A65.A17.A22.A3.A5.A
3.A27.A23.A.A.A2.3A.3A9.A2.A7.A165.A2.7A2.A\$24.A2.6A2.2D2.A2.2D2.A2.
2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A7.D55.A2.6A2.2D2.A2.2D2.A2.2D
2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A7.D38.A4.5B4.A2.A6.A65.D17.A21.
3A.3A2.3A.3A19.4A.D3A23.A2.2A4.A.A11.A2.4A4.A165.10A2.A\$24.A11.D2.D3.
D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D63.A11.D2.D3.D2.D3.D2.D3.D2.D
3.D2.D3.D2.D3.D2.D3.D2.D46.A2.9A2.A2.A6.A83.A22.A3.A5.A.A21.A2.A29.3A
.A.D2A34.A2BA2.3A2.A2.A2.A6.A62.BA2.3A2.A2.4A5.A59.D.D84.D32A34.D21A
14.2A4.A3.3A.A.A25.A2.2A2.A.A14.A\$35.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D
2.D3.D2.D3.D2.D75.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D3.D2.D47.A.
BA2.AB3.A2.A2.A5.BA62.BA2.3A2.A2.A8.A57.D.A118.A6.2A4.A3.3A.3A32.A15.
A2.4A2.A3.A.A25.A2.2A2.A.A3.D10.A\$35.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.
2D2.A2.2D2.A2.2D2.A2.2D7.D66.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D2.A2.2D
2.A2.2D2.A2.2D7.D38.A.BA2.A4.A2.A2.A70.A2.AB3.A2.A8.A59.A65.D44.D7.A
7.A2.4A4.A3.A21.D10.A15.A2.A.3A.3A.3A25.A2.2A2.3A3.A4.4A2.A\$35.A6.C6.
A6.C6.C6.C6.A6.A11.A66.C6.C6.C6.A6.C6.C6.C6.A11.A38.A2BA2.6A2.A2.A70.
A2.A4.A2.A8.A59.A60.B49.A3.5A7.A2.A.3A.3A.3A21.A4.4A2.A15.A2.4A2.A.A
3.A25.A2.2A8.A4.4A2.A\$35.A6.A6.A6.A6.A6.A6.A6.A11.A66.A6.A6.A6.A6.A6.
A6.A6.A11.A38.AB.A.2B5.B.A2.A70.A2.6A2.A7.BA59.D47.17A.D2A23.D18.A3.
A2.A70.A10.A121.A6.A3.A3.A21.B20.A7.A6.3A3.A3.3A.3A21.A7.A2.A56.A8.A
3.A7.A2.A\$263.AB.12A2.A70.A10.A121.A6.5A3.A18.4A.D6A12.A7.A44.A7.A2.A
56.A.D7A3.A3.5A2.A\$40.D6.D6.D6.D6.D6.D6.D3.D81.D6.D6.D6.D6.D6.D6.D3.D
48.A2B7.5B2.A70.12A98.3A3.3A.A.A10.A2.2A2.A7.A21.A7.A12.A3.5A44.A3.5A
2.A56.A12.A3.A3.A2.A\$263.A.B6.2B4.B.A179.A.A.A2.A3.A.A10.A2.2A2.A7.A
2.A.A\$353.A6.D.A97.A2.2A2.A.A3.A10.A2.2A2.6A2.A21.A4.D2.D4.D17.A51.A.
A2.D7.A42.D3A14.D3.A2.2A2.A.5A\$265.D14.D.D69.BA8.A98.3A3.3A3.A10.A2.
2A10.D21.A22.D7.A44.D6.3A2.A3.5A64.A2.2A2.A.A3.A\$265.A12.D.A71.BA8.A
A8.A121.A2.17A27.2A4.A9.A4.A35.B20.A7.A48.D15.A12.A\$264.BA14.A72.A8.A
121.A3.A42.2A4.A7.D.D4.A32.4A.D6A12.A7.A42.B21.A8.D.D.A\$265.A14.A72.A
8.D65.3AB52.A3.A42.A5.D4.D9.A35.A7.A12.A3.5A42.5A.D6A9.A8.A3.A\$264.BA
14.A147.A.A53.5A42.A15.3A2.A35.A7.A12.A3.A3.A46.A7.A9.A.D7A3.A\$264.BA
8.2A12.A\$394.A3.A4.A2.A131.A.A3.A2.A.A2.A35.A4.D2.D4.D17.A44.A3.2D2.A
8.2A12.A\$394.A2.3A3.A2.3A21.D.D105.3A3.A2.A.A2.A35.A22.D7.A44.A4.D2.D