Coreworld QTAAS

From FreeBio

Alexander (Sasha) Wait School of Computer Science, McGill University Montreal Quebec, Canada

Abstract

In this work—and elsewhere (see Wait 2004)—I propose to develop an abstract, quantum mechanical biosphere with the following properties:

• easily distributed, three-dimensional, quantum virtual machine (QVM) consistent with biological desiderata gathered from the literature and established axioms of quantum information processing (QIP);

• the QVM should evolve completely autonomously—starting from random sequences—and permit perturbation by human participants;

• include a change management/build/test system for systematic exploration of alternate QVMs so the abstract biosphere is as natural as possible; and,

• permit the solicitation of CPU time and human ingenuity over the Internet to ensure that any putative QIP advantage—or lack of advantage—is not an artifact of my personal ability or computational resources.

With some luck, I hope, the abstract biosphere presented here will provide an intriguing platform for further research.

Résumé

Dans cet ouvrage ainsi que dans d'autres (voir Wait 2004), je propose de développer une biosphère quantique abstraite avec les propriétés suivantes:

• elle comporte une machine virtuelle quantique (QVM) facilement distribuable et tridimensionnelle, incluant les desiderata biologiques rassemblés à partir de la littérature ainsi que les axiomes établis du traitement d'information quantique (QIP);

• la QVM devrait évoluer de façon tout à fait autonome, à partir de séquences aléatoires, et devrait permettre l'ajout de perturbations par des participants humains;

• elle inclut un système traitant les gestion, construction et test des changements pour l'exploration systématique de QVM alternatives, de sorte que la biosphère soit aussi naturelle que possible; et,

• elle permet la sollicitation de temps de CPU et de l'ingéniosité humaine au travers l'Internet pour assurer que tout avantage supposé de QIP, ou au contraire une absence d'avantage, n'est pas un pur produit de mes habilités personnelles ou de mes ressources de calcul.

Avec un peu de chance, la biosphère abstraite ci-présentée fournira une plateforme intrigante pour de futures recherches.

Acknowledgments

The quantum coreworld project could never have been started in earnest without the support of my graduate advisers in computer science, Gilles Brassard and Claude Crépeau. It continues with the support of my current graduate adviser in biophysics, George Church. Many others have provided formal and informal review of the ideas here including: David Deutsch, Kathleen Donohue, Rachelle Gaudet, James Hogle, Seth Lloyd, Norman Margolus, Peter Shor, Shamil Sunyaev, Gerald Sussman, and Jack Szostak. Their feedback, and their students' feedback, helped improve this thesis. Their skepticism, moderated with cautious encouragement, has kept me productive.

This project has been inspired by Richard Stallman's free software ideals; without the efforts of thousands of free software volunteers this work would not exist. Hilary Putnam suggested I look at Rush Rhees' remarkable book, Without answers. Bonnie Dlott brought the writing of Ken Wilber to my attention. Asher Lipner suggested I read Scholem's the Idea of the Golem. My friends Genevieve Arboit, Alisa Lockwood, Ernesto Posse, Will Renner and Sarah Zaranek helped with last minute edits. A.K. Dewdney's Computer Recreations columns, in particular his articles on “corewar� first appearing in the eighties in Scientific American, have sparked a career-long interest in using computer models as physical, chemical, biological, and even theological laboratories. The Internet news group REC.GAMES.COREWAR remains the focal point for corewar enthusiasts worldwide. Special thanks to Barkley Vowk, Christian Schmidt, Joonas Pihlaja, John Metcalf, Roy van Rijn and Will Varfar for their valuable feedback on this project.

An alternate thesis to the one I present here, proposed by Roger Penrose in the Emperor's New Mind and in Shadows of the Mind, is that we must develop radically new scientific theories before we can understand the mind. Whether or not all of my hopes for "artificial souls" are fulfilled—Prof. Penrose might still be right—some, non-classical, properties of life might remain tantalizingly out of scientific reach. Perhaps, secretly, I hope this is true.

Inevitably it is not possible to thank everyone who has helped me. The quantum coreworld has been an all consuming passion for much of my life; I am in debt to each and every person who has influenced me—Thank You!

Contents 1 Introduction 2 Background 2.1 Cellular automata 2.1.1 Zuse 2.1.2 Fredkin 2.1.3 Wolfram 2.1.4 Margolus 2.2 Assembler automata 2.2.1 Corewar 2.2.2 Coreworld (“classic�) 2.2.3 Tierra 2.2.4 Avida 2.3 Biological desiderata 2.3.1 Metabolism 2.3.2 Compartmentalization and hitchhiking 2.3.3 Lineage 2.4 Quantum games 2.4.1 Stabilizer formalism 2.4.2 Cryptography 2.4.3 Teleportation 3 Quantum Virtual Machine (QVM) 3.1 Overview 3.1.1 Compartments and regions 3.1.2 Bricks and cores 3.1.3 Steps, cycles, fluctuations 3.1.4 Pseudorandomness, branches and leaves 3.1.5 Interventions 3.2 Monomers (instructions) 3.2.1 Backbone 3.2.2 Side-chains 3.3 Polymers (programs) 3.3.1 Nutrient flux and origin of “life� 3.3.2 Brownian motion 3.3.3 Motifs and evolution 4 Quantum mechanics 4.1 Operations under the control of programs 4.1.1 Quantum Control Not (QCN) 4.1.2 Quantum OPeration (QOP) 4.1.3 Measurement 4.2 Operations under the control of the environment 4.2.1 Swap 4.2.2 Decoherance 4.3 Evaluating stabilizer circuits 5 Discussion 5.1 Artificial Souls 6 Conclusion and Future Directions 7 References 8 Appendices 8.1 Appendix I: A simple replicator

Introduction

Could the mind of a quantum lifeform be more ephemeral—more soul-like—than the mind of a classical lifeform? In this thesis I describe a world which might support quantum mechanical artificial life. My quantum coreworld is inhabited by assembly language programs; the language—an extended version of corewar's Redcode (Dewdney 1984)—permits programs to use quantum operations on quantum bits (Nielsen and Chuang 2000). For a lively discussion of similar work, but without a quantum or theological twist, see O'Neil 2003. With luck, this project—accessible over the Internet at http://science.fiction.org/qtaas—will provide a useful collaborative laboratory at the intersection of biology, physics and computer science.

A coreworld consists of volumes of spacetime, called bricks, arranged in a torus. In Figure 1 the bricks are colored cubes. For comparison with real biology it can help to think of one brick as a femtoliterday – a cube of water, one micron on each side, for one day. A femtoliter contains billions of water molecules at standard temperature/pressure and enough space for a few simple bacteria. Depending on its dimensions, in bricks, an abstract coreworld models the “biosphere� around a tiny speck of dust or an Earth-like planet. Necessarily these are very crude models. If computational investigation, however, finds sufficient similarity to real biology, the techniques of mathematical proof—in particular the tools of modern cryptology—might be fruitfully used to analyze the coreworld. Before we could even begin such a theoretical program, however, it will be necessary to determine the essential features of an evolving biosphere.

