next up previous
Next: So what? Up: How long are Long Previous: AND NAND OR NOR

Conclusions

How long are long programs?
Depends on type of machine, size of its memory $N$:

1. Any computer $\le 2.3\ a\ I^{a}$ ($I$ number of instructions)

2. Cyclic computer $0.06 \cdots 0.35 \times\ 2^{2N}$

3. Bit flip computer $\le \frac{1}{4}(N+1)(\log(m)+4)$ ($m$ output bits)

4. Average computer $\le {15 + 2.3 m}/{\log{I}}$

5. Four Boolean function computer $\le \frac{1}{2}N(\log(m)+4)$

Note unless inputs are write protected, fraction of interesting programs $\leadsto 0$.

Number of solutions grows exponentially with size

$\frac{1}{4}(l+1)(\log(l)+4)$ generations needed for mutation alone to scramble bit string GA ($l$ chromosome length)



Bill LANGDON 2002-07-17