josh@cs.rutgers.edu (03/05/91)
Announcing the Great Sci.Nanotech Self-Reproducing Program Contest!
In order to motivate people to think about mechanisms of self-reproducing
automata, sci.nanotech is holding a contest. Write a self-reproducing
program and mail it to nanotech@planchet.rutgers.edu (or post it, which
amounts to the same thing).
A self-reproducing program is one which prints out its own text.
There are lots of ways to cheat, as in "foo.c":
main(){char x[70];read(open("foo.c",O_RDONLY),x,70);write(1,x,70);}
It's also considered cheating to use a self-evaluating constant in
APL or LISP:
0
The simplest (non-cheating) method most often used is to come up with
some string that unfolds into the text of the program that prints it
when some simple "unfolding" operation (e.g. printing it twice) is done.
More generally, and more applicable to nanotech assemblers (and cells),
is the method developed by von Neumann:
Design a machine B which builds things given a description. If d(X) is
a description of X, B(d(X)) = X. Another machine C simply copies
descriptions: C(d(X)) = d(X). Now the self-reproducing machine is
the system (B,C,d(B,C)). "System" means there's enough control and
framework there to hold everything together and apply both machines
to the "tape".
The contest is open all through March; I will announce results
(and post all entries) in early April.
Have Fun!
--JoSH
ps: extra credit--explore encodings on the "tape" that make the
Hamming distance between syntactically correct programs as small
as possible.