Message Boards Message Boards

17
|
22073 Views
|
3 Replies
|
26 Total Likes
View groups...
Share
Share this post:

Lighting up WireWorld by image processing and exploring complex circuitry

Posted 12 years ago
I just found out about a wonderful machinery called WireWorld  ( MathWorld link ). It is simple algorithm (a cellular automaton) proposed by Brian Silverman in 1987 that can simulate all sorts of electrical circuitry from trivial wires to whole computers. The most precious thing about it – it is brutally simple. Imagine you have infinite graph paper. Empty cells are zeros. Wires (conductors) are 3s. Electrons running in the wires are represented by 1 and 2, - 1 for head and 2 for tail so we know direction where electron moves. Here are the rules.
  • Empty ? Empty
  • Electron head ? Electron tail
  • Electron tail ? Conductor
  • Conductor ? Electron head if exactly one or two of the neighbouring cells are electron heads, or remains Conductor otherwise. 
Now be amazed – despite this simplicity WireWorld is Turing-complete or computationally universal. But this is not what I’d like to talk about. 

It is pretty easy to write WireWorld in Mathematica. And there are many circuits built by various folks that do interesting things. But when I was looking around I found just simple circuits while I was really fascinated by huge circuitry similar to the 2nd image on the dedicated Wikipedia page titled “Example of a complicated circuit made in WireWorld: a seven segment display and decoder.” The way it lights up was beautiful, but – alas – I literally could not find the data for its structure. And building it by hand seemed unreasonably tedious. 

But then it downed on me – that image in Wikipedia is the data – if processed properly. I am sure the data are given somewhere, but it is always a sport & fun to reverse-engineer things. So here is how to reconstruct a WireWorld seven segment display just based in its image and then light it up like a Christmas tree.

First we import the image. It is animated .GIF so we need the first frame as the setup of the structure.
i = Import["https://upload.wikimedia.org/wikipedia/en/5/5d/Animated_display.gif"];
i[[1]]



Quality desires to be better – another reason I wanted to remake it. It seems like every cell of WireWorld structure corresponds to exactly one pixel in that frame. This is not surprising – person who generated it probably chosen this as a simplest setting to make the .GIF. Now let see how many colors in that image – a good guess is 4 because of the rules of the WireWorld – colors are background, wires, and heads and tails of electrons. Well good guess:
ArrayPlot@{DominantColors[i[[1]], 10]}


