3 Von Neumann's Solution

John von Neumann and

1 Burks' Problem: Machine

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 .
- Now consider those machine types, which we shall call
*constructors*, which are capable of constructing*some*other (types of) machine. For any given let (``offspring of '') denote that subset of which is capable of constructing. is then a constructor precisely provided ; and--incidentally-- is self-reproducing provided . This relation, , induces a directed graph on ; 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
--call it .
- Let 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 .

Now consider the two (highly schematic) graphs shown in
Figure 1. In both cases I have shown the putative set
partitioned more or less coarsely by the complexity measure
. That is, the inner rings or subsets are those of small
(low complexity), while the outer, more inclusive rings or
subsets include machines of progressively greater (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.^{1}

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 ,
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

Copyright © 2000 All Rights Reserved.

Timestamp: 2002-11-07