Von Neumann Universal Constructor
This is one of my favorite topics and wikipedia pages! Please forgive my wall of text, and inscrutable ascii graphics, and check out the Buckley paper for better illustrations.<p>Here&#x27;s some JavaScript code that implements (and describes) John von Neuman&#x27;s 29 state cellular automata machine. I based it on some older &quot;jvn&quot; C code by R. Nobili, U. Pesavento, and Umberto Pesavento I found on the net, but I have rewritten it to be more symbolic and self documenting, so I could understand it better.<p>What it really needs is a specialized set of rule-specific editing tools and templates to stamp down, since it&#x27;s impossibly tedious to paint anything non-trivial with the CA painting tools that this version of CAM6 currently supports.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;SimHacker&#x2F;CAM6&#x2F;blob&#x2F;master&#x2F;javascript&#x2F;CAM6.js#L4569" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;SimHacker&#x2F;CAM6&#x2F;blob&#x2F;master&#x2F;javascript&#x2F;CAM...</a><p>I&#x27;ve tried to document what everything means and describe how it works. With evocative function names and comments like &quot;pointedToByExcitedOrdinaryOrSpecial&quot; (Return 1 if pointed by an excited transmission state (ordinary or special), else returns 0) and &quot;wellFlankedByExcitedNotNextExcitedConfluent&quot; (Return 1 if well flanked by an excited (not next excited) confluent state, else returns 0)! ;)<p>For example, here are the bit sequences for constructing new cells. You can send these sequences of bits down a wire to an arrow pointing into an empty space, and it will construct the corresponding cell in that empty space -- the intermediate construction states are called &quot;Sensitized&quot;, and they huffman-encode all the possible cells you can create. Note that you can only construct non-excited cells. (See Buckley, page 457, The mechanisms of construction, below.)<p><pre><code>                &#x2F;&#x2F; Instructions to the jvn29 construction arm, whose tip
                &#x2F;&#x2F; is an arrow pointing into an unexcited state, that
                &#x2F;&#x2F; creates a sensitized state which evolves into other
                &#x2F;&#x2F; states over time, given the following excitement inputs.

                constructionInstructions: {
                    OR:  &#x27;10000&#x27;, &#x2F;&#x2F; =&gt; S S0 S00 S000 OR
                    OU:  &#x27;10001&#x27;, &#x2F;&#x2F; =&gt; S S0 S00 S000 OU
                    OL:  &#x27;1001&#x27;,  &#x2F;&#x2F; =&gt; S S0 S00 OL
                    OD:  &#x27;1010&#x27;,  &#x2F;&#x2F; =&gt; S S0 S01 OD
                    SR:  &#x27;1011&#x27;,  &#x2F;&#x2F; =&gt; S S0 S01 SR
                    SU:  &#x27;1100&#x27;,  &#x2F;&#x2F; =&gt; S S1 S10 SU
                    SL:  &#x27;1101&#x27;,  &#x2F;&#x2F; =&gt; S S1 S10 SL
                    SD:  &#x27;1110&#x27;,  &#x2F;&#x2F; =&gt; S S1 S11 SD
                    C00: &#x27;1111&#x27;   &#x2F;&#x2F; =&gt; S S1 S11 C00
                },
