phillips@cs.ubc.ca (George Phillips) (02/09/90)
In the Jan. 1990 issue of Scientific American, A. K. Dewdney describes
the rules for a cellular automata called "wireworld". For those that
haven't seen it, each cell has 4 possible states: space, wire, electron
head or electron tail. Cells interact with their 8 neighbours by the
following rules:
- space cells forever remain space cells
- electron tails turn into wire cells
- electron heads turn into electron tails
- wire cells remain wire cells unless bordered by 1 or 2 electron heads
With these rules, electrons composed of heads and tails can move along
wires and you can build diodes, OR gates, NOT gates, memory cells,
wire crossings and so on.
After a couple of really cheap hacks, I played with wireworld on my PC
and Unix and was able to come up with a 6 cycle memory cell, a number of
logical gates and some pulsars which generate electrons at different
rates. If anyone is interested, I'll post my patterns here and (hopefully)
someone can dazzle me with their discoveries. If such postings (or
even this posting) are inappropriate here, I'm sure you'll inform me :-).
--
George Phillips phillips@cs.ubc.ca {alberta,uw-beaver,uunet}!ubc-cs!phillipsxanthian@saturn.ADS.COM (Metafont Consultant Account) (02/10/90)
In article <6713@ubc-cs.UUCP> phillips@cs.ubc.ca (George Phillips) writes: > In the Jan. 1990 issue of Scientific American, A. K. Dewdney > describes the rules for a cellular automata called "wireworld". > For those that haven't seen it, each cell has 4 possible states: > space, wire, electron head or electron tail. Cells interact with > their 8 neighbours by the following rules: > > - space cells forever remain space cells > - electron tails turn into wire cells > - electron heads turn into electron tails > - wire cells remain wire cells unless bordered by 1 or 2 electron > heads > > With these rules, electrons composed of heads and tails can move > along wires and you can build diodes, OR gates, NOT gates, memory > cells, wire crossings and so on. > > After a couple of really cheap hacks, I played with wireworld on my > PC and Unix and was able to come up with a 6 cycle memory cell, a > number of logical gates and some pulsars which generate electrons > at different rates. If anyone is interested, I'll post my patterns > here and (hopefully) someone can dazzle me with their discoveries. > If such postings (or even this posting) are inappropriate here, I'm > sure you'll inform me :-). > > -- > George Phillips phillips@cs.ubc.ca > {alberta,uw-beaver,uunet}!ubc-cs!phillips Hey, post your cheap hacks, too. Porting them should be easier than coming up with them in the first place! This group is too quiet; a bit of source code wouldn't hurt a bit. -- Again, my opinions, not the account furnishers'. xanthian@well.sf.ca.us (Kent Paul Dolan) xanthian@ads.com - expiring soon; please use Well address for replies. Kent, the (bionic) man from xanth, now available as a build-a-xanthian kit at better toy stores near you. Warning - some parts proven fragile. -> METAFONT, TeX, graphics programming done on spec -- (415) 964-4486 <-
phillips@cs.ubc.ca (George Phillips) (02/12/90)
Here are some of the wireworld patterns I've developed. A quick legend:
'=' wire
' ' or '.' space
'#' electron head
'-' electron tail
I avoid using spaces since they may get converted to tabs and my stupid
programs would fail. Sometimes I'll stick in single tails ('-') just to
indicate where a pulse might be. Not all of the patterns work, but I'll
try and comment on what should do what. I suppose I should have put
these in a shar file, but that would have made commentary difficult so
you'll just have to hand edit them.
..................==....
.................=..=......
................===..======#-============.
................=.=.
.................=.=......................
.................=.=.....===-=====-====#-.
...==============.===...=................
...................=...=.................
....============....=#-....................
................=-#..........................
................=..=....................
.................==...................
A six-cycle memory cell. It is about to remember a
1 and then a 0 and then go back to 1 after a couple cycles. It has
a small bug in that the "write 0" line causes a single, spurious pulse
on the output, but that could be eliminated fairly easily.
........=
===================
........=
........=
........=
........=
A much improved "OR" gate (output going down):
..-...#..................................................................
.#==.-==.......======-#.......-#====-#==...............=.....=...........
..=...=................=................=.............=.=...=.=..........
..=.=.=...............===..............===............=.#...#.=..........
.=.===.=.............=.=................=..............-.=.=.-...........
.=..=..=..............=.========......==.=======.........=.=.............
.=..=..=.............==..............=.=...............=.=.=.=...........
.=..=..=.............==..............=.-.....-#====-#====...====#-=====-.
.=..=..=............=..=..............#.....=..........=.=.=.=..........=
.=..=..=.............#-.....................=............=.=............=
............................................=...........=...=...........=
............................................=...........=.=.=...........=
......................==....................=............===............#
.....===-#====-#==-#===.==.=................-.............=.............-
......................==..=.=...............=.............=.............=
.........................==..=========....................=.............=
......................==.=................................=..............
.....====-#====-===-#==.=.................................=..............
......................==..................................=..............
..........................................................=..............
In the above file we have a couple of NOT gates (top middle), an XOR gate
(bottom left) and a NAND gate (right). The inelegant part of these
NOT and NAND gates is that they have internal clocks -- a pulse arriving
must be in sync with the internal clock or the gate will fail to function.
I don't believe this can be helped, but an OR gate only requires that the
incoming pulses be in sync, which is seems to be a much nicer property.
On the other hand, the NAND gate does have a certain visual appeal.
.............................................................................
............=.==...........................................==................
...........===..=.........................................=..=...............
.........==.=.=.=..................====-#=====..........==..===..............
........=.....=.=.................=...........=........=.....=..==...........
=====-#=..==.=..=..=.========......=====#-====.====-#==..==.=.==..=..........
.........#..=..======...................................#..=.....========....
=====-#=..-=.=..=..=.==-...........-====#-====.====-#==..-=.=.==..=..........
........=.....=.=....=..#.........#...........=........=.....=..==.....===...
.........==.=.=.=.....==...........===========..........==..===.....=.=......
...........===..=.........................................=..=...=======.....
............=.==......................=....................==...=...=.=......
........===.........................=.=........................=......==.....
.......=...=.======..............=======.................======.......=......
.......=..===..............-=====...=.=.................=........===..=......
.......#...=......................==..==...............=........=...=.=......
........#==......................=..=.=.......-#====-#=.........=..===.......
................................=..===..........................=...=........
................................=...=...............-#====-#=...====.........
.............................#======.........................===.............
On the left is an AND gate and on the right is a NAND gate being fed test
patterns. The AND gate on the left is unfortunate: internally clocked
and is really only A & B = ~(~A | ~B). Happily, I found a non-clocked
AND gate (bottom right). The key is the "H" pattern near the output --
it does that actually ANDing. But 2 '1' pulses break the gate, so the
one signal must be multiplied into 2 electrons (by the G) with the
second electron stopping any out of control oscillations.
.-...-.......==.....................#..........=...........................#.
#=#.#.=..-..=..-.....................====....===#.......................=====
.=...=..#.=.#..#.......#.............====...=..=....#......==.....==...=...=.
.=.=.=...=..-..=..#...===............====...=..=...====...=..=...=..=..=..=..
=.===.=..=...==..==-...=.=....#......====...=..=....=..=..=.==#..=..=...==...
=..=..=..=.=.=....=.....=....===.....=..=..#===.=..=.==....=.=....===#....=..
=..=..=.=.===.=...=.....=....===.....=..=...=...=..=.......=.....=..=.....=..
=..=..=.=..=..=...=.....=...==.==....=..=.......=..=......=.=.=.=.=.......=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.....=...===...=......=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.....=....=....=......=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=......=...=...=.......=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
=..=..=.=..=..=...=.....=..=.=.=.=...=..=.......=..=.......=..=..=........=..
Some pulsars of rates from 3 to 9. To make it a bit tougher, I decided that
I would have to make the pulsars get their initial electron from an outside
wire rather than having an electron in the loop from creation. A little
junction which I call an "injector" accomplishes this. Notice that the
rate 5 pulsar is really a rate 10 pulsar with 2 electrons. I don't think it
is possible to build a loop which takes 5 generations to traverse.
.==========-#==========...........=====-#=========........................
=......................=.........=................=.......................
=......................=...=.....=................=.......................
=......................====.=....=................=.......................
=......................=....=....=...............===......................
=.....................===...=....=...............=.=......................
=.....................=.=..=......==========#-....=.......................
.#-....................=..===....................===......................
....................==.=...=....................=.=.......................
..===========-#======.=.===.=======.........==.=...=......................
.=................=.==.=...........=....=-#==.===...==============........
.=................=....=...........=...=....==.=.=........................
.=...............=...=.=...........=...=..........=.......................
.=...............=.====............=...=...........=......................
.=................=..=.=...........=...=...........=......................
.#.....................=...............=...........=......................
..-....................=...............=...........=......................
.......................=....===========............=......................
.......................=...=.......................=......................
.......................=....=#-...........................................
Some attempts at wire crossing. The one on the left stops some pulses
with diodes and splits an incoming pulse so that it suppresses the
pulse which goes down the wrong wire. The one on the right uses
injectors to send the puses in the "right" direction with diodes to
stop the rest. Unfortunately, both have a rather high cycle time.
.........................#.................
..........................=====............
...............................=...........
......................=...=====............
.....................=.=.=.................
.....................=.#.=.=.==............
......................-...===..#............
.....................===.=.=.=-............
......................=..=..................
.........======-#=====.==.==.===...===....
........=................=..=...=.=.......
........=...........-=.=.=.===..=.=.......
........=..........#..===...-....=..........
........=...........==.=.=.#.=..............
........=................=.=.=..............
........=................=..=...............
........=................=..................
........=................=..................
........=................=..................
.........=#-.............=..................
Another attempt at wire crossing. The idea was to use "power" to make the
circuit faster. But I ended up with nothing faster than before and
added internal clocking to boot :-(.
..................................
....................=====.........
.................=.=..............
................===...............
...............=.=.=..............
...............=...=..............
................=.=.==.=========..
............==.=.=.=..=...........
.#===========.=.=.=..===..........
-...........==.=.=.=..=...........
................=.=.==............
.................=................
................=.=...............
................===...............
.................#................
.................-................
.................=................
..................=================#-=
Another attempt at a wire crossing. A pulse from the right will send
electrons slightly staggered to the top wire. They will then cancel
each other. But the 2 electrons going to the right do not cancel each
other and send an output to the right. Similarly for the input on the
bottom. Diodes keep the other signals in check. A nice idea, but
still the cycle time is large :-(. I should hope a better wire crossing
can be constructed...
--
George Phillips phillips@cs.ubc.ca {alberta,uw-beaver,uunet}!ubc-cs!phillipsdeath@watcsc.waterloo.edu (Trevor Green) (02/25/90)
George Phillips, thank you for posting the source for your wireworld programme. When I can drag myself away from creating new patterns I might try to make it more efficient. I've been doing wireworld all day and my mind is a haze of =#-===s, but here are my revisions on George's patterns: (Note: I have slightly edited George's patterns for legibility's sake.) > '=' wire > '.' space > '#' electron head > '-' electron tail > (write 0) > ..I.... > .===... > .=.=... > ..=.=.. >O=.=.=.. > .=.===. > ....I.. > (write 1) >A six-cycle memory cell. I tried making a 4-cycle memory cell but failed. Anybody else care to give it a shot? Anyone got a 3-cycle memory cell? (-: > ... > .=. > I=I > .O. >A much improved "OR" gate. Thank you. It makes wireworld that much easier to use. > ....... >I-#==... > ....=.. > ...===. > ....=.. > ..==.==O > .=.=... > .=.-... > ..#.... > ....... > A NOT gate. The fastest NOT gate of this design is a 5-cycle NOT gate; the gate takes 5 cycles to clear following an input of 0. The 6-cycle NOT gate is, however, smaller. I include both of them here. Should you require a longer-cycle NOT gate, just replace the pulsar in either of the gates below with the pulsar of the desired cycle. (Note: with every diagram I post I include the vital statistics. Transit is the number of cycles it takes for a signal to propagate through the device, IBI (interval between inputs) is the number of cycles the device needs between inputs so that the output is guaranteed correct, and the size is the X and Y dimensions of the device. I is an input line and O is an output line (note: there may be more than one of either.)) ......... .=.O..=.. I==..=.-. .=.==..#. ...#...=. ....-==.. ......... ........ .=.O.... I==..... .=.===.. ...#..=. ....-=.. ........ Transit: 3 IBI: (5-cycle) 5 (6-cycle) 6 Size: (5-cycle) 9x7 (6-cycle) 8x7 > ....... > .==.... >I==.==.O > .==..=. > ....==. > .==.=.. > I=.=... > .==.... > ....... > An XOR gate. The main drawback of this particular XOR gate is that you have to stagger your pulses. I have come up with a symmetric XOR gate that also has a lower IBI: ....... .==.... I=.=... .==.==. .....=O .==.==. I=.=... .==.... ....... Transit: 6 IBI: 11 Size: 7x7 >........... >..=.....=.. >.=.=...=.=. >.=.#...#.=. >..-.=.=.-.. >....=.=.... >..=.=.=.=.. >.I==...==I. >..=.=.=.=.. >....=.=.... >...=...=... >...=.=.=... >....===.... >.....O..... > A NAND gate. A better NAND gate (5- and 6-cycle versions): ........... ...-#==.... ..=....=... ...==.-.... .....#..... ....=.=.... .=.=...=.=. I==..=..==I .=.=====.=. .....O..... ........... .....=..... ....=.=.... ....=.-.... .....#..... ....=.=.... .=.=...=.=. I==..=..==I .=.=====.=. .....O..... Transit: 6 IBI: (5-cycle) 5 (6-cycle) 6 Size: 11x10 As with NOT, this NAND has a minimum clearing time of 5, but can have any cycle greater than 4. The next 2 diagrams were a clocked AND gate (ugh!) and a NAND-gate set up for testing patterns, so I deleted them. > ................... > ..............=.O.. > ...........=======. > ..........=...=.=.. > .........=......==. > ...======.......=.. > ..=........===..=.. > .=........=...=.=.. >I=.........=..===... > ..........=...=.... > .....I=...====..... > .......===......... > An AND gate. This is quite elegant, if a little sloppy. I cleaned it up and this seems to be the optimum: ..I........ ...=====... ........=.. ..==...===. .=..=...=.. .=.======O. .=..=.=.=.. .===....... I.......... Transit: 9 IBI: 8 Size: 13x10 I tried another design for an AND gate, incorporating the XOR gate above, but it's larger and slower: .............. ....==........ ...==.=....... I==.==.==..... ........===... I.=.==.==..=.. .=.==.=...===. .=..==.....=.. .=.....====.O. ..=====....... .............. Transit: 14 IBI: 11 (same as XOR) Size: 14x11 >Some pulsars of rates from 3 to 9. (Patterns deleted) The minimum-size pulsars: .... ..... .#.. 3. 4x4 ..#.. 4. 5x5 .-=. .-.=. .... ..=.. ..... ...... ..-#.. 5. 6x7 .=..=. 10. 6x7 (just remove an electron) .=..=. .=..=. ..#-.. ...... > Notice that the >rate 5 pulsar is really a rate 10 pulsar with 2 electrons. I don't think it >is possible to build a loop which takes 5 generations to traverse. I think you're right. ..... ...... ...... ...... ..#.. 6. 5x6 ..-#.. 7. 6x6 ..-#.. 8. 6x6 ..-#.. 9. 6x7 .-.=. .=..=. .=..=. .=..=. .=.=. .=.=.. .=..=. .=..=. ..=.. ..=... ..==.. .=.=.. ..... ...... ...... ..=... ...... >Some attempts at wire crossing. As the diagrammes were rather large, I edited them out. However, I shall make a comment about all of them: they allowed individual signals to cross fine, but when 2 signals were sent simultaneously they'd cancel each other out. To the end of rectifying this, I came up with this rather ugly hack: .............. .....==.=..... .=====.==O.... I....==.=..... ........=..... I....==.=.=... .=..==.===.=.. .=.=.==.=..=.. .=.=......=... .=..==...=..O. .=....=.=...=. ..====...===.. .............. Transit: 22 (ugh!) IBI: 22 (double ugh!) Size: 14x13 Note the pair of delay loops at the bottom to prevent the signals from interfering with one another. It is rather inelegant, but it's the best I've come up with in two nights of wirehacking. Anybody got a *real* wire- crosser out there? For people attempting a wire-crosser, here's another design I came up with, with the idea of preventing the signals from colliding while they're in the device rather than delaying one beforehand and the other afterward. If someone can come up with a better bypass, you'll get a better wire-crosser out of this: ............ ..==..=..... .I=.===O.... ..==..=..... .....=====.. ....=.=...=. ...=.....=.. ..=.=...=... ..===...=... ...=...===.. ..=....=.=.. .=......=... ..===.=.=... .....===.... ..==..=..... .I=.===O.... ..==..=..... ............ Transit: 19 IBI: 24 Size: 12x18 (aack!) Have fun! >George Phillips phillips@cs.ubc.ca {alberta,uw-beaver,uunet}!ubc-cs!phillips Trevor Green death@csc.waterloo.edu watmath!maytag!watcsc!death
torbenm@diku.dk (Torben [gidius Mogensen) (03/01/90)
death@watcsc.waterloo.edu (Trevor Green) writes: > I have come up with a symmetric XOR gate that also has a lower IBI: > ....... > .==.... > I=.=... > .==.==. > .....=O > .==.==. > I=.=... > .==.... > ....... >Transit: 6 >IBI: 11 >Size: 7x7 How about: ..I.... .====.. .=.==O. .====.. ..I.... Transit: 3 IBI: 5 you can add another output opposite the O, which will be the OR'ed signal. >For people attempting a wire-crosser, here's another design I came up with, >with the idea of preventing the signals from colliding while they're in the >device rather than delaying one beforehand and the other afterward. If >someone can come up with a better bypass, you'll get a better wire-crosser >out of this: > ............ > ..==..=..... > .I=.===O.... > ..==..=..... > .....=====.. > ....=.=...=. > ...=.....=.. > ..=.=...=... > ..===...=... > ...=...===.. > ..=....=.=.. > .=......=... > ..===.=.=... > .....===.... > ..==..=..... > .I=.===O.... > ..==..=..... > ............ >Transit: 19 >IBI: 24 >Size: 12x18 (aack!) You can make a wire-crosser with 3 EOR gates: .....==..... ...==..=.... ..=...====.. .I....=.==O. ..=...====.. .====..=.... .=.====..... .====..=.... ..=...====.. .I....=.==O. ..=...====.. ...==..=.... .....==..... Transit: 9 IBI: 5 (as the EOR gate) I have not tried these except on paper, so there might be some bugs, but I believe not. >Trevor Green death@csc.waterloo.edu watmath!maytag!watcsc!death Torben Mogensen (torbenm@diku.dk)