next up previous contents
Next: Implicit versus Explicit Encoding Up: Self-Reproduction and Open-Ended Evolution Previous: Trivial versus Non-Trivial Reproduction

Genetic Reproduction versus Self-Inspection

Von Neumann's architecture was designed specifically to allow for a possible increase in complexity and efficiency of machines by evolution. However, even if we accept that his design is a solution to this problem, it is by no means the only conceivable solution, as von Neumann himself was well aware. In particular, he also discussed the possibility of a machine which built a copy of itself by actively inspecting its parts, without the need for this design information to be duplicated on a tape (i.e. without a `genetic' description). Indeed, systems which reproduce by self-inspection have been designed by Laing, e.g. [Laing 77], and by Ibáñez and colleagues [Ibáñez et al. 95].

Although he certainly did not prove that reproduction by self-inspection could not support open-ended evolution, von Neumann did suggest a number of reasons why his genetic architecture would be a more powerful and more general design for this purpose. First of all, as mentioned in Section 3.2.1, he noted that the essential feature which allowed his automata to overcome the otherwise seemingly valid rule that machines are necessarily superior (in size and in organisation) to their output, was that they contained a general copying automaton B, which was capable of copying any linear tape [von Neumann 66] (p.121). Although B is of fixed, finite size, it is able to copy a tape of any size. Now, this action of copying a tape is essentially reproduction by self-inspection, but this is generally a straightforward task for a linear tape. The major problems arise when trying to copy a two- or three-dimensional structure by the same method, for example in specifying the precise spatial relationships between parts.

Von Neumann also pointed out that self-inspection requires that we have a representation which is `quasi-quiescent' in the sense that it can be read (for the purposes of copying and possibly for interpretation) without being essentially disturbed. With a separate genetic description, we only require that this description is quasi-quiescent, but copying by self-inspection would require that the whole structure to be copied would have this quasi-quiescent property. In general, however, most machines would not have this property, nor would we want to restrict ourselves to only considering those machines which did. In conclusion, von Neumann says:

``To sum up, the reason to operate with `descriptions' ... instead of the `originals' ... is that the former are quasi-quiescent (i.e. unchanging, not in an absolute sense, but for the purposes of the exploration that has to be undertaken), while the latter are live and reactive. In the situation in which we are finding ourselves here, the importance of descriptions is that they replace the varying and reactive originals by quiescent and (temporarily) unchanging semantic equivalents and thus permit copying. Copying, as we have seen above, is the decisive step which renders self-reproduction (or, more generally, reproduction without degeneration in size or level of organization) possible.'' [von Neumann 66] (pp.122-123).

From a biological perspective, Waddington has made the same point. While discussing possible reasons for the universal adoption of genetic architectures for self-reproduction by biological life, he suggested that the issue ``is presumably related to the problem [of] how to combine a store which is unreactive enough to be reliable, with something which interacts with the environment sufficiently actively to be `interesting' '' [Waddington 69] (p.118).

As to the nature of the information encoded on the tape, von Neumann suggested that ``it is better not to use a description of the pieces and how they fit together, but rather a description of the consecutive steps to be used in building the automaton'' [von Neumann 49] (p.486). In other words, the information should be in the form of a developmental `recipe' rather than a `blueprint'. The advantages of this kind of genetic description have also been discussed by many biologists (e.g. [Dawkins 82] pp.177-8 & pp.250-264, [Maynard Smith 86] pp.21-23). From an evolutionary point of view, one of the most important features of the developmental approach is that it allows mutations on the genotype to have a wide range of magnitudes of phenotypic effect. For example, mutations affecting the early developmental process can potentially lead to gross macroscopic changes in phenotype, whereas those affecting later stages can have the effect of `fine-tuning' particular structures. Furthermore, if there is a degree of modularity in the developmental process, then these mutations have some chance of `making sense' from the point of view of the overall design of the organism (see the quotation from Waddington on p.[*]). For example, a mutation affecting the development of the spine in a vertebrate could conceivably result in the formation of an extra vertebra.

McMullin has pointed out that von Neumann's genetic architecture also effectively decouples the geometry of the variational space of the reproducers (i.e. the space of the genetic tapes) from the peculiarities of the environment in which they exist (i.e. the space of the phenotype), and in this way allows the possibility of a mutational pathway linking large numbers of viable reproducers [McMullin 92a] (pp.191-193). In addition, recall from Section 3.2.1 that the architecture will accept any tape of the general form φ[A + B + C + D], where A is a general constructing automaton, B is a general copying automaton, C is a control automaton, and D is any other automaton with arbitrary function. Assuming the the description of D on the tape can be separated from the description of A, B and C,7.9 this design guarantees that mutations which affect the part of the tape describing automaton D will not interfere with the reproductive capacity of the machine. Machines which reproduce by self-inspection would generally not be certain to have this localisation property. This being the case, we would not always be able to say that there was a particular section of the machine which could be disrupted by mutation without interfering with the machine's ability to reproduce.