Two parallel areas of research—digital physics and digital evolution—provide a platform on which to build this thesis. Digital physics typically uses simple, cellular automaton models that can be readily parallelized with appropriate hardware. In principle cellular automata can have arbitrarily complex behavior but, in practice, highly complex software systems are written more succinctly in higher level languages. For modeling biology, assembly languages are one step up. Assembler automata are currently a popular approach for digital evolution experiments. These languages, interestingly, are typically closer to the simple rules of cellular automata than to traditional assembly languages. Stripped down assembly languages are optimized for automatic evolution and are not intended for use by human programmers (Ofria et al. 2002). The information processing power of the biosphere overwhelms the computational resources available for digital evolution experiments. For this reason human written programs could be more complex than their digitally evolved cousins, so long as humans are sufficiently motivated to write them. In designing the world described here, arbitrary design decisions are always made to favor humans. I would prefer to know that highly complex “lifeforms� can be engineered to survive in the coreworld and, second, that they can evolve.

If the goal of this thesis is to build a world in which it's easy for humans to engineer lifeforms, why not use a very high level language such as Scheme, Haskel or OCaml? A subtle reason involves the definition of lifeforms. For instance, some scientists consider self-replication a requirement for life but others consider viruses—which do not replicate—to be lifeforms. There is no scientific consensus on the precise definition of a lifeform! An opportunity offered by this work is for such a definition to emerge from the bottom up. In the coreworld it should be possible for microbe-like replicators and virus-like hitchhikers to co-evolve and aggregate into larger structures from (causally) disconnected parts. While the parts can be written in a human friendly assembly language, the larger aggregate structure could have the locality of a cellular automaton. Tuning the world so that such aggregate structures are possible at all—let alone possible through a process of evolution by natural selection, given available computational resources—is a daunting challenge. The possibility of such lifeform-like aggregates does present one intriguing benefit, however, readily simulated quantum non-locality could provide a selective advantage to such quantum lifeforms.

There is no known method to simulate quantum information processing, in general, on a classical computer. A class of quantum states—described by the stabilizer formalism, often applied to problems in fault tolerant quantum information processing—can be classically simulated. By focusing on the non-locality of quantum mechanics exhibited by entangled states in the stabilizer formalism it might be possible for the lifeforms inhabiting the coreworld to out compete their classical counterparts. The construction and use of these entangled quantum states by programs provides an additional resource to be investigated; shared randomness is another resource. The time and space requirements for computation in the coreworld are not the only resources of interest.

To facilitate the simulation of a coreworld, bricks belong to compartments—there are four compartments in the world of Figure 1—that interact weakly (red bricks). No entanglement is permitted across compartments, so, each compartment can be computed independently by physically independent hardware. The physical system underlying computation in the coreworld also plays another role. Computer scientists can, normally, take for granted the mass/energy requirements underlying a computation. A central aspect of biology, however, is the flux of nutrients through an evolving biosphere. Programs and the assembly instructions from which they are composed are embodied by abstract polymers and monomers (respectively). These polymers (programs) undergo Brownian motion during fluctuations. Each fluctuation, new polymers—made from random sequences of monomers—enter the biosphere at the (green) bricks close to the center of the torus and these provide a source of nutrients and new diversity. In addition the coreworld is highly stochastic to avoid the brittleness—or sensitivity to arbitrary parameters—of many assembler automata. The ability to find and metabolize nutrient could be the most important determinant of program's persistence in the longterm. Nutrient is thus another resource that must be considered in analyzing the coreworld.

Background

It would be impossible to build an abstract, quantum-mechanical biosphere—that can be experimentally manipulated over the Internet—without using a great deal of preexisting practical and theoretical knowhow from Physics, Computer Science and Biology. In subsequent background sections, I will: review closely related work on assembler automata, suggest some biological desiderata, and briefly sketch some quantum games that might be relevant to quantum lifeforms. In the next section, on cellular automata, I grapple with prior explorations of the “universe as computer� metaphor.

Cellular automata

It is difficult to give a good definition of cellular automata since many people have used this term in slightly different ways. One definition I like is given by Norman Margolus at the end of this section. For our purposes, however, a cellular automaton is a type of finite automaton that has a regular spatial structure which permits easy computation, in parallel, of the automaton's state as it is updated through time. Many people have imagined that the entire universe is a variety of cellular automaton at bottom. It is not easy, however, to resolve the tension between classical locality and the non-locality permitted by quantum physics. Konrad Zuse, Stephen Wolfram, Edward Fredkin and Norman Margolus have explored this quantum/classical paradox—and many other topics—in their work on cellular automata. I will give some of the highlights in the rest of this section.

Assume for the moment the universe is a cellular automaton. How big is it? Seth Lloyd (2002) estimates the entire universe has performed, at most, 10120≈2400 elementary operations on 1090≈2300 (quantum) bits. How many “elementary� operations have been performed during the evolution of the Earth? Suppose we consider only the infection of bacterial cells by phage, or viruses, as elementary operations; Pedulla et al. (2003) estimate that 1042≈2140 phage infections of bacteria—in a global population of 1030≈2100 bacterial hosts—have occurred in the Earth's history. Clearly this is an underestimate of the number of elementary operations since the Earth began to evolve. To get it right, no matter how much we simplify, a cellular automaton model of evolution will require huge computational resources.

Zuse

In the 1960s Konrad Zuse (1969) wrote a remarkable manuscript in which he considered discrete models of physics—which, in translation, he called calculating space—as a possible replacement, or complement, to continuous models of physics. He concluded his manuscript with the following table and observations:

In view of the possibilities listed, it is clear that there are several different points of view possible:

1. The ideas of calculating space contradict some recognized concepts of present-day physics (for example, space isotropy); therefore, the fundamental basis must be false.

1. The laws of calculating space must be revised with the object of eliminating the existing contradictions.

1. The possibilities arising from the ideas of calculating space are in themselves so interesting that it is worthwhile to reconsider those concepts of traditional physics which are called into question and to examine their validity from new points of view.

I think that Zuse favored the later possibility – as do the other authors of this section. Zuse, as have others, hoped for a better picture of quantum physics from discrete, computational models.

Fredkin

Recognized as a pioneer of digital physics, Edward Fredkin continues to develop new models (Fredkin 2003) that explain physical phenomena as discrete, computational processes. While he acknowledges that digital physics cannot explain certain quantum phenomena (Fredkin 2004), I believe that Prof. Fredkin has missed an opportunity to consider hybrid quantum-classical digital physics models that have become possible with the advent of quantum information processing.

Wolfram

While Zuse, Fredkin and others have explored the possibility of founding the physical sciences on a discrete—cellular automaton—physics, Stephen Wolfram (2002) explicitly tries to connect his investigation of cellular automata to insights into biology. Clearly this work, which he has dubbed “A New Kind of Science,� is new to the last century but certainly not new to the last few decades. Also, Wolfram is generally dismissive of quantum information processing – although this sentiment is shared by many people it seems that the proponents of discrete physical models have an obligation to explain the central phenomena of quantum mechanics – failure to do this is both a problem and an opportunity for the field (as noted by Zuse.)

Margolus

Much of my interest in digital physics stems from a chance encounter with Norman Margolus at MIT in 1993. He defines cellular automata as follows (Margolus 1988):

