Document: John von Neumann and the Evolutionary Growth of Complexity

next 5 Conclusion: Looking Forwards
up John von Neumann and
previous 3 Von Neumann's Solution

4 Looking Backwards

While the designation of a distinct field known as Artificial Life is comparatively recent (Langton, 1989), 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:

  1. Was von Neumann the first one to solve his problem?

  2. Has von Neumann presented the only known solution to his problem?

  3. 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 (1970), Codd (1968) and Pesavento (1995) have all offered alternative, or at least significantly refined, solutions. 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.

Thatcher provided a somewhat simplified design for the basic general constructive automaton $u_0$, 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 $u_0$ in a CA space marginally more complicated than von Neumann's; and, further, has actually demonstrated a functioning simulation of this complete $u_0$.

Conversely, as already indicated, I think we can be clear that Langton's ``self-replicating loop'' system Langton (1984) does not qualify as an alternative solution to von Neumann's. Although it was derived from Codd's earlier system, and although he 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. (1982). There it is claimed that a general constructive automaton, of comparable functionality to von Neumann's $u_0$, 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 $u_0$ 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 (Ray, 1992) and related systems.

Tierra is, roughly, a shared memory parallel computer, with fairly simple ``von Neumann style'' processors.4 Ray has exhibited processes (``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)'' (McMullin, 1992, 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 (1999) 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 $u_0$, and, as such, is at least potentially mutable. In this way, von Neumann's system allows for what I have called Genetic Relativism (McMullin, 1992, 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. Having said that, I should also note that von Neumann himself seems to have discounted this idea. He stated explicitly that mutations affecting that part of a descriptor coding for $u_0$ would result in the production of ``sterile'' offspring (von Neumann, 1949, 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.

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.

next 5 Conclusion: Looking Forwards
up John von Neumann and
previous 3 Von Neumann's Solution

Document: John von Neumann and the Evolutionary Growth of Complexity

Copyright © 2000 All Rights Reserved.
Timestamp: 2001-01-03