WHAT  HIST  SEARCH  CHAOS  END  BIB

Artificial Life: A Brief History of Alternate Universes

Nathaniel Wesley Filardo

March 10, 2011

1 / 25

Outline

What is Artificial Life? Early History Searching with Genetics Let Chaos Reign Final thoughts Bibliography

2 / 25

What is Artificial Life? What is life, anyway?

• Now if that isn’t a heading, I don’t know what is.

• Let’s define life as

iterated high-fidelity auto-catalysis from environmental resources

• For life to be interesting, there should be some noise.

• For the purposes of this talk, viruses are alive: they auto-catalyse within their environment, a host cell.

3 / 25

What is Artificial Life? So… “artificial”?

• An alternative, “unnatural” biology.

• Not:

• A dicussion of our social lives.

• Theology (“supernatural biology”).

• Simulation of “real” biology (e.g. in silico, bioinformatics, …).

• Biochemical tricks with “real” biology.

• A simplified, mathematical environment.

• A grid of colored graphs and node state transition functions.

• A reified P-SPACE Automaton.

• A collection of interacting P-SPACE Automata.

• …

4 / 25

Early History

The first thing to emerge that might be called “artificial life” (probably as with the real thing) are artificial auto-catalytic compounds. The first auto-catalyzers emerged as

• cellular automata (“colored graphs”)

• computer programs Note that these are not generally robust to noise or resource scarcity.

5 / 25

Early History Cellular Automata

• 1940s : John von Neumann creates a universal construction for replicators. His uses 29 colors and 29^{5} transition rules [14].

• Universal here means “can build any realizable structure given a description.”

• In 1995, the first computational implementation of the construction was published using 32 states [11].

• In 2008, Neumann’s original design was realized [2].

6 / 25

Early History Cellular Automata

A von Neumann machine (32-state version; from Wikipedia):

7 / 25

Early History Cellular Automata

1970: John Conway invents Life (2 states, 8-neighbor, rules based on population only [7]):

Image from [5]. ^{8 / 25}

Early History Cellular Automata

1984 : Christopher Langton creates his iconic CA (not a universal constructor). (Picture credit [9].)

9 / 25

Early History Cellular Automata

CAs can be Turing complete. • Trivial encoding (but huge number of states).

• 1D rule 110 [4].

• Langton’s ant (1986 [8], universality proven in 2000 [6]) and other “Turmites.”

• Perrier loop (1996 [10]) adds a stack and tape to Langton’s loop.

• Conway’s Life is complete [3].

10 / 25

Early History Computer programs

• 1971 : Creeper “virus” (Bob Thomas, BBN) spreads across the ARPANET (picking itself up and moving from one TENEX/PDP-10 to the next).

• 1981 : Elk Cloner virus for Apple II systems. Floppy BSI.

• 1986 : ©Brain virus for PC/X86. Floppy BSI, escaped its intended role as an anti-piracy measure.

• 1988 : Morris worm runs wild on the Internet. Chiefly exploits bugs in sendmail. Portable across 4BSD/VAX and Sun-3 machines.

11 / 25

Early History Summary

It would be wrong to say that these ecosystems have no mutation (for CAs, see [13, 12]) or competition, but

• Mutation often manual (e.g., programmer, user).

• Mutation often immediately, catastrophically fatal.

• Especially in CAs, a point mutation can cause the whole environment to become chaotic.

• Real-world ISAs are designed assuming no noise.

12 / 25

Searching with Genetics

What if I want to search within the space of all… • strings?

• images?

• programs? for some thing I like. These spaces are huge!

13 / 25

Searching with Genetics

One way to do the search would be… • Have a large population of samples.

• Score each sample with a fitness function.

• Cull the lowest ranked.

• Generate some new samples. All pretty clear except the last bit. Generate

• At random?

• From some “smoothed” estimate?

• As a “neighbor” of an extant sample?

• From a set of extant samples?

14 / 25

Searching with Genetics Karl Sims

• Artist-in-residence at Thinking Machines, in the late 80s, uses manually selected evolution to evolve plant-like structures in an alternate biology.

• Goes on to evolve images (1993).

15 / 25

Let Chaos Reign

• Samples do not really interact with their environment

• They’re just descriptions of a point in the space

• Or with each other

• Even if we’re breeding them together

16 / 25

Let Chaos Reign

• Change the model!

• Make each sample consider others as environment.

• Introduce a notion of “acting” samples.

• Like a running program!

• Need some kind of sensors and actuators…

17 / 25

Let Chaos Reign Core Wars

• Concurrent with Langton’s loops (1984), Core Wars (and its programming language of Redcode) is introduced.

• A game for (really geeky) programmers.

• Goal: write a program to kill other programs.

• Redcode is designed for this environment:

• Abstract instructions ensure well-formedness.

• All of memory is instructions (including data).

• Relatively address everything, memory is circular.

• Can read & write anywhere.

• An odd idea of SMP/“instruction pointers.”

18 / 25

Let Chaos Reign Tierra

• Early 1990s, a biologist Thomas Ray, has an idea.

• Similar idea to Core Wars:

• Programs in “soup” of instructions.

• Read, write anywhere.

• Unlike Core Wars:

• Programs age to death. (Stall death by executing.)

