This section describes molecules, motifs, bricks, cores, coreworlds, the way these are arranged into an ecology or QVM. I also provide a sketch of the QVM's: use of pseudo-randomness, autonomous generation of new motifs, capacity for human intervention, relationship with the game Corewar, compression/entropy, and revision/build/test strategy. The QVM is designed so that motifs are (somewhat) insensitive to arbitrary constants: in particular, the number of molecules per brick and the total number of molecules in the QVM itself.
Molecules in the coreworld are described with an extended Redcode language that supports an energy/nutrient currency called privilege. Every molecule in the coreworld chemistry has one: instruction field (including a modifier field, A mode, B mode and tag), A field, B field, privilege field, and qubit field; each of these are described in the subsequent sections. For a given QVM, the classical part of a molecule-all but the qubit field-can be represented with a small constant number of classical bits (i.e. as one line in a text file).
The instruction field determines the type of thing that each molecule can do. The available instructions are listed in Table 1. The modifier specifies what field(s) an instruction uses. Modifiers are listed in Table 2. The A mode determines how the A-field is to be interpreted and the B mode determines how the B-field is to be interpreted. Valid addressing modes are listed in Table 3. The tag is a cryptographic hash of the brick in which the molecule entered the world (see the section on bricks and new motifs below.) The MOV.I instruction is the only way to duplicate the instruction field; it requires one unit of privilege; this gives motifs in the coreworld a simple, natural metabolism (see also discussion.) Table 1, Table 2 and Table 3 can be found here.
Several departures from, 1994, standard Redcode can be seen in Table 1. 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 field-IJN has an application as a "concurrency primitive" (atomic test and set). IJN also plays a role in adding privilege when used in combination with the new ".P" modifier-which specifies that the instruction deals primarily with the privilege field-causing a new thread of execution. The ".D" modifier specifies that the B-pointer refers to the dual core (see the discussion of bricks below). The ".E" modifier consumes privilege in exchange for a greater likelihood of execution; the ".E" modifier is one way that privilege is permanently removed from the world. All modifiers are listed in Table 2. Finally, all valid addressing modes are listed in Table 3.
The A-field and B-field are straightforward data fields. They can be integers between 0 and core-size - 1. Since the number of molecules in one core, coresize, can change-see bricks, cores, and coreworlds-from fluctuation to fluctuation these fields are automatically sign extended or truncated to accommodate the change.
Privilege is a positive integer. Its value can be unlimited, in principle, but it cannot be greater than the total privilege in the world, which is itself bounded. Coreworld style molecules require privilege greater than zero to be active, while corewar style molecules use corewar task-queues. Corewar molecules, that do not use privilege, are removed from the world at each fluctuation. Privilege is used to execute more quickly and is required by "MOV.I" to synthesize new instruction fields.
Quantum cryptography (Bennett and Brassard 1984), quantum teleportation (Bennett et al. 1993), quantum factoring (Shor 1994) and other QIP algorithms can be simulated on a classical computer for small numbers of quantum bits. The classical part of the quantum coreworld chemistry can perform quantum operations on the qubit field by recording the history of operations on the field and their time-stamps. 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 the simulator adds an axiom to quantum mechanics that, essentially, guarantees only small states are simulated. That is, the simulator does additional measurements to collapse states. Since simulated states are still far larger than anything experimentally realized this may not pose too much of a restriction.
|Figure 3. Four Motifs in the coreworld.|
Individual motifs in the coreworld, by definition, are contiguous sequences of coreworld style molecules. Motifs are treated as units because they are moved together during fluctuations. A simple one-molecule motif is shown in Figure 3; it is known as an "Imp" and it circles around the core until it is cleared. The "Imps" in Figure 3 can catch up to each other, from time to time, briefly creating a larger multiple-molecule motif. As mentioned previously, the MOV.I instruction is the only way to copy the instruction field-the "executable" part of a molecule, if it has privilege-and this operation consumes one unit of privilege. The privilege can be recovered by converting the new molecule back into privilege. If there is insufficient privilege to make a copy and continue executing, the active molecule is automatically converted into privilege. So, an "Imp" in the coreworld still works in the expected way.
A core is made of at least eight bricks and a coreworld is made of at least eight cores; recall Figure 1, this is the smallest possible coreworld. A molecule can act on any molecule in the same core and one eighth of the neighboring core. Every molecule in a core has a dual molecule which is illustrated in Figure 4.
|Figure 4. Dual locations in the Coreworld; red bricks have duals along the X axis, green bricks along the Y axis and blue bricks along the Z axis.|
The number of bricks in a core is "preferentially" eight but it can vary from fluctuation to fluctuation. So unlike Corewar, coresize is not fixed in the coreworld, and motifs must not depend on it being a particular value. The number of molecules per brick, however, is constant throughout the ecology. Whether or not the coreworld is actually insensitive to bricksize or the total size of an ecology, as designed, is a matter of further experimental investigation.
A coreworld-in addition to a description of the molecules and their quantum histories-must keep track of the number of bricks in the X-Y-Z dimensions, a seed for the cryptographic pseudo-random-number-generator, and the probability of a fluctuation (or temperature) T. Since coreworlds are stitched together into an ecology in a systematic way, the size of each coreworld (worldsize) and which coreworld(s) it interacts with is implicit in its name. Every molecule, similarly, belongs to a particular brick and a particular core for the current values of X,Y,Z and worldsize; this relationship is implicit and does not need to be stored in the world's description.
Further details are provided in the next section, Ecology.
As mentioned in the introduction, coreworlds are stitched together to make an ecology. The way this works is that control-nots are removed from the histories of qubits in bricks at the edge of a coreworld if those control-nots refer to a molecule outside that brick. Then, when molecules are exchanged during a fluctuation, only internal entanglement remains; no entanglement is allowed across coreworld boundaries. Figure 5 shows four successive QVMs; a brick size of 210 is implicit in the calculation of the number of molecules in the QVM and the number of bricks in the smallest permitted coreworld is 26 (recall Figure 1).
|Figure 5. Four QVMs (or ecologies); the size of the QVM, in molecules, is given by s and the number of different values, in the QVM, for worldsize is specified by n.|
In each successive QVM, above, the middle Coreworld is twice the size of its predecessor. The coreworlds in each column halve in size as you move away from the center; the left-most-edge is connected to the right most edge of the figure (the ecology is toroidal.) A visualization of the bricks for these four ecologies-similar to Figure 1-is forthcoming. Real time 3D movies, directly accessible from http://science.fiction.org are also forthcoming.
A cryptographically secure pseudo-random-number-generator (PRNG) can guarantee that there is no way to adapt or predict the "randomness" of the coreworld. Please see Goldreich (2001) for a thorough discussion of the precise guarantees offered. Practical PRNGs, like the one used in the QVM, are thought to be secure but have weaker guarantees-this should be further examined.
The Quantum Coreworld gets its name from the Coreworld of Rasmussen et al. (1990) which was closely based on the game Corewar. In that work, the 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). In the Coreworld, a different motif will be generated at random-from a probability distribution known to be biased for good motifs while keeping the probability of generating the same motif twice negligibly small-in every brick at the bottom of the coreworld's of the QVM.
Participants interested in intervening in the Quantum Coreworld ecology can write their own motifs and submit them at http://science.fiction.org to see the results. One brick-per fluctuation-can be uploaded (that brick will not be generated spontaneously).
At the end of every fluctuation-before motifs begin to execute under their own control-half of the biosphere is empty (except for distributed free privilege). 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-as specified in bricks, cores and coreworlds-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.) 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 Corewar contests provide a clean way to introduce mutation into the coreworld since regular coreworld style motifs could easily be damaged by the Corewar style programs.
In his excellent survey of complexity measures Shalizi (2002) discusses a wide swath of the literature on this topic and in particular writes about the failings of using off-the-shelf compression software as a proxy for entropy. As it happens, I am using the compressed file lengths of QVMs in precisely that way (i.e. as a proxy for the QVMs actual entropy and, similarly without the quantum histories, for apparent entropy. See, also, the discussion.) Why do I think this is a good idea? Primarily, because the data is readily available. Obviously, if it turns out that an upward trend in the compressed file lengths of QVM snapshots is not evidence for open-ended evolution but evidence for some rarely exercised defect in the compression algorithm this will need to be revisited.
Multiple developing branches of the QVM software are desirable for experimenting with various alternatives or to simply fix bugs. For example, to test the hypothesis that the QVM is insensitive to small changes in its total size, or the size of individual bricks, a custom version of the software can be used to test this. Similarly, it is also desirable to efficiently incorporate improvements in upstream software components. Changes to the QVM software can cause:
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 random number generators. The build/test strategy most cope with these different possibilities. I am in the process of implementing a change management/build/test system for the QVM that facilitates parallel development.
This whole project has been developed according to Free Software ideals (Stallman 2002); without the efforts of thousands of volunteers this work would not have been possible.