In CA, space is a regular lattice of cells, each of which contains one of a small allowed set of integers. Only cells that are close together interact in one time-step—the time evolution is given by a rule that looks at the contents of a few neighboring cells, and decides what should change. At each step, this local rule is applied everywhere simultaneously.

Under this definition CAs are well suited to dedicated, massively parallel hardware. This does not translate in an obvious way to non-local quantum systems. Efficient simulation of quantum systems is impossible, if some physically solvable computational problems—such as factoring—require solution by quantum means (Margolus 2003).

Assembler automata

Cellular automata, as seen in the last section, are the preferred tools of digital physics. Such automata can be reversible so that a description of the automaton at one point in time can be used to calculate both the description at both the “next� point in time and also the “previous� point in time. Assembler automata are a class of, generally, irreversible finite automata that have been used for experimental investigations of evolution. These automata update each lattice cell in only a few places at a time, have a finite—but possibly quite large—number of states at each position, and can perform arithmetic and conditional updates according to a simple assembly language in a local—but, again, possibly quite large—neighborhood of the cell. Four of these assembler automata will be discussed in the subsequent sections. Please see Dittrich et al, 2000, for a discussion of these and other computational chemistries.

Corewar

The game corewar was first described in Scientific American by A.K. Dewdney in 1984. Since the first corewar tournament at the Boston Computer Museum (Dewdney 1987) the game has continued to attract fans who play it over the Internet. In a tournament several authors compete vicariously through the activity of simple assembly language programs they have prepared in advance. In general, the winning strategies employed by these programs are quite sensitive to the rules of that particular tournament. To understand how this works it's helpful to understand the game in more detail.

Corewar is played in a circular memory array—called a “core�—in which every memory cell can address every other cell. Unlike a typical cellular automaton, each player executes at only one location in a given cycle or time slice. Each player, however, is allowed several “tasks� and the assembler automaton schedules these in successive cycles. A round lasts for a number of cycles. The core is reset at the end of each round and the competing programs are replaced at new positions in core. Thus, the main parameters of a tournament are: coresize, maximum tasks per player, cycles per round, and number of rounds. The dizzying progression of new strategies that has emerged over the last twenty years is the game's most biological quality.

Coreworld (“classic�)

Rasmussen et al. introduced the “Classic� Coreworld in 1990. In their corewar variant they: limited the cells addressable from a given point in core, introduced an “energy� resource that is consumed by computation, added mutation during the process of copying assembly instructions, and seeded the core with random sequences. The authors found that in high energy “jungle� conditions more complex behavior emerges, while in low energy “desert� conditions only simple behaviors emerge. This automaton is extremely difficult to analyze since “individuals� are not well demarcated from their environment; resolving this and other perceived difficulties was a goal in Tierra and Avida.

Tierra

Tom Ray introduced Tierra in 1992 to model the diversity of life. Ray introduced an environmental “reaper� process that examines the core and terminates tasks according an artificial selection pressure. This automaton uses a significantly simplified assembly language over corewar; and, thus, it has a smoother fitness landscape for evolution. It also introduces “protected memory� so that individual tasks can own certain memory cells in core and are thus easier to identify. Tierra is in active use today.

Avida

Avida is the premiere digital evolution platform and is actively used for the investigation of important evolutionary phenomena (eg. Chow et al. 2004). Avida permits a clear demarcation between individual organisms, gives organisms a two-dimensional landscape on which to roam, introduces metabolic “rewards� for solving certain computational tasks, and uses a Tierra-like assembly language to represent “genomes� that can show significant evolution in computationally tractable experiments. Avida organisms do not generally interact. The course of evolution is primarily determined by the fitness landscape induced by the schedule of metabolic rewards provided by the experimenter. Recently there has also been an effort to explore the effect of sexual reproduction in Avida lifeforms (Misevic et al. 2004).

Experiments with Avida—along with Tierra and the “Classic� Coreworld—provide inspiration and the necessary data to revisit the development of a new corewar-like assembler automaton that is significantly more biological than its predecessors. Some desiderata for such an automaton are described in the following section. I believe that the diversity generated by standard corewar is so spectacular, however, that the rules of any new corewar-like automaton should be compatible, if at all possible.

Biological desiderata

One criterion for an interesting abstract biosphere is that it should be possible to compare it with natural biospheres. The biological desiderata described here—metabolism, compartmentalization, hitchhiking, and lineage—are compiled from the literature to help provide criteria for naturalness (eg. Szostak et al. 2001; Weinbauer and Rassoulzadegan 2004). Another criterion for an interesting abstract biosphere—in direct conflict with biological plausibility—is the possibility to deduce its main properties through mathematical proof. A goal of this thesis is to abstract away enough of the programming and biological details to make theoretical investigation—perhaps, of simpler models—attractive to computer science theorists.

Metabolism

A central feature of life in the biosphere is the conversion of nutrients into new biomass or the irreversible consumption of these nutrients for the acceleration of essential biochemical processes. Programs in the corewar automaton have neither of these features; there is no limit on replication according to available “nutrients� and there is no cost associated with the rate of computation.

Compartmentalization and hitchhiking

Individual organisms, at the molecular scale, consist of independently evolving parts. These parts can be recognizably distinct “replicators� or virus-like “hitchhikers�. The interplay between evolving parts—and organisms—is made possible by the local structure imposed by physics that is missing from corewar.

Lineage

One reason that assembler automata are popular for digital evolution purposes is that similar assembly language programs are, often, similar in their function. corewar-like automata all have this property. It was noted in the classic Coreworld, however, that dense interaction networks can develop in which it is extremely difficult to identify individuals. Since “organisms� in the Quantum Coreworld, as in the real world, should consist of independent, co-evolving parts the problem of establishing lineage could be acute; addressing this issues will be a major task of this project.

Quantum games

Over the last century, the various interpretations of quantum mechanics have led to a great deal of controversy in physics and philosophy. In the last twenty years, the growing field of quantum information science has recognized that quantum mechanics has practical consequences for the possible “games� that can be played in the real world. The quantum coreworld permits evolving lifeforms to play some of these games. I hope to discover circumstances, if any, that lead to selective advantage for quantum lifeforms.

Stabilizer formalism

Quantum Information Processing (or QIP) is a mathematically well defined distillation of numerous physical experiments (Nielsen and Chuang 2002). The rules of QIP can be used to extend any assembly language with quantum operations on quantum bits.

In general it is believed to be impossible to simulate QIP efficiently on a classical computer; primarily this is due to the discovery of efficient algorithms for factoring and taking discrete logarithms (Shor 1994.) If the quantum operations belong to gates in the stabilizer formalism, see Figure 2, an efficient simulation is possible for thousands of qubits (Aaronson and Gottesman 2004). Although stabilizer circuits are not even capable of universal classical computation, they are interesting for their non-locality and widely applied in fault tolerant quantum computation (Gottesman 1999, Cross 2005.) Some properties of quantum gates in the stabilizer formalism will come in useful later. I state them here (following the above references).

The stabilizer formalism is characterized by the following theorem:

Where the Pauli matrices are defined:

The group of n-qubit Pauli operators consists of all tensor products of n Pauli matrices, together with a multiplicative factor of orThe total number of operators isGiven a pure quantum state we say a unitary matrix U stabilizesif is an eigenvector of U with eigenvalue 1, or equivalently if where we do not ignore the global phase.