But these are RGB colors. I need data presented by a matrix with elements given by integers from 0 to 3. So which color corresponds to which integer? Careful examination of the image makes things clear:
col = Flatten[i[[1]] // ImageData, 1] // Union;
Grid[{Graphics[{RGBColor[#], Disk[]}] & /@ col, col, {0, 3, 2, 1}}, Frame -> All, Spacings -> {1, 2}]



Now the simple step of constructing the WireWorld structure out of Wikipedia image:
data = ImageData[i[[1]]] /. Thread[Rule[col, {0, 3, 2, 1}]];
And with just a few lines of code we can light it up – what a marvelous pixel perfect spectacle!
Dynamic[ArrayPlot[
  data = CellularAutomaton[{{{_, _, _}, {_, 0, _}, {_, _, _}} -> 0, {{_, _, _}, {_, 1, _}, {_, _, _}} -> 2,
                            {{_, _, _}, {_, 2, _}, {_, _, _}} -> 3, {{a_, b_, c_}, {d_, 3, e_}, {f_, g_, h_}} :>
      Switch[Count[{a, b, c, d, e, f, g, h}, 1], 1, 1, 2, 1, _, 3]},
    data], ColorRules -> {0 -> Black, 1 -> Red, 2 -> Yellow,
    3 -> Gray}, PixelConstrained -> 2]]



I used built in function CellularAutomaton that made thing so easy and adopted a snippet of code from the Rosetta Code page (btw Mathematica code there is the shortest I think). 

Now have you ever thought about random circuits? Why would you think about them? Well because browsing random circuits you can discover interesting elements that you would not know exist. This is sometimes called “exploring the computational universe” abut which you can find out in the New Kind of Science book or learn hands on in the Wolfram Science Summer School.

Here I build a random circuit using another delightful Elementary Cellular Automaton Rule 54. It has a few cool properties, for example being a candidate for computational universality. But we interested in its ability to produce wiry patterns of complex shapes suitable for running WireWorld on them. These are difference patterns which are sort of analogy of Butterfly Effect in discrite world of bytes. The question we are asking here is not “if we get a hurricane if butterfly had flapped its wings earlier”, but if we get something interesting by flipping a single bit in a massive evolution in discrete space. Here is a function that builds a random circuit of difference pattern of Rule 54 and then runs WireWorld on it.
 WireWolrdRule54[sz_, sr_] := DynamicModule[
   {
    size = sz,
    half = Round[sz/2],
    ic1, ic2, data
    },
  
   SeedRandom[sr];
  
  ic1 = RandomInteger[1, size];
  ic2 = MapAt[1 - # &, ic1, half];
 
  data =
   ArrayPad[
    ReplacePart[
     3 Abs[CellularAutomaton[54, ic1, size - 1] -
        CellularAutomaton[54, ic2, size - 1]], {{1, half} ->
       2, {2, half} -> 1}], {{1, 0}, {0, 0}}];
 
  Dynamic[
   ArrayPlot[
    data = CellularAutomaton[{{{_, _, _}, {_, 0, _}, {_, _, _}} ->
        0, {{_, _, _}, {_, 1, _}, {_, _, _}} ->
        2, {{_, _, _}, {_, 2, _}, {_, _, _}} ->
        3, {{a_, b_, c_}, {d_, 3, e_}, {f_, g_, h_}} :>
        Switch[Count[{a, b, c, d, e, f, g, h}, 1], 1, 1, 2, 1, _, 3]},
       data], ColorRules -> {0 -> Black, 1 -> Red, 2 -> Yellow,
      3 -> Gray}, PixelConstrained -> 2]
   ]
  ]
Here are a few samples:
{WireWolrdRule54[200, 4], WireWolrdRule54[200, 83]}



What can we immediately notice? A single electron can run as it is, alone, until it hit a structure that can generate more electrons. Another thing – there are structures that do not conduct electrons in one direction, but do so in the opposite one – they are called diodes.

And of course, as soon as I finished all this, someone let me know that the data for largest circuit - The Wireworld Computer – is available on this webpage. To see it running we first need to import data. The data are in archived ZIP file which Mathematica understands perfectly. Let's see what is inside the ZIP file:
In[1]:= Import["http://www.zen6741.zen.co.uk/quinapalus/wi-primes.zip"]
Out[1]= {"primes.wi"}
Let's digg that out:
raw = Import["http://www.zen6741.zen.co.uk/quinapalus/wi-primes.zip", "primes.wi"];
Now the file is basically text and we need to do some conversion to numerical matrix. Symbol “@” is the head, “~” is the tail, and “#” is the wire:
data = ArrayPad[PadRight[Characters /@ StringSplit[raw, "\n"]] /. {" " -> 0, "~" -> 2, "@" -> 1, "#" -> 3}, 1][[3 ;; -1]];
Now we can run this awe-inspiring structure as we did before: 
Dynamic[MatrixPlot[
  data = CellularAutomaton[{{{_, _, _}, {_, 0, _}, {_, _, _}} -> 0, {{_, _, _}, {_, 1, _}, {_, _, _}} -> 2,
                            {{_, _, _}, {_, 2, _}, {_, _, _}} -> 3, {{a_, b_, c_}, {d_, 3, e_}, {f_, g_, h_}} :>
      Switch[Count[{a, b, c, d, e, f, g, h}, 1], 1, 1, 2, 1, _, 3]},
    data], ColorRules -> {1 -> Yellow, 2 -> Red, 3 -> Gray,
    0 -> Black}, ImageSize -> 500, Frame -> False]]



To discover more things check out a great recently published demonstration that inspired me to check this all out:

WireWorld Gates and Gadgets

POSTED BY: Vitaliy Kaurov
3 Replies
That's a very interesting factoid. I find the abstract of his talk to be very enlightening on the nature of WireWorld:
An Early Exploration of the Computational Universe
Brian Silverman
Playful Invention Company, MIT Media Lab


In the early 1980s I became fascinated with John Conway’s Game of Life. I had read that Conway had created the game to be able to demonstrate that computational universality could be shown in a system with simple rules. He succeeded but the nature of the demonstration was a description of what needed to be done, not actual initial conditions. This was because the “computer” he wanted to build was so large that it would vastly outstrip the resources of practical computers of the time. I wanted to see some actual computation happening so I started exploring similar rules looking for a rule that would be more friendly to the notion. One of the results was the WireWorld rule that allows logic gates to be built quite directly. In this talk I will retrace the path I took in this early exploration of the computational universe reinterpreting it from an NKS perspective.
POSTED BY: Vitaliy Kaurov
Vitaliy mentioned exploring the computational universe at the Wolfram Science Summer School, so I thought I'd mention that the website is now accepting applications for next summer.  (Note that Vitaliy and Philip are alumni.)
POSTED BY: Todd Rowland
Brian Silverman, the inventor of WireWorld gave a talk at NKS 2006 Conference: An Early Exploration of the Computational Universe
POSTED BY: Philip Dutton
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract