tri-state + lightspeed wire

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

tri-state + lightspeed wire

Post by Keiji » May 13th, 2010, 3:10 pm

I had the idea of making a 3-state CA which behaved like this:
- In any 3x3 block containing only cells of states 0 and one other state a, the centre cell behaves as it would in normal Life, a being "alive".
- In other situations, the rules are yet to be defined.

Now, I've been engineering the yet-to-be-defined rules, with the intention of making a form of lightspeed wire that's about as easy to manipulate as WireWorld. In essence, state 2 is WW's conductor state, state 1 is its electron tail state, and state 0 (blank) doubles up both as the empty space and the electron head state. I've got turning corners working fine now, haven't started working on logic gates or splitters or anything like that yet, but what I have been doing is attempting to make a "electron to glider" converter. After some trial and error, I've got a useful-seeming result in which an electron arriving at the end of a wire takes 15 generations to push a waiting state 1 beehive one cell to the right. If a second electron arrives, the beehive is pushed a further cell to the right, but the mechanism then breaks down and a third electron causes the entire setup to disintegrate. So, I'm looking for a way to detect that the beehive has moved, and then move it back and emit a glider.

I won't post the rules I've made so far since I might change them later, but here's a picture of the above effects so you know what I'm talking about (red = state 1, yellow = state 2):

Image

Thanks in advance for any suggestions.
Image
This is why signature character limits are pointless.

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

Re: tri-state + lightspeed wire

Post by Keiji » May 13th, 2010, 6:31 pm

Small update:

I now have two working "gates", both taking the form of T-junctions with what I shall call two ends and a middle. The first I call the transistor, but it's more like an XOR gate - it sends an electron out of the middle if it receives one from an end, but if two arrive at the ends at the same time, it outputs nothing. The second is the splitter, which produces an electron from each end when it receives one from the middle. Both are stable but have a recovery time of 6 generations. Four splitters can be put together as close as possible to make a period 6 electron generator, or further away to make a generator of any desired period >6. Both the splitter and transistor act as diodes; an electron sent the wrong way through them will simply disappear.

I also have an "input" method to convert a glider to an electron, but like the "output" method described in my previous post, it only works once. In this construction, the glider cleanly destroys the stabilizing end of a short diagonal wick, which sends an electron down the wire and is then replaced by some stable cells. I conjecture it's possible to restore the original construction via glider synthesis, though it would probably be quite difficult to find such a synthesis as the population is quite dense. The reaction takes 8 generations to go from the newly cut wick to the stabilized cells.

Sending a pair of electrons closer than 6 cells apart to anything other than a plain wire, or a sending a pair of electrons towards each other (regardless of whether they are separated by an even or odd number of cells) will make everything self-destruct... just in case you were wondering.

Here's a picture of all the new components:

Image
Image
This is why signature character limits are pointless.

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

Re: tri-state + lightspeed wire

Post by Extrementhusiast » May 14th, 2010, 1:14 am

Welcome to the board! :mrgreen: The rule is interesting, but complex. For the beehive pusher, you could use two to get an arbitrarily high-period oscillator. Where did you get the images? Was it from Golly, or somewhere else?
I Like My Heisenburps! (and others)

User avatar
calcyman
Posts: 2095
Joined: June 1st, 2009, 4:32 pm

Re: tri-state + lightspeed wire

Post by calcyman » May 14th, 2010, 2:32 am

Very impressive!

The first I call the transistor, but it's more like an XOR gate
XOR gate would really be more accurate, but the name 'transistor' reflects the fact that it is composed of two types of cells. You could even call the cells p-states and n-states, assuming that the relationship between the two states is symmetrical.
Both the splitter and transistor act as diodes
Oooh -- you're getting very close to Wireworld-completeness, or the ability to perform any finite computation. Do you have an AND gate / OR gate? (XOR gates can be coupled with periodic emitters to yield NOT gates.)
So, I'm looking for a way to detect that the beehive has moved, and then move it back and emit a glider.
No simple still life has been found that fits your description, even without emitting a glider. You could theoretically engineer a Herschel track to accomplish this.