• Errors: random soup, copy, and execution.

• Takes about 60 instructions to faithfully copy.

• Initial program is 80.

19 / 25

Let Chaos Reign Tierra

• A quirk: programs search for marked locations using

(NOP) templates.

• My beginning looks like this; where is it?

• My end looks like this; where is it?

• The beginning of my copy loop looks like this; jump there.

• …

• The cell division point looks like this; jump there.

• Anybody see what might go wrong in an interesting way?

• What happens if these templates change or go away?

• I’ll find somebody else.

20 / 25

Let Chaos Reign Parasitism in Tierra

• What does somebody else have that I might want?

• A copy loop, maybe?

• So now that I’ve found a copy loop…

• Jump there!

21 / 25

Let Chaos Reign Parasitism in Tierra

• Tierra was in no sense designed to support parasitism.

• “It just happened”

• Open-ended evolution.

• Also “just happened”:

• Genetic crossover (two parents copying atop each other).

• Immunity (trade efficiency for non-hijackability).

• Punctuated equilibrium.

22 / 25

Let Chaos Reign Sex in Tierra

• Well, maybe just “social reproduction”.

• Similar mechanisms to parasitism:

• “My partner looks like this; where is it?”

• Evolved from immune programs as a way of shortening the time taken to copy.

23 / 25

Let Chaos Reign Avida

• A derivative of Tierra, with goal of “evolve software”.

• Higher level of abstraction: replace soup with set of cells.

• Explicit means for code injection.

• Simulated “external I/O.”

• External objective function:

• Reward for doing a get.

• Reward for doing two gets and a put.

• Reward if that computes addition.

• …

24 / 25

Final thoughts

• AL is a bottom-up attempt at studying a mathematical model of biology.

• Contrast AI’s top-down approach to creating intelligence.

• Many other systems not discussed here.

• Including hybrid evolutionary neural nets like PolyWorld

[15] or AL [1].

• Open-ended evolution thus far usually isn’t:

• After a while, the system does settle down.

• Think of it as an engineering challenge.

25 / 25

D. Ackley and M. Littman. Interactions between learning and evolution.

W.R. Buckley. Signal crossing solutions in von Neumann self-replicating cellular automata. Automata-2008: Theory and Applications of Cellular Automata, page 453, 2008.

Paul Chapman. Life universal computer, 2002.

Available from: http://www.igblan.free-online.co.
uk/igblan/ca/.

M. Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1–40, 2004.

25 / 25

Steve Eddins. Lookup tables for binary image processing – Conway’s Game of Life, May 2008.

Available from: http://blogs.mathworks.com/steve/
2008/05/20/lookup-tables-conway-game-life/.

A. Gajardo, A. Moreira, and E. Goles. Complexity of langton’s ant. Discrete Applied Mathematics, 117(1-3):41 – 50, 2002.

Available from: http://www.sciencedirect.com/

science/article/B6TYW-45028GK-4/2/

f9d0c0da4a7d114c0c8862323900200b,
doi:DOI:10.1016/S0166-218X(00)00334-6.

Martin Gardner. Mathematical games.

25 / 25

Scientific American, 1970.

Christopher G. Langton. Studying artificial life with cellular automata. Physica D: Nonlinear Phenomena, 22(1-3):120 – 149, 1986. Proceedings of the Fifth Annual International Conference.

Available from: http://www.sciencedirect.com/

science/article/B6TVK-4CVPV04-C/2/

5ebc1d808142c87d9351747e7523273f,
doi:DOI:10.1016/0167-2789(86)90237-X.

Steven Levy. Artificial life: The quest for a new frontier. New York, New York: Pantheon, 1992.

Jean-Yves Perrier, Moshe Sipper, and Jacques Zahnd.

25 / 25

Toward a viable, self-reproducing universal computer. Physica D: Nonlinear Phenomena, 97(4):335 – 352, 1996.

Available from: http://www.sciencedirect.com/

science/article/B6TVK-3VSFD79-20/2/

0111100f4c2c5a4a14c5395e95bc4e4e,
doi:DOI:10.1016/0167-2789(96)00091-7.

Umberto Pesavento. An implementation of von neumann’s self-reproducing machine. Artificial Life, 2(4):337–354, 1995.

Available from: http://www.mitpressjournals.org/
doi/abs/10.1162/artl.1995.2.4.337,
doi:10.1162/artl.1995.2.4.337.

Chris Salzberg and Hiroki Sayama.

25 / 25

Complex genetic evolution of artificial self-replicators in cellular automata. Complexity, 10(2):33–39, 2004.

doi:10.1002/cplx.20060.

H. Sayama. Toward the realization of an evolving ecosystem on cellular automata. In Proceedings of the Fourth International Symposium on Artificial Life and Robotics (AROB 4th99), pages 254–257, 1999.

John von Neumann and Arthur W. Burks. Theory of Self-Reproducing Automata. University of Illinois Press, 1966.

25 / 25

Available from: http://history-computer.com/
Library/VonNeumann1.pdf.

Larry Yaeger. Computational genetics, physiology, metabolism, neural systems, learning, vision, and behavior or polyworld: Life in a new context, 1994.

Available from: http://www.beanblossom.in.us/
larryy/polyworld.html.

25 / 25