Document: John von Neumann and the Evolutionary Growth of Complexity
3 Von Neumann's Solution
John von Neumann and
1 Burks' Problem: Machine

2 Von Neumann's Problem:
The Evolutionary Growth of Complexity

I propose to resolve this enigma in a rather different way.

Firstly, I fully agree with Burks that to appreciate the full force of von Neumann's work, we must understand what problem he was attempting to solve. In particular, if it should turn out that this problem can be solved by trivial means (Herman), or at least much simpler means (Langton), then we should have to conclude that it was not such a substantial achievement after all. Where I differ from these, and indeed, most other, commentators, is that I think it is a mistake to view von Neumann's problem as having been wholly, or even largely, concerned with self-reproduction!

Of course, this is not to deny that von Neumann did, indeed, present a design for a self-reproducing automaton. I do not dispute that at all. Rather, my claim is that this self-reproducing capability, far from being the object of the design, is actually an incidental--indeed, trivial, though highly serendipitous--corollary of von Neumann's having solved at least some aspects of a far deeper problem.

This deeper problem is what I call the evolutionary growth of complexity. More specifically, the problem of how, in a general and open-ended way, machines can manage to construct other machines more ``complex'' that themselves. For if our best theories of biological evolution are correct, and assuming that biological organisms are, in some sense, ``machines'', then we must hold that such a constructive increase in complexity has happened not just once, but innumerable times in the course of phylogenetic evolution. Note that this claim does not rely on any sophisticated, much less formal, definition of complexity; it requires merely the crudest of qualitative rankings. Nor does it imply any necessary or consistent growth in complexity through evolution, but merely an acceptance that complexity has grown dramatically in some lineages.

Why is this growth of complexity a problem? Well, put simply, all our pragmatic experience of machines and engineering points in the opposite direction. In general, if we want to construct a machine of any given degree of complexity, we use even more complex machinery in its construction. While this is not definitive, it is surely suggestive of a difficulty.

To make all this a little more concrete, imagine that we could exhibit the following:

• Let there be a large (ideally, infinite) class of machine ``types'' or ``designs''; call this $M$.

• Now consider those machine types, which we shall call constructors, which are capable of constructing some other (types of) machine. For any given $m \in M$ let $O(m)$ (``offspring of $m$'') denote that subset of $M$ which $m$ is capable of constructing. $m$ is then a constructor precisely provided $O(m) \neq \phi$; and--incidentally--$m$ is self-reproducing provided $m \in O(m)$. This relation, $O(m)$, induces a directed graph on $M$; by following arrows on this graph we can potentially see what machine types can, directly or indirectly, be constructed by other machine types.

• Let there be a crude (``vague, unscientific and imperfect'') measure of complexity on the elements of $M$--call it $c(m), m \in M$.

• Let $c(m), m \in M$ span a large (ideally, infinite) range, which is to say that there are relatively simple and relatively complex types of machine, and everything in between, included in $M$.

Now consider the two (highly schematic) graphs shown in Figure 1. In both cases I have shown the putative set $M$ partitioned more or less coarsely by the complexity measure $c$. That is, the inner rings or subsets are those of small $c$ (low complexity), while the outer, more inclusive rings or subsets include machines of progressively greater $c$ (higher complexity). The graph on the left indicates our ``typical'' engineering experience: all constructional pathways lead inward (from more complex to less complex). As a result, complexity will always, and unconditionally, degenerate in time. Conversely, the graph on the right indicates the abstract situation posited by our best current theories of biological evolution: at least some edges of the graph (constructional pathways) lead from the inner rings to their outer neighbors. Provided there are sufficient such pathways, then, starting from only the very simplest machines (or organisms), there will be potential constructional pathways whereby even the most complex of machines can eventually be constructed (in time). Thus complexity might grow in time.¹

The problem which this presents is to show that the experience and intuition underlying the graph on the left is mistaken; to show, in other words, how the situation on the right might in fact be realised.

What would it take to solve this problem, even in principle? Well, one would need to exhibit a concrete class of machines $M$, in sufficient detail to satisfy ourselves that they are purely mechanistic; one would need to show that they span a significant range of complexity; and finally, one would have to demonstrate that there are constructional pathways leading from the simplest to the most complex (there may, or may not, also be pathways in the other direction, but that is not the point at issue--or at least, not immediately).

I believe that this is precisely the problem which von Neumann set out to solve. Furthermore, it seems to me that he did, indeed, solve it; and that it is only by seeing his work in this light that its ``real force'' can be understood.

3 Von Neumann's Solution
John von Neumann and
1 Burks' Problem: Machine
Document: John von Neumann and the Evolutionary Growth of Complexity

Copyright © 2000 All Rights Reserved.
Timestamp: 2002-11-07