really simple computers

[Kragen Sitaker]

Some time ago, I heard a rumor that someone had shown that a single OR
gate and an arbitrary number of delay elements sufficed to build a
universal computer.  (Miles Murdocca, at Bell Labs, in an unpublished
paper, between 1983 and 1993, according to an article by J. Storrs
Hall in "Extropy", #10, vol. 4, no. 2, Winter/Spring 1993, entitled,
"Nanocomputers: 21st century hypercomputing".)  I haven't seen this
proof, unfortunately.

Accepting Wolfram's assertion that rule 110 is a universal cellular
automaton, capable of simulating any 1-d CA (and therefore a Turing
Machine), building a rule-110 CA should suffice to build a universal
computer.  (I think he might have included a proof of his assertion in
his recent book.)  We can build a finite-space version of rule 110
with seven NAND gates and three delay lines, as follows.

If you join the two ends of your cell-space together, you get a
cylindrical sort of spacetime; this is a common strategy for
implementing CAs on finite machines without getting ugly edge-effects.
If you adjust your spacetime a bit so that each spacelike row meets
its predecessors and successors end to end, so that your cylinder is a
little bit askew, you can traverse the entire cylinder in a single
spacelike path that spirals around and around it.  A simple automaton
that zooms down this path, reading the cells on the previous row to
write cell states on the current row, can execute rule 110.

Suppose you have a combinatorial circuit that reads the requisite
three one-bit inputs and produces the one-bit output rule 110 calls
for.  (You can build such a circuit quite easily; if A, B, and C are
the inputs, with B as the middle input --- the previous state of the
current cell --- then let E = -(B*B) (that is, B NAND B, or just NOT
B), and calculate the output as -(-(-(E*-(A*A))*-(C*B))*-(E*C)).  I
felt sure I could do it in six NAND gates, but after trying
unsuccessfully for a while, I wrote a program to try all the
six-gate-and-less combinations.  None of them work.)

Now, drive a laser from the output of this combinatorial circuit.
Feed it into a long single-mode fiber, which serves as a delay line.
Split this light into three paths; the longer path should be, say, one
nanosecond longer than the medium, while the shorter path should be
one nanosecond shorter.  These three paths (perhaps with some clocking
or latching, to compensate for light spreading out in the fiber)
provide the inputs to the combinatorial circuit.

Now we have our spiral spacetime cylinder, as described above, but
instead of the automaton zooming around it calculating new cell
states, it's rotating --- screwing --- through our stationary
automaton at the fiber's speed of light.

Initialization, input and output are somewhat troublesome; it seems
likely that they will require much more complication than the actual
processing itself.

-- 
<kragen@pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
Edsger Wybe Dijkstra died in August of 2002.  The world has lost a great
man.  See http://advogato.org/person/raph/diary.html?start=252 and
http://www.kode-fu.com/geek/2002_08_04_archive.shtml for details.