levison@qucis.UUCP (Mike Levison) (01/08/88)
Self-replicating Programs
[Apologies. The following has little to do with Pascal, but
the rest of the discussion has appeared here.]
Some contributors seem to be missing the forest for the
trees. There is no pressing worldwide demand for a
production version of the program. It is of theoretical
interest only, and the only part of any significance is the
mechanism which permits the self-reproduction.
The quotemark problem may be "the only hard problem", but so
long as a solution exists (and there are many), it is of
little importance. Nor does it matter that the program works
with both EBCDIC and ASCII terminals, or that one version is
shorter or faster than another.
The problem, expressed in another form, seems to have
originated with John von Neumann over 30 years ago. The
motivation was to investigate the mechanisms necessary for
self-reproduction. His argument (rather freely paraphrased,
since I don't have the original to hand) runs as follows:
(1) We can readily build a machine to make one-inch hex bolts.
(2) We can also build a machine to make machines which make
one-inch hex bolts.
(3) We can, furthermore, build a machine to make machines
which make machines which ...
The question is: is there a means of terminating this
infinite sequence of machines each more complex than the one
before? In short, can we construct a machine which makes a
copy of itself?
To help in the solution, von N proposes a "universal"
constructor. This machine, given the blueprint of a machine,
is to construct the machine described by it. And now the
central question becomes: how can we have a blueprint
describe how to build BOTH the universal constructor AND a
copy of the blueprint itself.
The crucial insight is that the second is not in fact
necessary; that rather than have the blueprint describe how
to construct the pieces of the blueprint, we may simply use
a different mechanism, a copying mechanism, to obtain the
blueprint copy. In effect, the universal constructor
contains a photocopier. The blueprint describes how to build
constructor plus copier, and the copier (in the parent
machine) is used to make the copy of the blueprint.
All of the programs proposed here have used this blueprint/
chromosome mechanism in some form or another. An interesting
question is whether this mechanism is actually necessary for
non-trivial self-reproduction, or whether some quite
different approach is possible instead. (I have no idea
whether the answer is known.) If an alternative does exist,
one might expect to encounter organisms which reproduce
by some means other than DNA.
Actual designs for a self-reproducing automaton, or rather
for the universal constructor, were proposed by von Neumann
himself (aside from one technical problem solved by a later
researcher), and more elegantly by E.F. Codd ("Cellular
Automata", ACM Monograph, 1968).jik@athena.mit.edu (Jonathan Isaiah Kamens) (01/10/88)
If you want to get a [somewhat fanciful] look at the way von Neumann
machines work, you might want to take a look at a book of short
stories [Science Fiction] by David Brin. Unfortunately, I can
remember neither the name of the book nor the name of the story, but I
think that Brin has only published one book of stories, so if you can
go to a good SF library and look under Brin, you will find it.
The story is about interstellar probes which replicate using the von
Neumann scheme. It really is very interesting.
-=> Jonathan I. Kamens | "There is no expedient to which man will not go
MIT '91 | to avoid the real labor of thought."
jik@ATHENA.MIT.EDU | -- Thomas Alva Edison