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