Another useful fact to be used later is that the Pauli matrices X, Y, Z can be written as:

The X operation—in the computational basis—corresponds to a classical bit flip. We will need the operation since the environment can flip the value of a qubit.

Cryptography

The best known quantum cryptography protocol BB84 (Bennett and Brassard 1984)—implemented in the real world—is also easily simulated on a classical computer. The “catch� is that only the denizens of the simulation could benefit from the simulated security. Consider three such denizens Alice, Bob, and Eve. Starting with a shared private key—a random sequence of classical bits—Alice and Bob can extend their key; Eve cannot obtain knowledge of the extended key without giving herself away.

For this to work, Alice and Bob have access to quantum and classical channels which they will use as required. All parties can prepare quantum states in the computational basis, measure those states in the computational basis and perform, for example, hadamard operations. No matter what operations Eve can do, in addition to these, she doesn't gain any extra power; her observation of the quantum channel will necessarily disturb that channel. Alice begins by sending n qubits to Bob; she chooses the qubits uniformly at random from the computational basis states or a basis state followed by a hadamard (four possibilities). Bob receives the n qubits and measures them, first applying a hadamard (or not) to each qubit at random. The protocol then proceeds in two steps:

Reconciliation: For all n qubits, Bob reveals on the classical channel if he applied a hadamard prior to measurement. Furthermore Bob unveils the results of, say, n/2 measurements (at random). If Alice also applied a hadamard, the result of Bob's measurement should match what Alice sent—unless Eve or the environment disturbed the channel—Alice can now announce the error rate on the quantum channel. Based on this error rate—and applying a classical error correcting code—Bob can use the remaining n/2 bits to establish a smaller private key with Alice.

Distillation: If Eve is watching the quantum channel she can surreptitiously measure a few qubits. Since Eve doesn't know if Bob will apply a hadamard, or not, half the time she measures a qubit she will scramble the result of Bob's measurement; her increased knowledge of the key results in an increase in the error rate above! Alice and Bob may use classical privacy amplification to discard enough bits of their corrected key that Eve has no knowledge (whatever) of any of its bits. If Eve acquires so much information that this doesn't work, Alice and Bob can abort.

Teleportation

The quantum teleportation procedure (Bennett et al.1993) is illustrated in Figure 3 below:

1. Alice and Bob share an EPR pair; Alike keeps qubit A and Bob keeps qubit B.

1. Alice teleports her qubit to Bob by applying the above circuit and transmitting bits X and Y to Bob.

1. Bob receives bits X and Y from Alice; he then applies the above circuit and, thus, completes the teleportation.

The existence of the teleportation procedure permits quantum information to be passed around over classical channels so long as entanglement was previously shared. Since this procedure consists of gates from the stabilizer formalism it can be efficiently simulated if the teleported qubit was itself prepared by gates in the formalism.

Quantum Virtual Machine (QVM)

Imagine a toroidal volume of water wrapped around a tiny speck of dust or Earth-like planetoid (see Figure 4 below); currents keep some regions partially isolated from others and nutrients—sugars, lipids, amino acids, the ingredients for new life—seep in from the center. If we could write down the coordinates and composition of every “dry� biochemical monomer—dissolved in the water—we would have a real version of the biosphere described in this thesis. I find it is helpful to keep this imagery in mind when thinking about the QVM.

The QVM is designed so that polymers, or programs, are (somewhat) insensitive to arbitrary constants; further elaboration of this insensitivity is reserved for the Discussion. The QVM will produce 4D spacetime snapshots of the biopsphere and perform other types of real-time analysis. To make the problem tractable the evolution of the biosphere is divided into spacetime volumes called “bricks� which are organized into compartments that can be computed by independent processors. For concreteness one can think of a brick as a femtoliter of water (a cube one micron on each side) in space—at standard temperature and pressure this would consist of billions of water molecules—a few, small, bacteria could fit in a femtoliter. Also, for concreteness, one can think of a brick as one Earth day in time.

Overview

The non-locality of quantum mechanics rules out a quantum mechanical biosphere that can be distributed to a cluster of classical processors without communication. Independent—only weakly communicating—compartments, however, are a design goal for the QVM. This is achieved as follows.

Compartments and regions

Coreworlds are divided into W regions of size X by Y by Z arranged in a torus; X,Y,Z are restricted to powers of two and W must be even. Some coreworlds are illustrated in Figure 5. Every coreworld has at least 4 regions of size 4x4x4; furthermore it has 2W/2 compartments that interact during fluctuations by exchanging neighboring bricks (red). Qubits in these bricks are measured so no quantumness crosses compartment boundaries. Every compartment has independent parameters X, Y, Z, and T that vary from fluctuation to fluctuation; this should prevent the brittleness of many assembler automata.

Bricks and cores

A core is made of at least eight bricks—more depending on the microclimate of the compartment—and a compartment is made of at least eight cores; recall Figure 1, this is the smallest possible coreworld. A monomer (instruction) can act on any monomer in the same core and one eighth of the neighboring core. Every monomer in a core has a dual monomer which is illustrated in Figure 6; there are 2 bricks in each core in the X direction, 4 bricks in the Y direction and 8 bricks in the Z direction in this figure. Since coresize can vary, polymers (programs) must not depend on a particular coresize. The number of monomers per brick, however, is a constant. Whether or not programs in the coreworld are actually insensitive to bricksize, coresize, compartment dimensions or the coreworld's W, X, Y, and Z dimensions is a matter of further investigation.

A coreworld of dimensions 10•32•32•32 is probably the largest that can be reasonably simulated with available hardware (only 10/4 times larger than the world in Figure 6). If there are 1024 molecules per brick in this world it would require over 300 million lines to write down the world, not including any quantum histories. I would estimate that each complete description will use up to several gigabytes of uncompressed storage but less than one megabyte when compressed. In his excellent survey of complexity measures Shalizi (2002) writes about the failings of using off-the-shelf compression software as a proxy for entropy. Great care should be taken in over-interpreting the significance of the compressed file lengths of quantum coreworld snapshots.

Steps, cycles, fluctuations

Each compartment in the coreworld can be distributed to a different physical processor for computation. The number of updates from compartment to compartment, furthermore, can be quite variable. Although the actual updates of a compartment occur sequentially—one monomer at a time—these individual steps are effectively simultaneous from the perspective of the world's inhabitants. For each cycle that passes in the compartment every active monomer in the compartment has an opportunity to execute one step. These independent computations are synchronized in time during fluctuations. New polymers (programs) enter the world during fluctuations, free nutrient is distributed within and between compartments, bricks are exchanged between compartments (their qubits are measured so no quantum information is exchanged), the microclimate in each compartment fluctuates and some programs undergo a type of Brownian motion. At the end of a fluctuation the coreworld looks like Figure 7 with exactly half the bricks empty (except for distributed free nutrient). The fluctuation itself can be computed in parallel; for each compartment data from only the neighboring compartments must be parsed before computation of that compartment can continue as usual. Once neighbors have completed, work for the next fluctuation can begin.