</code></pre>
Here is the table of all the possible cell values, symbols and names (which is useful for an editor&#x27;s user interface):<p><pre><code>                &#x2F;&#x2F; Array of dicts describing cell values for jvn29.

                cellStates: [
                    { symbol: &#x27;U&#x27;,    value: 0x00, name: &#x27;Unexcited&#x27;              },
                    { symbol: &#x27;S&#x27;,    value: 0x01, name: &#x27;Sensitized&#x27;             },
                    { symbol: &#x27;S0&#x27;,   value: 0x02, name: &#x27;Sensitized 0&#x27;           },
                    { symbol: &#x27;S1&#x27;,   value: 0x03, name: &#x27;Sensitized 1&#x27;           },
                    { symbol: &#x27;S00&#x27;,  value: 0x04, name: &#x27;Sensitized 00&#x27;          },
                    { symbol: &#x27;S01&#x27;,  value: 0x05, name: &#x27;Sensitized 01&#x27;          },
                    { symbol: &#x27;S10&#x27;,  value: 0x06, name: &#x27;Sensitized 10&#x27;          },
                    { symbol: &#x27;S11&#x27;,  value: 0x07, name: &#x27;Sensitized 11&#x27;          },
                    { symbol: &#x27;S000&#x27;, value: 0x08, name: &#x27;Sensitized 000&#x27;         },
                    { symbol: &#x27;C00&#x27;,  value: 0x10, name: &#x27;Confluent 00&#x27;           },
                    { symbol: &#x27;C10&#x27;,  value: 0x11, name: &#x27;Confluent 10&#x27;           },
                    { symbol: &#x27;C01&#x27;,  value: 0x90, name: &#x27;Confluent 01&#x27;           },
                    { symbol: &#x27;C11&#x27;,  value: 0x91, name: &#x27;Confluent 11&#x27;           },
                    { symbol: &#x27;OR&#x27;,   value: 0x20, name: &#x27;Ordinary Right&#x27;         },
                    { symbol: &#x27;OU&#x27;,   value: 0x21, name: &#x27;Ordinary Up&#x27;            },
                    { symbol: &#x27;OL&#x27;,   value: 0x22, name: &#x27;Ordinary Left&#x27;          },
                    { symbol: &#x27;OD&#x27;,   value: 0x23, name: &#x27;Ordinary Down&#x27;          },
                    { symbol: &#x27;SR&#x27;,   value: 0x40, name: &#x27;Special Right&#x27;          },
                    { symbol: &#x27;SU&#x27;,   value: 0x41, name: &#x27;Special Up&#x27;             },
                    { symbol: &#x27;SL&#x27;,   value: 0x42, name: &#x27;Special Left&#x27;           },
                    { symbol: &#x27;SD&#x27;,   value: 0x43, name: &#x27;Special Down&#x27;           },
                    { symbol: &#x27;ORX&#x27;,  value: 0xa0, name: &#x27;Ordinary Right Excited&#x27; },
                    { symbol: &#x27;OUX&#x27;,  value: 0xa1, name: &#x27;Ordinary Up Excited&#x27;    },
                    { symbol: &#x27;OLX&#x27;,  value: 0xa2, name: &#x27;Ordinary Left Excited&#x27;  },
                    { symbol: &#x27;ODX&#x27;,  value: 0xa3, name: &#x27;Ordinary Down Excited&#x27;  },
                    { symbol: &#x27;SRX&#x27;,  value: 0xc0, name: &#x27;Special Right Excited&#x27;  },
                    { symbol: &#x27;SUX&#x27;,  value: 0xc1, name: &#x27;Special Up Excited&#x27;     },
                    { symbol: &#x27;SLX&#x27;,  value: 0xc2, name: &#x27;Special Left Excited&#x27;   },
                    { symbol: &#x27;SDX&#x27;,  value: 0xc3, name: &#x27;Special Down Excited&#x27;   }
                ],
</code></pre>
I wrote an earlier version in OpenLaszlo that had some custom editing tools, but that requires Flash, and was on my old Drupal site that&#x27;s not up any more. But here is the archive.org link and description (with a screen snapshot). I wasn&#x27;t able to get the old Flash app to run though. The source code has some interesting initial condition configurations, that I&#x27;ll try explain, and are described in more detail in a paper referenced on the Wikipedia page:<p><a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20110720235050&#x2F;https:&#x2F;&#x2F;www.donhopkins.com&#x2F;drupal&#x2F;node&#x2F;41" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20110720235050&#x2F;https:&#x2F;&#x2F;www.donho...</a><p>John von Neumann&#x27;s 29 state Cellular Automata Implemented in OpenLaszlo<p>Submitted by dhopkins on Sun, 2005-09-18 04:12. Cellular Automata Live Demos<p>For fun, and to learn OpenLaszlo, I implemented the classic 29 state self reproducing cellular automata, invented by John von Neumann.<p>The JavaScript and XML code is written with no thought to efficiency, just conceptual clarity and convenience of implementation. It can&#x27;t run a lot of cells at once, but at least it&#x27;s slow enough to watch it compute. Don&#x27;t worry: there&#x27;s not space for it to reproduce!<p>I&#x27;ve configured it with several interesting initial conditions, including several different approaches to signal crossing, and an exclusive-or gate.<p>It uses pie menus for editing the grid of cells.<p>Laszlo von Neumann Cellular Automata Demo<p><a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20120319060434&#x2F;http:&#x2F;&#x2F;www.donhopkins.com&#x2F;openlaszlo&#x2F;my-apps&#x2F;vonNeumann&#x2F;vonNeumann.lzx" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20120319060434&#x2F;http:&#x2F;&#x2F;www.donhop...</a><p>Laszlo von Neumann Cellular Automata Source Code in Laszlo<p><a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20120319060340&#x2F;http:&#x2F;&#x2F;www.donhopkins.com&#x2F;openlaszlo&#x2F;my-apps&#x2F;vonNeumann&#x2F;vonNeumann.lzx?lzt=source" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20120319060340&#x2F;http:&#x2F;&#x2F;www.donhop...</a><p>Here are some of the most interesting initial configurations: all different ways to perform signal crossing. Signal crossing is difficult with this rule, which doesn&#x27;t directly support it, so you have to &quot;emulate it in software&quot; with multi-celled machines or &quot;organs&quot;. Here are a few different ways of dealing with signal crossing, each with their own problems and limitations.<p>Buckley&#x27;s paper about these gadgets is called &quot;Signal crossing solutions in von Neumann self-replicating cellular automata&quot;. The Wikipedia page discusses some of it and links to the paper, but the link is broken. So here is the paper about it on archive.org, on page 453:<p><a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20081209155223&#x2F;https:&#x2F;&#x2F;uncomp.uwe.ac.uk&#x2F;free-books&#x2F;automata2008reducedsize.pdf" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20081209155223&#x2F;https:&#x2F;&#x2F;uncomp.uw...</a><p>or (faster download):<p><a href="https:&#x2F;&#x2F;donhopkins.com&#x2F;home&#x2F;documents&#x2F;automata2008reducedsize.pdf" rel="nofollow">https:&#x2F;&#x2F;donhopkins.com&#x2F;home&#x2F;documents&#x2F;automata2008reducedsiz...</a><p>The Real Time Crossing (Buckley, p. 457, The real-time crossing organ) is like a road intersection that splits the two crossing lanes, then uses traffic lights to give cars in each pair of lanes alternating turns to cross, and then merges the lanes back together (since each intersection works at 50% throughput, you need to split, use two of them, and merge -- Factorio and Satisfactory players will get what I mean, in terms of conveyor belts, splitters and mergers, and conveyor belt throughput).<p>The description of the real time crossing, &quot;This real time crossing is not easily constructible, but nonetheless here it is&quot;, is a reference to the fact that you can only construct non-excited cells (you&#x27;d get electrocuted if you tried to construct machines with the power on, so to speak -- it may be possible to kludge it with some simple machines, but in general it&#x27;s extremely impractical if not impossible -- see Buckley p. 470).<p>And after you&#x27;ve constructed a machine in a powered-down state, then you have to excite just the right cells at just the right time, to get the machine to work. But that&#x27;s impossible with this real time signal crossing machine! So it&#x27;s like a beautiful tiny crystal alien artifact with perfectly blinking lights, that the laws of physics practically prohibit from ever being constructed, but there it is.<p>The Real Time Crossing depends on having a certain synchronized configuration of excited cells in it, acting as synchronized clocks or traffic lights that start and stop all the traffic at just the right time so the cars don&#x27;t collide.<p>It&#x27;s not actually possible for a universal constructor to construct a real time crossing, because it can&#x27;t reach in through existing cells and excite internal cells from outside. It&#x27;s essentially like a &quot;Garden of Eden&quot; configuration, that had to have been constructed by the Hand of God, and can&#x27;t be copied or constructed, or used as part of a reproducible machine. Essentially it has a &quot;spark of life&quot; that is beyond the ability of creatures living in the world to ignite. Intelligent Design and DRM FTW! ;)<p><pre><code>          &lt;save
            name=&quot;Real Time Crossing&quot; 
            rows=&quot;16&quot; cols=&quot;16&quot;
            description=&quot;This real time crossing is not easily constructible, but nonetheless here it is.&quot;
          &gt;
    sssssw-----sbhb-
    yggggggggg-wbyb-
    hhhhhhhhhy-wbyb-
    yggggggggg-wbyb-
    ------sssw-wbyb-
    ------w----wbyb-
    ------w----wbyb-
    --ezshqaez-wbyb-
    --yty--wyt-wbyb-
    --shqshqsb-wbyb-
    ssq-wezw-z-wbybs
    --z-wyty-qswbybw
    --shqshqsy--bybw
    --ezw--wez--bybw
    --ytyqswyt--bybw
    -----w------hyhw
          &lt;&#x2F;save&gt;
</code></pre>
The &quot;Coded Channel Crossing&quot; (Buckley, p. 460) is like two channels sharing the same wire by using a coding system, so you have to somehow make sure neither channel tries to send a message over that one wire at the same time (left as an exercise for the reader ;), otherwise there will be a collision. This is the only kind of signal crossing organ designed by von Neumann.<p><pre><code>          &lt;save 
            name=&quot;Coded Channel Crossing&quot; 
            rows=&quot;8&quot; cols=&quot;64&quot;
            description=&quot;Coded channel crossings have interference problems, demonstrated here.&quot;
          &gt;
    -zaaaaaaa-----qsssesqsq-----------qhshqsssqsqsqsq---------------
    -z------w-----w---w-z-z-----------w-------w-z---z---------------
    -sshhsssqsssssqsqsq-ssssssssssssqsusqhesqsq-ssssshshssssssssssq-
    --------------------------w-----z-------------------------------
    zaagagaaa-thssqsssqsqsqsq-w-----b-tsssqsqsq---------------------
    z-------w-w-------w-z---b-w-----b-w---w-z-z---------------------
    ssssssssqsqsthqsqsq-ssssshw-----ssestsq-sshhsssssssssssssssssse-
    ----------------------------------------------------------------
          &lt;&#x2F;save&gt;
</code></pre>
This is the fun one, and the subject of Buckley&#x27;s paper, an &quot;Autoinitializing Exclusive Or&quot; organ (Buckley, p. 473 and on). You can use these to solve the signal crossing problem, without needing the intervention of a benevolent God to power up all your traffic lights with the right synchronization. It actually has a &quot;boot up&quot; sequence: you first send it a &quot;reset&quot; signal, and part of it is used to initialize all the clocks the first time it&#x27;s run, then it fires a bunch of &quot;explosive bolts&quot; that cut off the auto-initialization circuitry, and start up the exclusive or gate, after all its clocks have been initialized. It&#x27;s literally self modifying code, that pokes itself after it boots, to switch into run mode! That&#x27;s why it&#x27;s so big and messy, compared the elegant but impossible to construct real time crossing.<p><pre><code>          &lt;save
            name=&quot;Autoinitializing Exclusive Or&quot; 
            rows=&quot;28&quot; cols=&quot;40&quot;
            description=&quot;William R. Buckley&#x27;s autoinitializing exclusive-or is initialized by 11111 at each input.&quot;
          &gt;
    sstsb-sqqssssssssssssssssssssssssz--szsz
    y-z-b-wsw------------------------z--wzwz
    w-b-b-w-sqqsqsssssssqfqssqsssssz-z--wzwz
    y-z-b-qawsw----ssz--wsw--wsz---z-z--wzwz
    w-b-b-qww-----sq-sqzqqz--wqaa--z-z--wzwz
    y-z-z-w-qsq---wsqr-swwassz--w--z-z--wzwz
    w-b-z-qaw-zcqsqsqsqssqsq-ssqw--z-z--wzwz
    y-z-z-qww-zfw-zsqc-szzasqr-szssz-z--wzwz
    w-b-zsw-w-z-w-sq-szwqqw--zqaqq-z-z--wzwz
    yaa-sqz-w-q-w--sswswzsz--zsw-w-z-z--wzwz
    ------qsq-ssqsssssssqfqssqssqw-zsqz-wzwz
    zga-sqw-z-ssqsssssssqfqssqssqszsq-szwzwz
    b-y-wsz-z-wa---ssz--wsw--wsz--zwsqwzwzwz
    z-w-w-q-z--w--sq-sssqqz--wqaaazw-w-zwzwz
    b-y-w-z-z-qw--wsqr-wawassz---wzw-w-zwzwz
    z-w-w-q-qswcqsqsqsqssqsq-ssqswsw-w-zwzwz
    b-y-y-z-z--fw-zsqc-zazasqr-z---w-w-zwzwz
    z-w-y-z-z---w-sq-sqsqqw--zqa---w-w-zwzwz
    b-y-y-z-zsszw--ssw--zsz--zsw--qw-w-zwzwz
    z-w-y-z-sq-sqsssssssqfqssqssssww-w-zwzwz
    hstsy-z--sqsqsssssssqfqssqsssssw-w-zwzwz
    ------z-----z--ssz--wsw--wsz-----w-zwzwz
    ------z-----z-sq-sszqqz--wqaa----w-zwzwz
    ------z----fz-wsqr-swwasqc--w----w-zwzwz
    ------z----rqsqsqsqssqsq-sssw----w-zwzwz
    ------z----------------ssw-------w-zwzwz
    ------sssssssssssssssssssssssssssw-zwzwz
    -----------------------------------swsww
          &lt;&#x2F;save&gt;
</code></pre>
Buckley, p. 473 (&quot;rtco&quot; means &quot;Real Time Crossing Organ&quot;):<p>&gt;Auto-initialisation provides much more capability than that used in the rtco, the examples of clock synchronisation and trivial reconstruction being the simplest applications. Mechanisms used are signal sampling, portal closure, clock
synchronisation, and staged initialisation. Our implementation uses three separate start signals; a staged initialisation. Each clock of the rtco has a separate
auto-initialisation circuit. Signal to a stage is intercepted from a suitable path of
channel A, by an interposing confluent state, or portal, and directed to the pulser
of the adjacent auto-initialisation circuit by an auxiliary path. Pulser output is
directed to clock input; and to a special transmission path constructor, which
is addressed shortly. Clock signal for the entire organ is suitably synchronised,
as initialisation of the first clock pair occurs simultaneously upon input of the
first start pulse. All subsequent initialisations occur given knowledge of timing
for the first two clocks. In this way, synchronisation becomes a trivial concern.
Figure 17 shows the auto-initialisable rtco.<p>&gt;Fig. 17. The rtco, configured for auto-initialisation. The minimum start signal for this organ is 10^13 10^32 1, which is applied once to Ai. The organ begins crossing
signal 30 clock ticks later. This organ can be started at the time of construction; there is no start signal propagation. All signal crossing paths impose equal delay.
The organ has 18×18 dimensions. This configuration can be marginally reduced in area.