Evolutionary Growth of Complexity:

Looking Backward,

Looking Forward...

**Barry McMullin
Research Institute in Networks and
Communications Engineering (RINCE)
Dublin City University
**

**ALife VII: August 2000
( FoilTeX
Presentation)**

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.

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

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

- Burks (1970):
... Clearly what is needed is a requirement that the self-reproducing automaton have some minimal complexity...

- 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.*

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!

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

Herman's Counter Example

- Herman (1973):
... Hence, there is a need for new mathematical conditions to insure non-trivial self-reproduction.

- Langton (1984):
Computational criterion too strong rather than too weak?

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

Langton's Counter Example!

- Langton (1984):

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

- 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 (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...

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

(Engineering)

(Biology)

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

(von Neumann)

- Is this the
*first*solution? - Is it the
*only*solution? - Is it the
*simplest*solution?

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

Science Foundation Ireland

(the*other* SFI...)

(the

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

**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.

- Full Paper:
- DCU Alife Laboratory:
- Research Institute for Networks and
Communications Engineering (RINCE):

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