Hand written Logic Nine Programs

These programs were written as supplementary material for The Evolutionary Origin of Complex Features from 2003: http://myxo.css.msu.edu/papers/nature2003/. Here are programs that will trigger the nine default logic tasks with the default instruction set.

The following hand-written programs perform the various one- and two-input logic operations. These programs appear to be the shortest ones to perform these operations that do not depend on the initial content of stacks and registers (whose initial contents are represented by a '?' below). However, it has not been proven that these are the shortest programs. None of these programs permit self-replication; rather, they merely perform a calculation.

ECHO
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	IO	?	Y	?	?	X
NOT
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	push	?	X	?	X, ?
3	pop	?	X	X	?
4	nop-C
5	nand	?	~X	X	?
6	IO	?	Y	X	?	~X
NAND
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	IO	?	X	Y	?	?
3	nop-C
4	nand	?	X nand Y	Y	?
5	IO	?	Z	Y	?	X nand Y
OR_N
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	IO	?	X	Y	?	?
3	nop-C
4	nand	?	X nand Y	Y	?
5	nand	?	X or ~Y	Y	?
6	IO	?	Z	Y	?	X or ~Y
AND
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	IO	?	X	Y	?	?
3	nop-C
4	nand	?	X nand Y	Y	?
5	push	?	X nand Y	Y	X nand Y, ?
6	pop	?	X nand Y	X nand Y	?
7	nop-C
8	nand	?	X and Y	X nand Y	?
9	IO	?	Z	X nand Y	?	X and Y
OR
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	push	?	X	?	X, ?
3	pop	?	X	X	?
4	nop-C
5	nand	~X	X	X	?
6	nop-A
7	IO	~X	Y	X	?	X
8	push	~X	Y	X	Y, ?
9	pop	~X	Y	Y	?
10	nop-C
11	nand	~X	~Y	Y	?
12	swap	Y	~Y	~X	?
13	nop-C
14	nand	Y	X or Y	~X	?
15	IO	Y	Z	~X	?	X or Y
AND_N
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	IO	?	X	Y	?	?
3	nop-C
4	nand	?	X nand Y	Y	?
5	nand	?	X or ~Y	Y	?
6	push	~X	X or ~Y	Y	~X or Y, ?
7	pop	~X	X or ~Y	X or ~Y	?
8	nop-C
9	nand	?	~X and Y	X or ~Y	?
10	IO	?	Z	X or ~Y	?	~X and Y
NOR
#	Inst	AX	BX	CX	Stack	Output
1	IO	?	X	?	?	?
2	push	?	X	?	X, ?
3	pop	?	X	X	?
4	nop-C
5	nand	~X	X	X	?
6	nop-A
7	IO	~X	Y	X	?	X
8	push	~X	Y	X	Y, ?
9	pop	~X	Y	Y	?
10	nop-C
11	nand	~X	~Y	Y	?
12	swap	Y	~Y	~X	?
13	nop-C
14	nand	Y	X or Y	~X	?
15	push	Y	X or Y	X	X or Y, ?
16	pop	Y	X or Y	X or Y	?
17	nop-C
18	nand	Y	X nor Y	X or Y	?
19	IO	Y	Z	X or Y	?	X nor Y
XOR
#	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	IO	X nand Y	Z	X or ~Y	?	X xor Y
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