The microclimate of each compartment consists of parameters X, Y, Z and T. One of these parameters is adjusted upward with probability ¼ or downward with probability ¾. The X, Y, Z parameters determine the number of bricks per core in that compartment; 2-T is the expectation that the compartment will complete computation for that fluctuation. There is no maximum value for T. By default the minimum is 16. It remains to be seen if programs in the world are insensitive to these constants.

Pseudorandomness, branches and leaves

Each compartment uses an independent 128 bit seed—for pseudorandomness—to determine the outcome of the computation for one fluctuation. These seeds can be varied so that for the same initial state we get a distribution of QVM states. Both the classical and quantum mechanical behavior of the world depends on this distribution. I refer to the QVM states for different seeds but otherwise identical initial state as leaves. I refer to a particular path from some initial state through many fluctuations a branch. Computing multiple leaves and branches provides for the possibility of determining the generality of the outcomes of evolution in the coreworld's biosphere. For the QVM to be correct it must produce only “possible� leaves and, furthermore, the probability distribution of leaves must also be correct.

Interventions

Participants interested in intervening in the quantum coreworld ecology can write their own programs and submit them at http://science.fiction.org to see the results. Up to one corewar and one coreworld program can be uploaded. Programs are queued and take effect at the next fluctuation. Manipulatable, 4D, models of the quantum coreworld's evolution are planned; Figure 1 consists of two snapshots, in time, of such models. Real-time debugging, analysis and change-management facilities are also planned.

Corewar programs provide a source of mutation in the coreworld (by causing damage during their execution.) In principle these programs can co-evolve in parallel with the QVM so that there is an evolution in the abiotic environment of the world along with the biotic environment. At the end of every fluctuation—before programs begin to execute under their own control—half of the biosphere is empty (except for distributed free nutrient). In this empty portion of the biosphere, a standard 1994 corewar program can be unleashed to battle random opponents that have been previously uploaded. The coresize of each battle will vary from world to world and the number of corewar style tasks will be 64 (this was the ICWS tournament standard and keeps the memory footprint of the corewar tasks low.) For purposes of human participation scoring will be 1 point to each if both programs are still alive at the next fluctuation; 3 points to the winner if only one program is alive. These contests provide full compatibility between the quantum coreworld and the classic corewar game.

Monomers (instructions)

A monomer in the quantum coreworld chemistry embodies an instruction from Table 1. Instruction monomers have “mass�—one Biological Mass Unit (BMU) per monomer—as do the nutrient side-chains. The behavior of a monomer is determined by its backbone (modifier, A mode, B mode, tag) and side-chains (A, B, nutrient, and qubit); each of these are described in the subsequent sections. For a given QVM, the classical part of a monomer—all but the qubit field—can be represented with a small, constant number of classical bits (i.e. one line in a text file).

DAT	terminate (corewar); don't advance nutrient (coreworld)
MOV	copy from A to B; use nutrient (coreworld only)
ADD	add A to B, result in B
SUB	subtract A from B, result in B
MUL	multiply A by B, result in B
DIV	divide B by A, result in B; DAT if zero
MOD	divide B by A, remainder in B; DAT if zero
JMP	execute at A
JMZ	execute at A if B is zero
JMN	execute at A if B is not zero
DJN	decrement B, if B is not zero, execute at A
IJN	increment B, if B is not zero, execute at A
SLT	skip if A is less than B
SEQ/CMP	skip if A is equal to B
SNE	skip if A is not equal to B
NOP	no operation
SPL	new task (corewar); NOP (coreworld)
QOP	quantum operation on B, specified by A
QCN	quantum not of target B, controlled by A

Table 1. Valid instructions.

Backbone

The instruction field determines the type of thing that each monomer can do. The available instructions are listed in Table 1 (above). The modifier specifies what field(s) an instruction uses. Modifiers are listed in Table 2 (below). The A mode determines how the A side-chain is to be interpreted and the B mode determines how the B side-chain is to be interpreted. Valid addressing modes are listed in Table 3 (next page). The tag is a cryptographic hash of the ancestral program which brought that monomer into the world. Although there are several ways in which a monomer backbone can be flushed from the world, the MOV.I instruction is the only way a backbone can be synthesized. Executing this instruction—which copies the Instruction, Modifier, Tag, A Mode, B Mode and the A/B side-chains—uses one unit of nutrient. Since nutrient is a scarce resource—akin to glucose in real biology—motifs in the quantum coreworld must have a simple metabolism to persist in the long term (see also discussion.)

Departures from the Redcode language of standard corewar can be seen in Table 1 (previous page). IJN, Increment Jump if Not zero, is analogous to DJN, Decrement Jump if Not zero. It has been discussed, but not added to Redcode, in the past. In combination with the new “.Q� modifier—which specifies that the instruction deals primarily with the qubit side-chain—IJN has an application as a “concurrency primitive� (atomic test and set). IJN also plays a role in adding nutrient when used in combination with the new “.P� modifier—which specifies that the instruction deals primarily with the nutrient side-chain—causing a new thread of execution. The “.D� modifier specifies that the B-pointer refers to the dual core (see the discussion of bricks earlier). The “.E� modifier consumes nutrient in exchange for a greater likelihood of execution; the “.E� modifier is the only way that nutrient is permanently removed from the world. All modifiers are listed in Table 2 below. Finally, valid addressing modes are listed in Table 3 (next page).

.A	Instruction reads and writes A fields
.B	Instruction reads and writes B fields
.AB	Instruction reads A field of A instruction, B field of B instruction and writes B field
.BA	Instruction reads B field of A instruction, A field of B instruction and writes A field
.F	Instruction reads both A and B fields of A and B instruction and writes to both A and B fields (A to A and B to B)
.X	Instruction reads both A and B fields of A and B instruction and writes to both A and B fields (A to B and B to A).
.I	Instruction reads and writes Instruction field, Modifier field, Addressing Modes, A and B fields; (Tag for MOV.I, coreworld only)
.P	Instruction reads and writes nutrient field(coreworld only)
.Q	Instruction reads and writes qubit field (coreworld only)
.D*	B pointer refers to dual core (coreworld only)
.E*	Consume nutrient, execute faster (coreworld only)

Table 2. Valid modifiers; * indicates modifier can be combined with others

#	immediate
$	direct
@	indirect using B-field
<	predecrement indirect using B-field
>	postincrement indirect using B-field
*	indirect using A-field
[	predecrement indirect using A-field
]	postincrement indirect using A-field

Table 3. Valid addressing modes.

Side-chains

The A-side-chain and B-side-chain are straightforward data fields. They can be integers between 0 and coresize - 1. Since the number of monomers in one core, coresize, can change from fluctuation to fluctuation these fields are automatically sign extended or truncated to accommodate the change.

Nutrient is a positive integer. Its value can be unlimited, in principle, but it cannot be greater than the total nutrient in the world, which is itself bounded. Coreworld style monomers require nutrient greater than zero to be active, while corewar style monomers use corewar task-queues. Corewar monomers, that do not use nutrient, are removed from the world at each fluctuation. Nutrient is used to execute more quickly (with the “.E� modifier) and is required by “MOV.I� to synthesize new monomer backbones.

The qubit side-chain is described further in the chapter on quantum mechanics.

Polymers (programs)

