Design of Logic Environments

The "nand" logic operation is considered functionally complete, which means that using only nands it is possible to build any othr logic operation. For this reason, we have chosen to give Avida organisms "nand" as one of their instructions, and we can thereafter approximate the difficulty of all of the other tasks by the number of nands it takes to complete them.

The nand operation functions as follows:

All 2-input logic operations can be described in the same fashion. There are always 4 pairs of possible inputs, and the function is described by the four bits in the right-hand column. This means that there are, theoretically 16 possible 2-input logic functions, but some of these are trivial.

Four of the logic operations require no nands at all. They are ALL-ZEROs, ALL-ONEs, ECHO-A, and ECHO-B. In Avida we combine ECHO-A and ECHO-B into a single task (ECHO) and we ignore ALL-ZEROs and ALL-ONEs since they are trivial (a bit string with all zeros is just "0" and a bit string with all ones evaluates to "-1").

Given one NAND, we can determine whats possible by NANDing all pairs of our no-nands values together and see what we get. We have our two inputs (A and B) and out ALL-ZEROs and ALL-ONEs to work with.

Glancing through this, it looks like we get four new functions: NOT-A, NOT-B, A-NAND-B, and B-NAND-A. We also see that ALL-ZEROS and ALL-ONES get us nothing new that we can't get from the other options, so we're going to ignore them from here on out.

Looking closer at the new functions, we realize the A-NAND-B is identical to B-NAND-A (they both produce 1,1,1,0 in the last column), so we lump them together into a single NAND function. With this, we discover that with a single nand we have uncovered three more 2-input logic functions, for a total of seven so far.

They are:

We will also lump the NOT-A and NOT-B together and create the single task NOT, which will identify either of them in Avida. Of course, for the purpose of determining what other tasks can be built off of these, we will consider both separately.

To continue this process, we take our current state (and nand everything together again.) Anything new we get here will be function that cannot be performed using fewer than two nands.

Here it looks like we've found four new functions: A-OR-NOT-B, B-OR-NOT-A, A-OR-B and A-AND-B. But how many nands do they each require? Clearly the first two are a 1-nand function nanded with a 0-nand function, thus they require 2 nands each. The A-OR-B is clear-cut in the other direction. To get this function you must nand NOT-A to NOT-B. Each of these already cost 1 nand to build. Add to that the additional nand of combining them and you realize the A-OR-B costs 3-nands.

The same logic can almost be used for A-AND-B until we realize that both inputs are the same function. As such, we would only need one nand to construct it, and one more to nand it to itself, for a total of two nands.

When converting these to tasks in Avida, we note the symmertry between A-OR-NOT-B and B-OR-NOT-A and create a single "or not" task called ORN.

We have now found 11 of the 16 possible operations. The last 5 will arise by repeating this process. For each of them we keep track of the fewest nands we can build it with.

The final five are: A-AND-NOT-B and B-AND-NOT-A (combined into ANDN) costing 3 nands, A-NOR-B , A-XOR-B, and A-EQU-B.

This entire process can easily scale up to three-input or higher logic functions, but by that point you'd probably want to automate the process. When you move to three inputs, you have 8 combinations of inputs (2^3). Each of these combinations comes out to a zero or one for any specific logic function. This means that there are 2^8 = 256 unique logic functions. When we remove symmetries (given that inputs can come in in any order), we only get 68 new logic operations out of this.