Try replacing the beehive with a boat or something, and see if you can coax a glider out of it.
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: tri-state + lightspeed wire

Post by Keiji » May 14th, 2010, 7:02 am

Extrementhusiast wrote:Welcome to the board! :mrgreen: The rule is interesting, but complex. For the beehive pusher, you could use two to get an arbitrarily high-period oscillator. Where did you get the images? Was it from Golly, or somewhere else?
Thanks! Yes, the pictures were from Golly. I realized I could easily make an oscillator from two of them - but the original purpose was to emit a glider, and such an oscillator wouldn't help with that ;)

The rules are rather complex, I'm using RuleTable at the moment and I have 27 rules for normal Life (using a variable for state 1 or 2), 5 rules for normal wire (straight and corners), 4 rules for the beehive pusher, 9 rules for the splitter, 7 rules for the transistor and 1 for the one-time input. No doubt the latter objects rely on previous rules as well though.

I was originally intending to use rules only consisting of "if cell in state N is surrounded by p cells of state P and q cells of state Q, go to state R", though I haven't attempted this (due to Golly not supporting the "permute" symmetry and not wanting to manually permute it every time) and I imagine it probably isn't possible to get the same functionality within the same area (essentially 5x5 for each gate) and processing time (6 generations) using such rules.
calcyman wrote:XOR gate would really be more accurate, but the name 'transistor' reflects the fact that it is composed of two types of cells. You could even call the cells p-states and n-states, assuming that the relationship between the two states is symmetrical.
The relationship isn't symmetrical - note that the signal encoding is 22210222 (moving to the right as shown here) - if this were changed to 11120111, the 0 would become a 1 and the 2 would die (because those are the rules that make the intended signal encoding work), and it would become 11101111, which would rapidly disintegrate.

The reason I called it the transistor in the first place is because I intended its use as a NOT gate, which one type of transistor acts as, IIRC.
Oooh -- you're getting very close to Wireworld-completeness, or the ability to perform any finite computation. Do you have an AND gate / OR gate? (XOR gates can be coupled with periodic emitters to yield NOT gates.)
I already have a splitter and an XOR gate, so it already has the ability to perform finite computation. I'm not particularly interested in adding extra rules to support an AND/OR gate, since they can be made from combinations of splitters and XORs anyway (edit: actually, thinking about it, I might be wrong on this...). There are two more important things I wanted to find (other than a reusable input/output construction), which are a method to arbitrarily construct or destroy parts of the wiring technology so that a Turing machine with an ever-extending tape can be constructed, and a method to "flip" the color of a glider from state 1 to state 2, since my current input method requires a state 2 glider, but my output method uses state 1 Life patterns.
So, I'm looking for a way to detect that the beehive has moved, and then move it back and emit a glider.
No simple still life has been found that fits your description, even without emitting a glider. You could theoretically engineer a Herschel track to accomplish this.

Try replacing the beehive with a boat or something, and see if you can coax a glider out of it.
Are Herschel tracks relatively easy to construct? I've never tried but they look ridiculously complicated (which is why I've never tried).

The beehive is necessary to ensure the bi-block gets reconstructed. If I replace the beehive with a ship in a certain position, it does emit a glider, but it then destroys the wire track. A boat destroys the track without emitting a glider. A tub becomes a traffic light and turns the bi-block into the double L configuration shown in generation 30 in my first post. A bi-block turns the main bi-block into two boats...

...

Separating the bi-block into two blocks with 3 cells vertically between them destroys the two blocks and reconstructs the original bi-block after 21 generations (six more than the beehive pusher took), while producing a spark which is one cell off a glider (well, a pair of them)...

I'm going to see if I can use that spark...

Edit:

I have now found a one-time reaction which produces a glider and stabilizes after 207 generations:

Image
(the left eater simply eats a second glider fired in the opposite direction - without this eater, the glider stabilizes as a pair of red blocks sitting on the yellow blocks of the wire)

If the two eaters are removed, the reaction instead produces a B-heptomino (and some junk) which later turns into a Herschel (and some different junk):

Image

Edit2:

Even better, the following produces a glider and a traffic light:

Image
Image
This is why signature character limits are pointless.

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

