5 Evolvability: A Closer

John von Neumann and

3 Von Neumann's Solution

While the designation of a distinct field known as
*Artificial Life* is comparatively recent
[10], I would argue that, looking
backwards, it is clear that von Neumann's work properly defines
its origin and inspiration. If the formulation above of von
Neumann's problem--and his solution to it--is accepted, then a
proper assessment of his contribution to the field he effectively
founded presents at least three distinct questions:

- Was von Neumann
the
*first*one to solve his problem? - Has von Neumann presented
the
*only*known solution to his problem? - Is von Neumann's
solution the
*simplest*known?

My answer to question 1 is clearly an unambiguous ``yes''; and it
stands as von Neumann's remarkable achievement *both* to
have formulated this foundational problem *and* to have
actually succeeded in solving it.

Question 2 is slightly more difficult. Given than von Neumann's problem situation has been poorly understood, it follows that subsequent contributors have not generally articulated clearly the relation between their work and this problem.

However, I do not hesitate to say that
Thatcher [20], Codd [6]
and Pesavento [15] have all offered
alternative, or at least significantly refined, solutions.
Thatcher provided a somewhat simplified design for the basic
general constructive automaton , in the *same* CA space
as defined by von Neumann. Codd defined a significantly simpler
CA space, which could still accommodate a functionally equivalent
general constructive automaton. Much more recently, Pesavento has
demonstrated a substantially simplified design for in a CA
space marginally more complicated than von Neumann's; and,
further, has actually demonstrated a functioning simulation of
this complete .
Because these three systems are so very closely related to von
Neumann's it follows that they are at least equally satisfactory
in solving his problem.

Conversely, as already indicated, I think we can be clear that
Langton's ``self-replicating loop'' system [9]
does *not* qualify as an alternative solution to von
Neumann's. Although it was derived from Codd's earlier system,
and although Langton exhibits a self-reproducing configuration
(involving ``copying'' and ``decoding'') this does not embody
anything like a ``general constructive automaton'' and therefore
has little or no evolutionary potential.

Another possible candidate solution to von Neumann's problem
might be that of Berlekamp et al. [1]. There it is
claimed that a general constructive automaton, of comparable
functionality to von Neumann's , can be realized in Conway's
well known ``Game of Life'' (GOL) CA. This arguably takes Codd's
(and thus von Neumann's) result to some kind of limiting case, as
the GOL cells have the absolute minimum of only 2 states. On the
other hand, in contrast to the fully detailed designs for
presented by Thatcher, Codd and Pesavento, Berlekamp et. al.
provide only a very sketchy outline to indicate the
*possibility* of an equivalent automaton in GOL. Moreover,
because GOL is so radically simplified (as a CA) it would not be
quite trivial to establish that it supports embedded automata of
comparable range of ``complexity'' to those of Von Neumann etc.

This last issue affects the comparative evaluation of certain
other systems even more seriously. I have in mind particularly
`Tierra` [17] and related systems.

`Tierra` is, roughly, a shared memory parallel computer, with
fairly simple ``von Neumann style'' processors.^{4} Ray has exhibited
processes (embedded ``machines'' or ``automata'' in von Neumann's sense)
in this framework which are capable of self-reproduction; and
which, moreover, exhibit clear and significant evolutionary
change. However, because the `Tierra` system is so very
different in style from von Neumann's (or, indeed, *any* CA
of 2 or more dimensions), it is very difficult to make even
informal and qualitative comparisons of automata ``complexity''
between these systems.

I also have another quite different, and perhaps more important,
misgiving about whether `Tierra` should be regarded as offering an
equally satisfactory alternative solution to von Neumann's problem.

I originally expressed this reservation by stating that `Tierra`
uses ``... a form of self-reproduction based on self-inspection
(rather than a properly genetic system in the von Neumann
sense)'' [12, Chapter 4]. The
implication was that the self-reproducing entities in `Tierra`
lack the important distinction between ``copying'' and
``decoding''--and that this perhaps affects evolutionary
potential in the system. However
Taylor [19] has since persuaded me that
this way of presenting the matter is, at best, unclear.

It might be more precise to say that `Tierra` *does*
incorporate a distinction between copying and decoding processes:
but that the ``decoding'' is represented by the execution of
instructions by the `Tierra` processors. Thus, the decoding is
hard-wired, whereas, in von Neumann's system, the decoding is
itself a product of the specific design of , and, as such,
is at least *potentially* mutable. In this way, von
Neumann's system allows for what I have called *Genetic
Relativism* [12, Chapter 4],
where the actual ``decoding'' map can itself evolve. It seems to
me that this allows for a more profound form or degree of
evolvability in von Neumann's system compared to `Tierra`.

Now this is an idea which von Neumann himself seems to have recognised, but discounted. He explicitly asserted that mutations affecting that part of a descriptor coding for would result in the production of ``sterile'' offspring [23, p. 86]--and would thus have no evolutionary potential at all. Clearly, on this specific point, I disagree with von Neumann, and consider that he actually underestimated the force of his own design in this particular respect. Accordingly, I will explore this issue in more depth in the following section below.

As to my question 3 above--whether von Neumann's solution is the
``simplest''--this clearly does not admit of a clearcut answer,
given the informality of our notions of simplicity and
complexity. Certainly, the alternative solutions of Thatcher,
Codd and Pesavento can all be said to be *somewhat* simpler
in at least some respects. Similarly, if the outline design of
Berlekamp et. al. is accepted then it is *much* simpler in
one particular dimension (the number of cell states).
Nonetheless, in considering the overall development of the field
I would say that none of these ``simplifications'' either
undermine, or significantly extend, von Neumann's seminal
results.

5 Evolvability: A Closer

John von Neumann and

3 Von Neumann's Solution

Copyright © 2000 All Rights Reserved.

Timestamp: 2002-11-07