Programs in the coreworld, by definition, are linear polymers that fit in one “brick�. Polymers are made out of monomers (instructions). Brownian motion moves the polymers around during fluctuations. A simple—single monomer—program is shown in Figure 8; it is known as an “Imp� and it circles around a neighborhood of bricks—the core—until it is cleared. A motif may be active at more than one point in the polymer; the active sites have non-zero nutrient. Please see monomers for further explanation.

Nutrient flux and origin of “life�

The quantum coreworld gets its name from the “Classic� coreworld of Rasmussen et al. as discussed in Background: Assembler Automata. In that work, investigators were not able to detect any satisfactory evidence for evolution of complexity. This was assumed to be caused by the brittleness of the Redcode instruction set and other factors. Recently much progress has been made at generating human competitive corewar programs in various circumstances (Corno et al. 2003, Vowk et al. 2004). At every fluctuation, in the Coreworld, a different program will be generated at random in every brick closest to the toroid's center (eg. green bricks in Figure 1 from Introduction). These programs will be chosen from a probability distribution known to be biased for good programs while keeping the probability of generating the same program twice negligibly small. An example program is found in Appendix I.

New diversity can also enter the biosphere through human written programs; these programs must also be unique and are, essentially, indistinguishable from those that might have arisen by chance.

Brownian motion

At every fluctuation half the bricks in every compartment will undergo brownian motion. A polymer will be moved according to its mass in Biological Mass Units (BMUs). This is computed by counting the number of monomers in the backbone plus the total number of nutrient monomers attached to the backbone. The polymers will be moved according to a ball around their present location whose radius is determined by flipping a coin until it comes up heads and then dividing by the square root of the polymer's mass. The rate of diffusion of polymers could be tuned by modifying this formula. Polymers that overlap with others will cause those polymers to revert to the free nutrient pool. Furthermore, some polymers will be reverted to the pool – outright. The possibility that a polymer will be reverted to free nutrient creates a selection pressure for distributing nutrient more evenly throughout a population of programs. Failure to do so will lead to a catastrophic loss of accumulated nutrients. Due to the effect of Brownian motion programs in the world can lose track of one another. Entanglement, within a compartment, is unaffected by this – entangled qubits, as expected, remain entangled.

Motifs and evolution

Evolution in the world occurs when damage (eg. deletion) or recombination with another polymer during Brownian motion leads to a new polymer that can still replicate or be replicated. These new polymers can have a selective advantage over existing polymers and thus lead to evolution. Data mining techniques can be used to find common motifs in the coreworld. Although evolution in real bacterial populations is very slow I hope that the arms-race between replicator and hitchhiker leads to evolution in the coreworld.

Quantum mechanics

Every operation in the quantum coreworld is serialized so that the world's state is modified in only a handful of monomers per step. From the perspective of programs these steps are stochastic and can seem, effectively, simultaneous. In each compartment the QVM records the step (an integer) in which a quantum operation occurs, which operation it is and the qubit(s) involved. The QVM performs whatever simplifications it can and, when necessary, feeds the resulting quantum circuits to a simulator if the QVM requests a measurement. The result of the measurement is registered in the classical state of the QVM and recorded in the qubit's history. The measured states are never too large because—for simplicity—the only permitted quantum operations belong to the stabilizer formalism (with some minor variants). These states are still highly non-local, so, a selective advantage might still be obtained from them. Please see the discussion and the background section on quantum games. During fluctuations overwritten qubits are measured (and swapped), as are qubits bordering between compartments.

Operations under the control of programs

The quantum coreworld permits programs to build very complicated, non-local quantum states. These states are stored as histories of quantum operations and interact with the “classical� biosphere through measurement. Millions of qubits can be present in the same compartment. Practical considerations, however, require that states be limited to only a few thousand qubits; this may not mean that programs run into any limitations of simulation. Programs moved by Brownian motion will lose track of all but their own qubits (the qubits that are part of the program that was moved.) The rest of the qubits in the environment will be measured, so, the maximum expected density of qubits will be related to the density of programs in the coreworld.

Quantum Control Not (QCN)

The control not operation is the only two qubit operation under the control of programs. The simulator stores these operations in the history of both qubits with the time stamp (step) of the operation. When measurement occurs only the subset of qubits which were touched by a control not will need to be considered by the circuit simulator.

Quantum OPeration (QOP)

All single qubit operations are stored in the history of the qubit.

Measurement

When a measurement occurs it might be the case that it can be readily obtained (because the qubit is in a basis state) or it will require the evaluation of a quantum circuit. This circuit is built by considering all qubits that have been in contact with this one (via control not) and ordering all of these by time stamp. If classical operations have flipped the qubit these can be applied by performing the equivalent sequence of operations from the stabilizer formalism. Recallwhere X, by definition, is a classical bit flip. The circuit can be discarded once it has been evaluated and re-computed from scratch from the history. Some qubits—with seemingly complicated histories—may in fact be in basis states. Such measurements can be discarded from the history (since the measurement does not change the state.)

Operations under the control of the environment

At the end of each fluctuation the environment measures qubits in bricks swapped into other compartments; also it measures qubits in polymers reverted to nutrient. These measurements are called decoherence.

Swap

Brownian motion moves qubits at the end of a fluctuation. To do this qubits that have “moved� can be simply swapped by relabeling all references to each qubit with a reference to the other and vice-versa.

Decoherance

Decoherence in the coreworld is implemented as a measurement. It is given a different name simply because it occurs under the control of the environment rather than under program control. Eventually every qubit in a carefully constructed quantum state might decohere. If this happens then the histories of all of these qubits can be purged. Since error correction is possible—the stabilizer formalism is particularly well suited to this—large enough populations of entangled programs may never lose their histories. The accumulation of operations, in histories, that no longer have any casual effect on the state of the coreworld will be a problem that needs further investigation.

Evaluating stabilizer circuits

A stabilizer circuit—consisting of Control Not, Hadamard, Phase and Measurement operations, in any order—can be efficiently evaluated by the QVM. The C code appears in Appendix II (Aaronson and Gottesman 2004). Assume a circuit has been prepared by the QVM based on the operation of programs and the environment they inhabit. No evaluation is required until a measurement or decoherance occurs. Circuits can include gates outside the stabilizer formalism but then require exponential resources in the number of extra gates. Circuits within the formalism are simpler to simulate/analyze and are the only ones considered in this thesis.

Discussion

Given some fast (classical) CPUs, an Internet server and some Free Software libraries is it possible to build an interesting, quantum mechanical, biosphere? Can the biosphere be built so that it tells us something new, even if no interesting exploit of quantum mechanics is found? I believe the answer is – yes – to both these questions. In the preceding sections I have described my best effort to build a world that steps off from the current state-of-the-art and pushes it even further. In this discussion I will first consider some of the reasons I think a Quantum Virtual Machine (QVM) is interesting and then I will discuss some of its advantages as a digital evolution laboratory (quantum or not.)

Precisely because the QVM is, in fact, a classical machine we can write it down as a classical object at every fluctuation. Even if we could build fault-tolerant, biomolecular, quantum-proto-cellular-life we would lose the Quantum Coreworld's ability to keep track of the history of quantum operations. As a laboratory for a truly quantum-mechanical-biosphere the QVM—preferably augmented with a real quantum CPU for evaluating histories of quantum operations—is ideal. What can we do with this laboratory?