Re: tri-state + lightspeed wire

Post by Keiji » May 14th, 2010, 8:47 am

Okay, I've realized that you can't make an AND/OR gate from an XOR gate, so at the expense of losing the original XOR gate/transistor mechanism entirely (you now need to use a splitter and a stopend to alter the corner timing, instead of the transistor construction) and changing the way the input construction works, I've created a NOR gate. There are three inputs and one output; an electron will be generated at the output iff one arrives at the top input and none arrive at the side inputs. Like the splitter and the original XOR gate, it has recovery time of 6 generations and "fits" within a 5x5 area (though it's really a 5x6 area due to the two topmost stable state 1 cells):

Image

And just for completeness, the altered input construction:

Image
Image
This is why signature character limits are pointless.

Axaj
Posts: 232
Joined: September 26th, 2009, 12:23 am

Re: tri-state + lightspeed wire

Post by Axaj » May 14th, 2010, 10:43 am

This is neat, I'd love to see the rule table/tree of this.
Image

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

Re: tri-state + lightspeed wire

Post by Extrementhusiast » May 14th, 2010, 11:20 am

Are Herschel tracks relatively easy to construct? I've never tried but they look ridiculously complicated (which is why I've never tried).
Individual Herschel conduits are not easy to construct by hand, but there are 15 or so Herschel conduits that you can just paste together to make one long Herschel conduit/track. So, by that method, Herschel TRACKS are easy to construct, but Herschel CONDUITS aren't.
I Like My Heisenburps! (and others)

User avatar
calcyman
Posts: 2095
Joined: June 1st, 2009, 4:32 pm

Re: tri-state + lightspeed wire

Post by calcyman » May 14th, 2010, 11:34 am

... a method to arbitrarily construct or destroy parts of the wiring technology so that a Turing machine with an ever-extending tape can be constructed ...
I presume that you know that these are already possible in Life. My Phi calculator uses several unbounded memory tapes to calculate and print the infinite deimal expansion of phi (1.618033...). You can load the following file into Golly:

http://calcyman.awardspace.co.uk/life-massive/phi.mc

You'll have to increase the Golly step size to 8^8 to watch it in a reasonable amount of time. It can output 30 digits in the first hour of operation, and does so in polynomial time. You're welcome to utilise any of the components in your own constructions, of course, such as the memory tapes and printer.


Anyway, your extensible wiring would look much more elegant and ingenious than my clumsy fields of reflectors and Herschel tracks.

Okay, I've realized that you can't make an AND/OR gate from an XOR gate
Correct. A combination of XOR gates can only calculate the parity of several inputs.


There are three inputs and one output; an electron will be generated at the output iff one arrives at the top input and none arrive at the side inputs.
That's not a NOR gate; it is known as the "A AND NOT B" gate. It is, of course, equally universal, and is much more like a true transistor than the XOR gate.


Are Herschel tracks relatively easy to construct?
Herschel tracks don't involve synchronisation, so they are as easy to assemble as attaching Lego bricks together. Custom-building a Herschel track to have a specific displacement and delay is only slightly harder, as it simply involves inputting parameters into the Hersrch search program.

Herschel tracks are comprised of a string of conduits, which can rotate, translate or flip (or any combination thereof) a Herschel. For example, the R64 conduit rotates a Herschel clockwise by 90° in 64 generations. Four copies can be attached to form a loop with a period of 256:

Code: Select all

x = 49, y = 49, rule = S23/B3
31boo$31boo5boo$38boo3$7boo27boo$7boo27boo$42boo$42boo$boo$boo$5boo$5b
oo4$oo$oo5$34b3o$34bo$33b3o7$47boo$47boo4$42boo$42boo$46boo$46boo$5boo
$5boo$11boo27boo$11boo27boo3$9boo$9boo5boo$16boo!
All known 90° stable glider reflectors use Herschel tracks. These, in turn, can be used to form logic gates and memory units, and can eventually be assembled into massive constructions.

Here is a medium-sized Herschel construction, which converts a glider into a LWSS and recovers:

Code: Select all

