Glossary

add

This instruction reads in the contents of the BX and CX registers and sums them together. The result of this operation is then placed in the ?BX? register.

Bitwise

A bitwise operation is one in which each bit is treated independently of all the other bits in a number. Thus if a logical AND was performed between two bitstrings, the first bit of the first string would be ANDed to the first bit in the second string, the second bit to the second bit and so on.

Complement-Template

The complement of a template is found by taking each no-operation instruction that makes up that template, and shifting it to the next in alphabetical order, looping around at the end. Thus, in the default instruction set, nop-A -> nop-B -> nop-C -> nop-A. The template "nop-B nop-A nop-C nop-C" has the complement "nop-C nop-B nop-A nop-A".

Computational Merit

A rating to determine the number of additional SIPs an organism has earned by performing tasks. The number is a multiple of the default SIPs they would otherwise receive.

CPU

Each individual organism in an Avida population has its own virtual central processing unit (CPU) that executes its genome. An Avida CPU consists of a memory space with four heads pointing to specific locations in that memory, three registers, two stacks, and input-output buffers.

dec

This instruction reads in the contents of the ?BX? register and decrements it by one.

Genome

The genome of an organism is the original, underlying program that controls the behavior of that organism. The memory space in the CPU of that organism is initialized to the genome, but will change with time. A genotype is is determined by a unique genome sequence.

Genotype

A genotype is a unique sequence of instructions that make up a genome of an organism. Any two organisms with identical genomes are considered to be the same genotype.

Gestation Requirement

The total number of SIPs required for an organism to produce an offspring.

h-alloc

This instruction allocates additional memory for the organism up to the maximum it is allowed to use for its offspring.

h-copy

This instruction reads the contents of the organism's memory at the position of the read-head, and copies that to the position of the write-head. If a non-zero copy mutation rate is set, a test will be made based on this probability to determine if a mutation occurs. If so, a random instruction (chosen from the full set with equal probability) will be placed at the write-head instead.

h-divide

This instruction is used for an organism to divide off a finished offspring. The original organism keeps the state of its memory up until the read-head. The offspring's memory is initialized to everything between the read-head and the write-head. All memory past the write-head is removed entirely.

Heads

Each CPU has four heads associated with it. The first is the instruction pointer (IP) which determines the next instruction to be executed by the CPU. After each execution, the IP is automatically advanced (unless the instruction executed dictates otherwise). The second is the read-head (RH), which determines what instruction is copied from a copy command, and then the write-head (WH) determines the position it is copied to. Finally, the flow-head (FH) is used to mark positions in the genome to move the other heads. The flow-head is commonly used to mark the beginning of a loop to jump the IP back there from the loop's end.

h-search

This instruction will read in the template that follows it, and find the location of a complement template in the code. The BX register will be set to the distance to the complement from the current position of the instruction-pointer, and the CX register will be set to the size of the template. The flow-head will also be placed at the beginning of the complement template. If no template follows, both BX and CX will be set to zero, and the flow-head will be placed on the instruction immediately following the h-search.

if-label

This instruction reads in the template that follows it, and tests if its complement template was the most recent series of instructions copied. If so, it executes the next instruction, otherwise it skips it. This instruction is commonly used by an organism to determine when it has finished producing its offspring.

if-less

This instruction compares the ?BX? register to its complement. If ?BX? is the lesser of the pair, the next instruction (after a modifying no-operation instruction, if one is present) is executed. If it is greater or equal, then that next instruction is skipped.

if-n-equ

This instruction compares the ?BX? register to its complement. If they are not equal, the next instruction (after a modifying no-operation instruction, if one is present) is executed. If they are equal, that next instruction is skipped.

inc

This instruction reads in the contents of the ?BX? register and increments it by one.

Input-Output

Each CPU in Avida is supplied with 3 input values of 32 bits each. The IO instruction is used by the organisms to get an input (cycling through the three options) into a register and to output numbers from a register. Each output is compared to all inputs to determine if any tasks (by default, specified logical computations) have been performed by the organism.

Instruction

Each position in an organism's genome or a CPU's memory consists of an instruction. Each instruction is associated with a specific function on the CPU when it is executed (expressed); in series these instructions lead to all of the complex behaviors of the organisms.

IO

This is the input-output instruction. It takes the contents of the ?BX? register and outputs it, checking it for any tasks that may have been performed. It will then place a new input into ?BX?.

jmp-head

This instruction will read in the value of the CX register, and then move the ?IP? by that fixed amount through the organism's memory.

Logic

A logic operation has as inputs a collection of bits, and as an output a single bit. The operation itself is a unique map from the input bits to the output bits. In Avida, a logic operation is done in a bitwise fashion, so that the operation is effectively performed 32 times without error if a reward is granted.