Many investigators have tried to discover evidence for open-ended evolution; simply defining a quantitative measure for such evolution is difficult. In the QVM, a trivial measure of complexity offers itself as a promising candidate: the compact, classical description of a quantum lifeform's molecules. Since there is a strong selective disadvantage to do classical processing with QIP operations—a QOP modifies one qubit at a time while a standard coreworld operation modifies a data-field of many bits at a time—the only QIP histories that are likely to survive the selective environment of the world are interesting, advantageous—non random—ones. Finding a simple concrete example of this seems to be very worthwhile.

I will call actual entropy the standard Shannon entropy of the compact, classical description of a quantum lifeform's state. I will call apparent entropy the standard Shannon entropy of a quantum lifeform's state from its own perspective. So the maximum apparent entropy of a fixed number of monomers is linearly proportional to the number of monomers but the actual entropy is exponential in the number of monomers. Even if we restrict ourselves to stabilizer states the actual entropy can be quadratic in the number of monomers. In an evolving biosphere where the number of discrete time units is modest actual entropy is effectively unbounded.

Some considerations: 1) as desired, the coreworld equivalent of a “flame� will have low actual entropy, random sequences have high apparent entropy, but don't manipulate coherent quantum information; 2) as desired, the coreworld equivalent of a “mule� will have high actual entropy, since they manipulate coherent quantum information, it doesn't matter that they don't replicate because all their parts are shared with other replicating things; 3) pure speculation – large contributions to actual entropy, from quantum histories, can only be generated by a process of Natural selection if the history is evidence for the sort of complexity we want in a complexity measure. In some sense this turns the argument against biological quantum information processing on its head. If Natural selection can generate and manipulate coherent quantum information (i.e. it is capable of evolving quantum error correction and fault tolerant QIP techniques) then when it does so it is due to a strong selective pressure and is strong evidence for interesting, high complexity.

Thousands of programs, using a dizzying variety of strategies, have been engineered by an international community of corewar enthusiasts. Diversity in the quantum coreworld, however, is not similarly assured. All programs must replicate—or be replicated—to persist in the long-term. Perhaps there is simply one best way to survive in the proposed world or, perhaps, the strategies discovered by humans will never evolve with the computational resources available; an essential ingredient of the diversity of actual biology could very well be missing from the QVM proposed here. Much tuning might be required to get the quantum coreworld even approximately “right�.

In tuning the quantum coreworld a great deal of methodological knowledge can also be gained. Changes to the QVM software can cause:

• no change in the evolution of a coreworld from the same initial conditions;

• no change in program (or motif) frequency and spatial distribution from the same initial conditions (but different random seeds); and,

• a change in the evolution of a coreworld from the same initial conditions.

New or different quantum circuit evaluators, in particular, could produce different results that are physically indistinguishable (according to the rules of quantum mechanics). The same is true about different pseudo-random number generators. The build/test strategy most cope with these different possibilities and the development of these strategies is an important contribution.

Clearly, the quantum aspects of the Coreworld may not lead to any new or startling discoveries. Some reasons why QIP might not provide a selective advantage in this biosphere—by no means an exhaustive list—include:

• there is a QIP advantage only if the QVM runs on an actual quantum computer i.e. there is a QIP advanrage but only outside the stabilizer formalism;

• there is a QIP advantage but it never arises spontaneously or through evolution by natural selection (although interesting classical programs do); or,

• there is no QIP advantage at all for the biosphere as devised (that is, the QVM offers an advantage on certain problems that never arise in biologically “naturalâ€? settings).

It would be desirable, in that case, if the coreworld described here could still lead to new discoveries. I believe this is possible because I have constructed the selection pressures of the quantum coreworld to be as natural as possible.

Further experiments, with small QVMs, will help clarify the naturalness of the world but, ideally, the techniques of mathematical proof should be applied to large QVMs comparable to the Earth's biosphere. The prospect of an axiomatized biology—from which valid theorems can be derived—should be a holy grail for theoretical biology and I believe that modest goals toward this end are within reach. There is strong evidence for this based on the achievements of the Coreworld (“classic�), Tierra, Avida and many other computational evolutionary theory models in the literature.

An abstract biosphere, with any claim to being called natural, is necessarily more complicated than is considered practical or desirable by most theoreticians. A combined approach—including both theory and experiment—will be prudent for the foreseeable future.

Artificial Souls

Asher Peres (2004) wrote the following about the origin of the term “teleportation�:

I don't watch television and was suspicious of the term teleportation. In my dictionary I found the definition, “theoretical transportation of matter through space by converting it into energy and then reconverting it at the terminal point.� I protested that this was not at all what we had in mind, but Charlie reassured me, saying that we would cite Roger Penrose's 1989 book, The Emperor's New Mind. I threatened that if we cited it, I would not be a coauthor. ... We had other semantic problems: I proposed stating that the quantum state was disembodied and reincarnated. This was found to be unacceptable. Later, when a newsman asked me whether it was possible to teleport not only the body but also the soul, I answered, “only the soul.� Even that was a gross oversimplification.

Could it be—not necessarily for life as we understand it—that quantum teleporation is the only way to disembody some lifeforms into classical information (in their own world)? What if we can build quantum biomolecular life in the real world (and evolution has not already done it)? Are such quantum lifeforms different in kind from classical lifeforms? The computational investigations of this thesis seem to collide with many philosophical and even theological puzzles. I don't have ready answers to the above questions; I think further investigation is a worthwhile long-term pursuit.

Conclusion and Future Directions

In this thesis, I have speculated that complicated “difficult to write down� quantum histories could be precisely the ones that give the greatest selective advantage to the programs that enact them; the length, in bits, of these histories could easily exceed the maximum apparent, entropy of the whole biosphere. Thus, the standard maxim that a complexity measure should “reward� intermediate measures of complexity between total randomness and total order is not necessary, in this case. Simply equating the complexity of a quantum mechanical biosphere with the length, in bits, of its compact description, or actual entropy, seems to capture the intuitive definition of “complexity�. Similarly, such a complexity measure is consistent with a gradual “open ended evolution� since the primary gain in complexity comes from the quantum operations being added to their qubits' histories and this can go on for a period of time exponential—or quadratic for stabilizer states—in the apparent entropy of the biosphere (at which point it becomes more compact to just store the whole quantum state).

A natural biosphere has multiple time and space scales at which different, biologically important, phenomena occur; nutrients and energy flow through natural biospheres, are used or consumed by the inhabitants, and ultimately re-cycled for use by future generations. For the foreseeable future, theoretical investigation of the abstract biosphere described in this thesis will be the only avenue for exploring evolutionary processes of similar complexity to the ones that occurred over the four billion years of Earth's history. Never-the-less, investigation of the quantum coreworld should also leverage the rapid increase in classical computing power and even the availability of modest quantum computers to experimentally explore the abstract world described here. It will be a long time before such advances could rival the awesome resources of the biosphere but—eventually with enough poking and prodding—a human, or super-human, intelligence will surely wake-up in an artificial world.

