Math Games

WireWorld Multiplication

Ed Pegg Jr., May 24, 2004

For A New Kind of Science, it was desirable to show a cellular automaton that demonstrated logic circuitry, within a simple picture. Systems such as the Game of Life can create logic circuits, but usually not within a 100×100 space. For example, Paul Rendell's Universal Turing Machine was created with Life, but it is somewhat large. Eventually, we looked at Brian Silverman's WireWorld rule: White (background) goes to White. Red (electron head) goes to Green (electron tail). Green (electron tail) goes to Black (wire). Black (wire) goes to Red if it touches exactly 1 or 2 Reds. In WireWorld, the logic gates are: (not, or, xor, and, nand).

Figure 1. Logic gates in Brian Silverman's WireWorld. (MCL code)

With the cellular automaton logic, and the appropriate logic gates, a construction in WireWorld is easy. For example, the logic of cellular automaton rule 30 is p xor (q or r). The following images demonstrate how WireWorld can emulate Rule 110, with a before and after shot of 3608 steps, along with an image of Rule 110.

  
Figure 2. WireWorld emulation of Rule 110. (MCL code)

This was a good demonstration, so it got into the book. Months later, I met the original creator of WireWorld, Brian Silverman, at the NKS2003 conference. Brian told me that he invented WireWorld after getting frustrated with the Game of Life. He only had a 40×40 screen in 1986, and designed WireWorld so that he could actually see something happening. Brian is still extending the ideas of "see something happening" today, through the continued development of the StarLogo System.

In 1996, Brian Silverman did a write-up of WireWorld for web publication, with explanations, insight, and Java demonstrations. He has very graciously allowed me to update and republish it here.

Link to Brian Silverman's interactive article, The Virtual Computer.

Obviously, it's easy to make a logic circuit in WireWorld. Still, I wondered whether it was truly universal. It's one thing to have the pieces, but can they actually be made into a computer? In constructions, timing is everything. On 24 July 2002, I posted a challenge to my mathpuzzle.com site: "If you'd like to experiment with large constructions, I'll award $10 to the first person that can make a WireWorld construction capable of multiplying two 8 digit binary numbers."

Little did I know how much would come out of this challenge.

2 Aug 2002 -- Brian Trial took up my challenge to make a working Multiplier in WireWorld. It can be run in the free program Mirek's Cellebration. Brian: "Without Mirek's excellent application I couldn't have begun to put this together. Note that multiplication is done using a SINGLE full bit adder, with the carry bit and output fed back in as feedback loops. The entire operation takes about 18,000 generations to complete, so go get a cup of coffee. Don't forget to light the FUSE or the result won't get captured properly. The file as shown will multiply $A3 (value in b7 - b0) by $95 (value in a7 - a0) and put the result in c15 - c0."

Figure 3. Brian Trial's WireWorld Multiplier. (MCL Code)

18 Aug 2002 -- Nick Gardner: "I loved Brian Trial's WireWorld multiplier so much that I had to make my own. It's just a little bit smaller than Brian's version. :-) There's some brief notes about how it works in the pattern description." This is just stunning to watch in action in MCell. I didn't think multiplication of large numbers could be done with a simple cellular automata in such a small size, but there it is.

Figure 4. Nick Gardner's WireWorld multiplier. (MCL Code)

26 Sep 2003 -- Karl Scherer has made a grand page about WireWorld. His page contains many new discoveries for WireWorld logic circuits, many of which are considerably smaller than previously known constructions.  All of his constructions work within the WireWorld explorer, a program written with Zillions of Games.

13 Dec 2003 -- Nyles Heise fit a 32-bit WireWorld multiplier into a 22×93 rectangle.   Yes, that is a very tiny multiplication program. You can see his notes, or his MCL representation. (Input 1's, and Output 1's) You can download MCell from Mirek's site. In hexadecimal, the multiplier calculates EF4E75E7×EFA03229 = DFFFFFFFFFF7FFFF in 8116 cycles. See the Output 1's file for an expanded MCell version.  (Many other constructions are available at Nyles Heise's website.)

Figure 5.  Nick Gardner's WireWorld multiplier for EF4E75E7×EFA03229. (MCL Code)

On 6 July 2003, encouraged by what the previous challenge had uncovered, I tried another one. "$20 Challenge. I'm certain that WireWorld can be used to make tape-like cells that mimic Turing machines. If you can make one, please let me know."

This challenge was also solved.

12 March 2004 -- Nyles Heise: "In response to the $20 challenge posted on 6 July 2003, I've built several WireWorld implementations of a Turing Machine. I'm including two of them here. The Turing machines do unary multiplications. I set out to do the exact algorithm found in A. K. Dewdney's "The New Turing Omnibus", but backed of slightly by leaving the original numbers on the tape along with the product. The first design has 6 states plus halt and 4 symbols. It is basically the Nick Gardner approach. That is, it has specific latches to simulate the symbols on the tape. The symbols are read from and written to the tape location under the R/W head. The shift register is shifted either left or right one symbol. It's set up to do 4 = 2 X 2. The second design has 9 states plus halt and 2 symbols. This is Karl Scherer's approach where the tape is simulated as a loop in which electrons pass by the control mechanism and get modified as required. It's set up to do 5 X 4 = 20. Quite detailed descriptions of both machines are included in the .mcl and viewable by clicking the blue information button."

Figure 6.  Nick Gardner's WireWorld multiplier, via a Turing machine. (MCL Code)

13 May 2004 -- Nyles Heise has built Langton's Ant in WireWorld, along with many other things.  He also built a lovely Binary Counter (as explained at MathWorld).  They are incredible to watch.  All of these are differing implementations of 2-dimensional Turing machines (turmites).

Figure 7. Nick Gardner's WireWorld implementation of a 2D Turing machine that does binary counting. (MCL code)

My hope is that someday, a material can be made which can mimic a cellular automaton such as WireWorld.  With that, the Central Processing Units of computers could be made much smaller than they are today, and therefore much faster.

References:

Math Games archives.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as the administrator of the Mathematica Information Center.