[comp.lang.pascal] self-replication

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