Now, in the context of the experimental portion of this thesis, and of Tierra-like platforms in general, it is interesting to ask whether the programs in these systems reproduce according to von Neumann's genetic architecture or rather by self-inspection. As the arguments of the previous paragraphs suggest that a marked difference exists in the evolutionary potential of these two methods, it is an important question, but it has not received much discussion in the literature. McMullin argued that these programs are reproducing by self-inspection [McMullin 92a] (p.200). Ibáñez and colleagues appear to agree [Ibáñez et al. 95] (p.574).7.10

In contrast, I would like to suggest that they can sensibly be analysed in terms of von Neumann's genetic architecture. Before getting into this topic, it should be noted that the terminology commonly used to describe reproducers in Tierra-like systems is somewhat different to that used for von Neumann's work. Because of the similarity between Tierra-like operating systems and those of standard digital computers, the actions of Tierran reproducers are often referred to as computations rather than constructions, even when a reproducer is in the process of building a new copy of itself. Additionally, the terms `program' or `algorithm' are generally used instead of `machine' or `automaton'. These may seem trivial issues, but the different terminology can lead to confusion when comparing the two architectures. In the following, also remember that von Neumann's general constructing automaton A is the machinery which interprets the tape to produce a new machine (phenotype), and the general copying automaton B copies the tape uninterpreted.

At first sight it might seem that there is no separate genetic description of the program in a Tierra-like system. The picture is complicated by the fact that the machinery which interprets the program (i.e. automaton A) does not reside in the same part of the computer in which the program itself is stored. The state information for this machinery--a program's `virtual CPU' (i.e. the instruction pointer, stacks, registers, etc.)--is generally represented in an independent area of memory to the program's instructions. Furthermore, the actual `interpreting machinery' of the virtual CPU is encoded in the global operating system provided by the platform, and is in this sense implicit in the program's environment. Additionally, the control automaton C, which controls when the instructions in the program are executed, is also implicit in the part of the operating system which governs mechanisms such as how a program's instruction pointer is updated after the execution of each instruction. All that is left to be explicitly encoded by the program, therefore, is the copying automaton B, and potentially any other arbitrary automaton D.

Now, the instructions which make up the program exist in an unreactive state in the system's random-access memory. It is only when the control automaton C transfers instructions to the interpreting automaton A that they become `active'. Looked at in this way, we can see that it is the behaviour of the program (including looping, jumping around the code, etc.) that is the result of automaton A interpreting the unreactive genetic description. This behaviour, or computation, is therefore the equivalent to the constructed machine, or phenotype, in von Neumann's design.7.11 The string of instructions residing in the random-access memory (which is normally referred to as the program) can now been seen as nothing more than the tape or genetic description of this phenotype. It is perhaps easier to see the distinction if one considers a parallel program, with multiple processes (with different state information) using the same program listing.

I therefore suggest that a self-reproducing program in a Tierra-like system is consistent with von Neumann's architecture. However, as automata A and C are largely implicit in the environment in which the programs reside (the only explicit representation being the state information in a program's virtual CPU), and are certainly not encoded by the individual programs, we can see that the `program', in the sense of a string of instructions in the system's random-access memory, corresponds to the tape φ[B + D] in von Neumann's scheme.

The situation is complicated not only because the interpretation machinery resides partly implicitly in the environment, and partly in a different area of memory, but also for (at least) two further reasons. First, I am claiming that the string of instructions comprising the `program' in random-access memory should be viewed as the genetic tape in a von Neumann style self-reproduction architecture. Now, von Neumann pointed out that the process of copying the tape in his automaton was essentially itself a process of self-inspection. In this sense, Tierran programs do reproduce by self-inspection. However, the overall mechanism for reproduction, including the implicit encodings of the interpretation and control automata, fits in with von Neumann's architecture, in which the copying of the tape by self-inspection is an integral feature. The major consequence of this is that programs in Tierra-like systems should, all else being equal, have similar evolutionary potential to von Neumann's self-reproducing automata, because extra instructions can be added to the end of the `tape' and subject to mutations. As long as the mutations do not affect that part of the tape which encodes the self-reproduction algorithm, they will be inherited without disrupting the capacity of the program to reproduce.

A second source of complication concerns the way in which information is encoded on the tape of a reproducing program in a Tierra-like system. The statement in the previous paragraph about the evolvability of such programs was qualified by the phrase ``all else being equal''. Now, as already mentioned, von Neumann claimed that it would be better to store the information of how to build the machine as a recipe rather than a blueprint. The description of the behaviour of a computer program by that program's listing (i.e. its tape) falls somewhere in between these two alternatives. It is not a straightforward blueprint in the sense of a one-to-one mapping to the program's behaviour (phenotype), because it involves things such a looping, branching and conditional execution. However, these features are fairly transparent in the program's tape (at least if we restrict ourselves to a serial rather than a parallel program). This being the case, single mutations will usually have a rather small effect on the program's behaviour. Only if we start considering the development of a multi-process parallel program from a single-process `egg' would mutations have the potential for changing both coarse-level and fine-level details of the programs, thereby allowing for the sorts of benefits, from an evolutionary point of view, discussed earlier (p.[*]).

next up previous contents
Next: Implicit versus Explicit Encoding Up: Self-Reproduction and Open-Ended Evolution Previous: Trivial versus Non-Trivial Reproduction
Tim Taylor