In pursuing the intellectual puzzles presented by the quantum coreworld, I have always tried to keep an open mind to the ethical challenges that accompany such research. As we consider life as it might be—and demystify life as it is—these ethical challenges may ultimately prove to be more perplexing than the typical hurdles that preoccupy computer science theorists.

References

• Aaronson S and Gottesman D. (2004) Improved Simulation of Stabilizer Circuits. Phys Rev A. 70:052328. ArXiv:quant-ph/0406196.

• Bennett CH and Brassard G. (1984) An update on quantum cryptography. In Advances in Cryptology – proceedings of Crypto'84, 475-480, Springer Verlag.

• Bennett CH, Brassard G, Crepeau C, Jozsa R, Peres A, and Wootters W. (1993) Teleporting an unknown quantum state via dual classical and EPR channels. Physical Review Letters 70:1895-1899.

• Chow SS, Wilke CO, Ofria C, Lenski RE, Adami C. (2004) Adaptive Radiation from Resource Competition in Digital Organisms. Science 305:84-86.

• Corno F, Sanchez E, Squillero G. (2003) Exploiting co-evolution and a modified island model to climb the core war hill. In the proceedings of CEC03: Congress on Evolutionary Computation, December 8-12, 2003, Canberra, Australia, 2222-2229, IEEE.

• Cross A. (2005) Synthesis and Evaluation of Fault Tolerant Quantum Computing Architectures. MSc thesis. MIT-EECS.

• Dewdney AK. (1984) In the game called core war hostile programs engage in a battle of bits. Scientific American 250(5):15–19.

• Dewdney AK. (1987) A program called MICE nibbles its way to victory at the first Core War tournament. Scientific American 256(1):8-11.

• Dittrich P, Ziegler J and Banzhaf W. (2000) Artificial Chemistries - a Review. Artificial Life 7:225-275.

• Fredkin E. (2003) An Introduction to Digital Philosophy. International Journal of Theoretical Physics 42(2):189-247.

• Fredkin E. (2004) Five big questions with pretty simple answers. IBM Journal of Research and Development 48(1):31-45.

• Gottesman D. (1999) The Heisenberg Representation of Quantum Computers. In Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, eds. S. P. Corney, R. Delbourgo, and P. D. Jarvis, 32-43, Cambridge, MA, International Press. Longer version quant-ph/9807006.

• Lloyd S. (2002) Computational capacity of the universe. Physical Review Letters 88:237901.

• Margolus N. (1988) Physics and Computation. PHD thesis. MIT/LCS/TR-415

• Margolus N. (2003) Looking at Nature as a computer. International Journal of Theoretical Physics 42(2):309.

• Misevic D, Lenski RE, and Ofria C. (2004) Sexual reproduction and Muller's ratchet in digital organisms. In the proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE IX), 340-345, Boston MA, Sept 12-15.

• von Neumann J. (1966) Theory of Self-Reproducing Automata. Arthur Burks editor. Univ. of Illionois Press.

• Nielsen MA and Chuang IL. (2000) Quantum computation & quantum information. Cambridge University Press; ISBN: 0521635039.

• Ofria C, Adami C, and Collier TC. (2002) Design of Evolvable Computer Languages. IEEE Transactions in Evolutionary Computation 17:528-532.

• O'Neil B. (2003) Digital evolution. PloS Biology 1(1):11-14.

• Pedulla ML, Ford ME, Houtz JM, Karthikeyan T, Wadsworth C, Lewis JA, Jacobs-Sera D, Falbo J, Gross J, Pannunzio NR, Brucker W, Kumar V, Kandasamy J, Keenan L, Bardarov S, Kriakov J, Lawrence JG, Jacobs WR Jr, Hendrix RW, Hatfull GF. (2003) Origins of highly mosaic mycobacteriophage genomes. Cell. 113(2):141.

• Peres A. (2004) What is actually teleported? IBM Journal of Research and Development 48(1):63-69.

• Rasmussen S, Knudsen C, Feldberg R and Hindsholm M. (1990) The Coreworld: emergence and evolution of cooperative structures in a computational chemistry. Physica D, 42:111–134.

• Ray TS. (1992) An approach to the synthesis of life. In C. G. Langton, C. Taylor, J.D. Farmer, and S. Rasmussen, editors, Artificial Life II, 371–408, Redwood City, CA, Addison-Wesley.

• Shalizi C. (2003) Complexity measures, unpublished, visited on the web January 31st, 2005 at: http://http://cscs.umich.edu/~crshalizi/notebooks/complexity-measures.html

• Shor, P. (1994) Algorithms for quantum computation: discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science, 124-134, IEEE.

• Stallman, R. (2002). Free Software, Free Society: Selected Essays of Richard M. Stallman. Edited by Joshua Joshua Gay. GNU Press. ISBN 1882114981

• Szostak JW, Bartel DP, Luigi P. (2001) Synthesizing life. Nature 409:387-390.

• Toffoli T. (2004) A pedestrian's introduction to spacetime crystallography. IBM Journal of Research and Development 48(1):13-29.

• Vowk B, Wait AS, Schmidt C. (2004) An Evolutionary Approach Generates Human Competitive Corewar Programs. In Artificial Chemistry and its Applications, part of ALIFE IX. Sept. 12-15, Boston, MA.

• Wait AS. (2004) The Quantum Coreworld: competition and cooperation in an artificial ecology. In the proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE IX), 280-285, Sept. 12-15, Boston, MA.

• Weinbauer MG and Rassoulzadegan F. (2004) Are viruses driving microbial diversification and diversity? Environmental Microbiology 6(1):1-11.

• Wolfram S. (2002) A New Kind of Science. Wolfram Media. ISBN 1579550088

• Zuse K. (1969) Rechnender raum, Vieweg (Braunschweig); translated as "Calculating Space," Tech. Transl. AZT-70-164-GEMIT, MIT Project MAC, Cambridge, MA.

Appendices

Appendix I: A simple replicator

;redcode
;name myMice
;standard 2004
 
deltap equ CORESIZE/4

step      equ              64
steps     equ              16

first     DAT               0,          last-first  
begin     MOV           #step,                last
reset     MOV  #last-search+1,              search
          MOV          #steps,               count
loop      DJN.P        energy,             >search
count     DJN            loop,              #steps
search    JMP           reset,                   0

;get all the priv.
continue  JMP            loop,             <search
 
;found some priv. so continue (or boot)
energy    IJN.Q      continue,               begin 
          IJN.P             1,            continue

;check (and set) the lock   
check     IJN.Q          next,               @last

;spawns a new copy in the core
          MOV     #last-first,               first
          ADD              #1,                last 
rep       MOV          @first,               <last 
          DJN             rep,               first
          IJN.P             1,               @last
          ADD   #last-first-1,                last
next      ADD           #step,                last

;check (and set) the dual lock
checkDual IJN.QD        check,               @last

;spawns a new copy in the dual core
          MOV     #last-first,               first 
          ADD              #1,                last
rep2      MOV.ID       @first,               <last
          DJN            rep2,               first 
          IJN.PD            1,               @last
          ADD   #last-first-1,                last
last      JMP           check,                   0

;boot code -- not copied

start     IJN.Q             1,                last
          IJN.P             1,                begin
          end           start