John von Neumann and the
Evolutionary Growth of Complexity:
Looking Backward,
Looking Forward...

Barry McMullin
Research Institute in Networks and
Communications Engineering (RINCE)
Dublin City University
Barry.McMullin@dcu.edu

ALife VII: August 2000
(FoilTeX Presentation)

Burks' Problem:
Machine Self-Reproduction

• Kinematic Framework

• Cellular Framework (Ulam)
  • Discrete 2D Space/Discrete Time
  • Cells are 29 State FSM's
  • Automata are functional patterns of states over cells, embedded in the space.

Trivial Self Reproduction?

• Burks (1970):

  ... This result is obviously substantial, but to express its real force we must formulate it in such a way that it cannot be trivialized ...

Trivial Self Reproduction?

• Burks (1970):

  ... Consider, for example, a two-state cellular system whose transition function takes a cell into state one when any of its neighbors is in state one. Define an automaton to be any area, even a single cell. A cell in state one then reproduces itself trivially in its neighboring cells...

Trivial Self Reproduction?

• Burks (1970):

  ... Clearly what is needed is a requirement that the self-reproducing automaton have some minimal complexity...

Burks' Criterion:

• Burks (1970):

  ... This requirement can be formulated in a number of ways. We will do it by requiring that the self-reproducing automaton also be a [universal?] Turing machine.

But...
Herman's Counter Example

• Herman (1973):
  • 2D Cellular Framework
  • Cells combine trivial, crystaline, reproduction with universal turing machine head
  • Cells still simpler than in von Neumann model!

But...
Herman's Counter Example

• Herman (1973):

  ...What the result does show is that the existence of a self-reproducing universal computer-constructor in itself is not relevant to the problem of biological and machine self-reproduction...

But...
Herman's Counter Example

• Herman (1973):

  ... Hence, there is a need for new mathematical conditions to insure non-trivial self-reproduction.

Langton's Critique

• Langton (1984):

  Computational criterion too strong rather than too weak?

Langton's Criterion

• Langton (1984):
  • Non-trivial self reproduction characterised by separate processes of copying and decoding of a machine description.
  • Satisfied by von Neumann's design.

But...
Langton's Counter Example!

• Langton (1984):
  Langton's Loop automaton also satisfies this criterion - yet is clearly (?) trivial!

von Neumann's Criterion?

• von Neumann (1949) [Illinois Lectures]:

  ... One of the difficulties in defining what one means by self-reproduction is that certain organizations, such as growing crystals, are self-reproductive by any naive definition of self-reproduction, yet nobody is willing to award them the distinction of being self-reproductive...

von Neumann's Criterion?

• von Neumann (1949) [Illinois Lectures]:

  ... A way around this difficulty is to say that self-reproduction includes the ability to undergo inheritable mutations as well as the ability to make another organism like the original...

von Neumann's Problem:

• How can machines manage to construct other machines more ``complex'' that themselves, in a general and open-ended way--i.e., with the potential for unbounded evolutionary growth of complexity.

Degeneration of Complexity
(Engineering)

Growth of Complexity
(Biology)

von Neumann's Problem:

• Exhibit a class of constructing machines, spanning a wide range of complexities, such that the whole class is connected by the relative construction (mutation) network.
• For good measure, require that every machine in the class also be SR (every machine has a self construction loop). This is necessary (not sufficient) for Darwinian selection...

The General Constructive Automaton

$$(u_0 \oplus d(m)) \leadsto (m \oplus d(m))$$

Von Neumann SR: Minimal Case

$$(u_0 \oplus d(u_0)) \leadsto (u_0 \oplus d(u_0))$$

Von Neumann SR: Generic Case

$$((u_0 \oplus m) \oplus d(u_0 \oplus m)) \leadsto ((u_0 \oplus m) \oplus d(u_0 \oplus m))$$

Growth of Complexity
(von Neumann)

Looking Backward

• Is this the first solution?
• Is it the only solution?
• Is it the simplest solution?

Looking Forward

• Complexity?
• Individuality?
• Origins?
• Evolutionary growth of complexity?

Coda...

Science Foundation Ireland
(the other SFI...)

http://www.sfi.ie/

...multidisciplinary proposals in Biotechnology/ICT will be welcomed.

Bibliography

Burks, A. W. (1970),

Von Neumann's Self-Reproducing Automata, in A. W. Burks, ed., `Essays on Cellular Automata', University of Illinois Press, Urbana, pp. 3-64 (Essay One).

Herman, G. T. (1973),

`On Universal Computer-Constructors', Information Processing Letters 2, 61-64.

Langton, C. G. (1984),

`Self-Reproduction in Cellular Automata', Physica 10D, 135-144.

von Neumann, J. (1949),

Theory and Organization of Complicated Automata, in A. W. Burks, ed., `Theory of Self-Reproducing Automata [by] John von Neumann', University of Illinois Press, Urbana, pp. 29-87 (Part One).
Based on transcripts of lectures delivered at the University of Illinois, in December 1949. Edited for publication by A.W. Burks.

Related Online Resources

• Full Paper:
  • http://www.eeng.dcu.ie/~alife/bmcm-2000-01/

• DCU Alife Laboratory:
  • http://www.eeng.dcu.ie/~alife/

• Research Institute for Networks and Communications Engineering (RINCE):
  • http://www.rince.ie/

Copyright

This work is copyright ©2000 by Barry McMullin.

Permission is hereby granted to private individuals to access, copy and distribute this work, for purposes of private study only, provided that the distribution is complete and unmodified, is accompanied by this copyright notice, and that no charges are levied. The work may not be accessed or copied, in whole or in part, for commercial purposes, except with the prior written permission of the author.

All other rights reserved.

Copyright © 2000 All Rights Reserved.
Timestamp: 2000-08-16