The following hand-written program appears to be the shortest
one using the set of available instructions that performs the EQU function,
and that does not depend on the initial content of stacks and registers
(whose initial contents are represented by '?' below). However, it has
not been proven that this is the
shortest program. Also, this program does not encode self-replication;
rather, but only performs the logic operation.
| EQU | ||||||
|---|---|---|---|---|---|---|
| # | Inst | AX | BX | CX | Stack | Output |
| 1 | IO | ? | X | ? | ? | ? |
| 2 | IO | ? | X | Y | ? | ? |
| 3 | nop-C | |||||
| 4 | push | ? | X | Y | X, ? | |
| 5 | nand | ? | X nand Y | Y | X, ? | |
| 6 | swap | ? | Y | X nand Y | X, ? | |
| 7 | nand | ? | X or ~Y | X nand Y | X, ? | |
| 8 | swap | X or ~Y | ? | X nand Y | X, ? | |
| 9 | nop-A | |||||
| 10 | pop | X or ~Y | X | X nand Y | ? | |
| 11 | nand | X or ~Y | Y or ~X | X nand Y | ? | |
| 12 | swap | X nand Y | Y or ~X | X or ~Y | ? | |
| 13 | nop-C | |||||
| 14 | nand | X nand Y | X xor Y | X or ~Y | ? | |
| 15 | push | X nand Y | X xor Y | X or ~Y | X xor Y, ? | |
| 16 | pop | X nand Y | X xor Y | X xor Y | ? | |
| 17 | nop-C | |||||
| 18 | nand | X nand Y | X equ Y | X xor Y | ? | |
| 19 | IO | X nand Y | Z | X xor Y | ? | X equ Y |
From the Supplementary Information for an article by Lenski, Ofria, Pennock & Adami on "The Evolutionary Origin of Complex Features" that appeared in Nature (8 May 2003), vol 423, pp 139-144.