x = 163, y = 113, rule = B3/S23
45bo22boo7boo$45b3o20boo7bobo44boo$48bo26bobob3o42boo5boo$47boo26boo5b
o12bo35boo$81boo12b3o7boo$98bo6bo3boo$97boo4bobo4bo18boo$30bo72boo5bob
o16boo$4bo9bo15b3o78boo22boo$4b3o5b3o18bo101boo$7bo3bo20boo11boo$6boo
3boo32boo$$4bo$bbobo$3boo4$20boo$20boo$8boo$7bobbo127boo$bboo4boo81boo
45bo$bobo62boo24bo43bobo$bo65bo21b3o3boboo37boo$oo44boo16b3o22bobb4ob
oo46bo$10boo34bobo15bo27bo50b3o4boo$10bo37bo45booboobboo6boo31bo7bo$
11b3o34boo45bobo4bo6bobo30boo4bobo$13bo56boo23bobb4o9bo9boo25boo$70bo
25bobobbobo7boo9bo$68bobo26bo4boo18bobo29boo$68boo53boo29bo$152bobo$
152boo$$11boo$10bobo28bo42bo$10bo30b3o38b3o17boo$9boo33bo36bo20bo$43b
oo23boo11boo20bo11bo$68boo32boo9b3o$112bo42bo$112boo10boo28bobo$124bo
30bo$122bobo$122boo29b5o$99boo52bo4bo$99boo55bobboboo$156booboboo$32bo
23boo95bo5bo$31bobo22bo95bobo4boboo$32bo14boo8b3o92bobbobbooboo$47bo
11bo93boo$48b3o$50bo82boo23boo$67boo39boo23boo23bo$34boo30bobo22boo16b
o46bobo$33bobo30bo24bo14b3o47boo$33bo31boo25b3o11bo$20bo11boo60bo26boo
$20b3o25boobo69boo3bo$23bo24boboo73bobo$22boo102bobo$41boo85bo$41boo
85b3o$131bo$130boo25boo$157boo6$156boo$156boo3$91boo$92bo$51boo39bobo$
51bo41boo27boo$49bobo70bo$49boo69bobo12bo$120boo12bobo$134boo$$79bo48b
oo$60boo17b3o47bo$53boo6bo20bo46bobo$53bo6bo20boo11boo34boo$51bobo6boo
32boo$51boo3$38boo$37bobo110boo$37bo25boo85boo$36boo25boo$119boo$106b
oo11boo$100boo5bo39boo$41boo54boobbobb3o40boo$42bo54boobo3bo$39b3o14b
oo42bobobo$39bo16bo15boo23booboboo19boo$50bo6b3o11bobo17boo4bobbo23bo$
49bobo7bo11bo19boo6boo20b3o$50bo19boo49bo16boo$139bo$136b3o$136bo!
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: tri-state + lightspeed wire

Post by Keiji » May 14th, 2010, 12:21 pm

This is neat, I'd love to see the rule table/tree of this.
Since I've got finite universal computation now I'll post the current table:

Code: Select all

n_states:3
neighborhood:Moore
symmetries:rotate8reflect
var a={1,2}

## Life rules
# birth
0,a,a,a,0,0,0,0,0,a
0,a,a,0,a,0,0,0,0,a
0,a,a,0,0,a,0,0,0,a
0,a,0,a,0,a,0,0,0,a
0,a,0,a,0,0,a,0,0,a

# death with 0/1
a,0,0,0,0,0,0,0,0,0
a,a,0,0,0,0,0,0,0,0

# death with 4
a,a,a,a,a,0,0,0,0,0
a,a,a,a,0,a,0,0,0,0
a,a,a,a,0,0,a,0,0,0
a,a,a,0,a,a,0,0,0,0
a,a,a,0,a,0,a,0,0,0
a,a,a,0,a,0,0,a,0,0
a,a,a,0,0,a,a,0,0,0
a,a,a,0,0,a,0,a,0,0
a,a,0,a,0,a,0,a,0,0

# death with 5
a,0,0,0,a,a,a,a,a,0
a,0,0,a,0,a,a,a,a,0
a,0,0,a,a,0,a,a,a,0
a,0,a,0,a,0,a,a,a,0
a,0,a,0,a,a,0,a,a,0

