

Article 354 of comp.theory.cell-automata:
Path: mimsy!haven!ames!think!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!maytag!watcsc!death
>From: [email-masked] (Trevor Green)
Newsgroups: comp.theory.cell-automata
Subject: Wireworld patterns
Keywords: long, wireworld
Message-ID: <[email-masked]>
Date: 25 Feb 90 05:01:18 GMT
Reply-To: [email-masked] (Trevor Green)
Organization: University of Waterloo Computer Science Club
Lines: 299

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 [email-masked] {alberta,uw-beaver,uunet}!ubc-cs!phillips

Trevor Green [email-masked] watmath!maytag!watcsc!death