Memory

A CPU contains a memory space to hold a sequence of instructions to be executed. The memory space is initialized to the genome of the organism, but it will be modified over the lifetime of the organism, typically as an offspring is produced. As section of the memory is then divided off to initialize the offspring.

mov-head

This instruction will cause the ?IP? to jump to the position in memory of the flow-head.

Mutation

A mutation is a random change of an instruction from the genome of an organism. There are three main times that mutations can occur: point mutations will happen randomly through time, with an equal probability at every site, copy mutations occur when a site is actively being copied, and divide mutations occur when an organism is splitting off an offspring.

nand

This instruction reads in the contents of the BX and CX registers (each of which are 32-bit numbers) and performs a bitwise nand operation on them. The result of this operation is placed in the ?BX? register. Note that this is the only logic operation provided in the basic Avida instruction set.

Nop-Head-Notation

A head abbreviation (IP, RH, WH, or FH) surrounded by question marks refers to that head being used as a default, when the instruction in question is being executed, but if the instruction is followed by a no-operation (nop) instruction, the nop will alter the register used. A nop-A instruction indicates the instruction pointer (IP), nop-B is the read-head (RH), nop-C is the write-head (WH), and there is no way to use the flow-head (FH) unless it is by default.

nop-instructions

The instructions nop-A, nop-B, and nop-C are no-operation instructions, and will not do anything when executed. They will, however, modify the behavior of the instruction preceding it (by changing the CPU component that it affects; see also nop-register notation and nop-head notation) or act as part of a template to denote positions in the genome.

Nop-Register-Notation

A register name (AX, BX, or CX) surrounded by question marks refers to that register being used by default when the instruction in question is being executed, but if the instruction is followed by a no-operation (nop) instruction, the nop will alter the register used. A nop-A instruction indicates AX, nop-B is BX, and nop-C is CX.

Organism

An organism in Avida consists of a unique genome and a CPU that expresses (executes) the code in that genome. A population in Avida is a collection of these organisms.

pop

This instruction removes the top element from the active stack, and places it into the ?BX? register.

Population

A population in Avida is a collection of digital organisms that interact and evolve over time.

push

This instruction reads in the contents of the ?BX? register, and places it as a new entry at the top of the active stack. The ?BX? register itself remains unchanged.

Registers

Each CPU in Avida contains three registers, each of which is made up of 32 bits. All math-based instructions operate on the registers, and various instruction will move the values in the registers around.

Replication Efficiency

This quantity is, for any genotype, the ratio of its genome length to its gestation requirement. The numerator is the number of instructions that must be copied during replication, while the denominator is the amount of energy needed to complete the life cycle. A genotype's expected replication rate, or fitness, is equal to its replication efficiency multiplied by its computational merit.

set-flow

This instruction moves the flow-head to the memory position denoted in the ?CX? register.

shift-l

This instruction reads in the contents of the ?BX? register, and shifts all of the bits in that register to the left by one, placing a zero as the new rightmost bit, and truncating any bits beyond the 32 maximum. For values that require fewer than 32 bits, it effectively multiplies that value by two.

shift-r

This instruction reads in the contents of the ?BX? register, and shifts all of the bits in that register to the right by one. In effect, it divides the value stored in the register by two, rounding down.

SIPs

SIPs are the basic unit of energy available to an organism. The more SIPs an organism has, the faster it can express the instruction sequence encoded by its genome. The phrase refers to Single Instruction Processing units. (These units are often called 'CPU cycles' in other contexts, but the notion of cycles confuses the fact that SIPs are the fundamental unit of energy in Avida.)

Stack

Each CPU in Avida has two stacks used for storage of numbers. The push and pop instructions are used to move numbers between the registers and the stack, and the swap-stk instruction toggles the active stack in use.

sub

This instruction reads in the contents of the BX and CX registers and subtracts CX from BX. The result of this operation is then placed in the ?BX? register.

swap

This instruction swaps the contents of the ?BX? register with its complement.

swap-stk

This instruction toggles the active stack in the CPU. All other instructions that use a stack will always use the active one.

Tasks

The organisms in Avida receive extra SIPs for performing specific computations. Every time an organism outputs a number, it is examined against the inputs to determine if any tasks have been completed. If the number of extra SIPs outweighs the number used to perform the task, the computation will typically be reinforced through natural selection. By default, the tasks in Avida are all logic operations that act upon the inputs in a bitwise fashion.

Template

A template (sometimes called a label) is a sequence of no-operation instructions used to mark regions of code withing a genome. Some instructions (such a h-search) are followed by a template; the complement of that template is then used to match against other templates. See the descriptions of the individual instructions for how they use templates.