# death with 6
a,0,0,a,a,a,a,a,a,0
a,0,a,0,a,a,a,a,a,0
a,0,a,a,0,a,a,a,a,0
a,0,a,a,a,0,a,a,a,0

# death with 7/8
a,a,a,a,a,a,a,a,0,0
a,a,a,a,a,a,a,a,a,0

## Wire rules
# normal wire
0,1,0,0,0,2,0,0,0,1
0,1,0,0,2,0,0,0,0,1
1,2,0,0,0,0,0,0,0,2
1,2,0,0,0,2,0,0,0,2
2,1,0,0,0,1,0,0,0,1

# beehive pusher
1,2,0,0,0,1,0,0,0,2
2,1,0,1,0,0,0,0,0,0
0,2,1,0,1,1,1,0,0,1
1,2,0,1,1,1,1,1,0,0

# splitter
2,1,0,0,2,1,2,0,0,1
1,1,0,2,2,2,2,2,0,2
2,2,0,2,2,2,1,0,0,0
2,2,0,1,2,2,2,2,0,0
0,2,0,0,2,2,1,0,0,1
2,2,0,0,1,2,1,0,0,1
0,1,2,2,2,0,2,0,0,2
1,2,2,1,0,0,0,0,0,2
1,2,2,0,0,0,0,0,0,2

# nor
0,1,0,1,1,0,1,2,0,1
1,1,0,2,1,0,1,2,0,0
0,0,2,1,1,1,1,1,2,1
2,0,1,1,2,0,2,0,2,0
1,0,2,1,0,1,0,1,2,2
0,2,0,0,1,2,1,0,0,1
2,1,0,1,0,1,0,1,0,0
0,0,0,1,2,1,2,0,2,2
1,0,0,0,0,0,2,1,2,2
0,2,1,0,0,1,2,1,0,1
1,1,2,2,0,2,1,0,0,0

# input
0,1,0,0,2,1,2,0,0,2
1,1,2,0,0,0,0,0,0,2
Incidentally this rule can lead to some very chaotic patterns; for example I tried firing two state-2 gliders at a state-1 block and it ran for over 1,200,000 generations without stabilizing (it may be infinite for all I know; I got bored of watching it) as boundaries between areas of the two states tend to stay rock solid themselves and spew chaos in the vicinity. I would prefer changing the rules so that, while everything I've made so far still works, any combination of state 1 and 2 that isn't necessary for wiring flips to the opposite state in the hope that that would remove this "rock solid" property and encourage tri-state oscillators and other interesting patterns and perhaps make it easier to engineer a whole pattern state-flipper.
calcyman wrote:
... a method to arbitrarily construct or destroy parts of the wiring technology so that a Turing machine with an ever-extending tape can be constructed ...
I presume that you know that these are already possible in Life.
Yes, I already know that one can build a Turing machine in Life. However, doing it in classic Life requires a huge number of cells and a huge number of generations. The entire point of what I'm doing is to make calculation possible using a "small" number of cells and generations, so that you can actually see what's happening without zooming out past 1:1.
There are three inputs and one output; an electron will be generated at the output iff one arrives at the top input and none arrive at the side inputs.
That's not a NOR gate; it is known as the "A AND NOT B" gate. It is, of course, equally universal, and is much more like a true transistor than the XOR gate.
Okay, put more correctly: it's an "A AND NOT (B OR C)" gate, where A is the top input, B is the left input and C is the right input. But the top input was always supposed to be a period 6 clock (or whatever period you like so long as it's at least 6 and is in sync with the other inputs) - so I only count B and C as "real" inputs. Certainly, if you want an AND gate, it's easier to wire up two of these in an AND NOT NOT configuration than whatever the normal NOR construction is, but it was intended to be a NOR gate.

Has anyone ever built a pattern which stretches the wire medium I'm using (three parallel lines stabilized by blocks)? I imagine this would be the easy part, compared to synthesizing corners, splitters, NOR gates and input/output constructions, since those use both live states.

In the mean time, I'll experiment with Herschel tracks to see if I can do anything useful with that output reaction...
Image
This is why signature character limits are pointless.

Post Reply