Memory

• The length of (linear) GP programs needed for convergence of distribution of fitness depends on
• Instruction set (i.e. type of computer)
• number of bits of memory $N$.

  Simple computers give scaling laws or upper bounds of:

  $\exp N$, O($N \log N$), O($N$), O(1)

• AND NAND OR NOR, can implement any Boolean function
• A randomly chosen instruction: 50% set a bit, 50% clear a bit

  I.e. 50% toggle a randomly chosen bit in memory,
  50% do nothing

  Limit $\pi$ exists. In the limit each memory pattern is equally likely. Output register is part of memory. So each output must be equally likely.

• $\vert\vert \mu_{l} - \pi \vert\vert^{2} \le \frac{1}{4}\sum_{j=1}^{N} \frac{N!}{j! (N-j)!} \left\vert 1-\frac{j}{N}\right\vert^{2l}$

  Deviation from limit is bounded by a sum for each eigenvalue [Diaconis, 1988, pages 28-30]

• $\vert\vert \mu_{l} - \pi \vert\vert^{2} \le \frac{1}{2}\left(e^{N e^{-\frac{2}{N}}{l}}-1\right)$

• Requiring $\vert\vert \mu_{l} - \pi \vert\vert$ not to exceed 10% gives the upper bound $l \le \frac{1}{2}N (\log(N) + 4)$

• informally $l \le \frac{1}{2}N (\log(m) + 4)$ since need to randomise only $m$ output bits, not whole of memory.