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 |