Density Proof
- Richard Bowles and I have been working on capacity.
- We start out with n neurons. Divide these into N
primitive non-overlapping CAs.
- Divide these into 4 groups called A, B, C, and D with individual
members being A1, A2 etc.
- A 3/4 CA is made up of four primitive CAs, one from each
group. If either 2 are activated, the third will become
activated (completion).
- There are O(N^2) of these 3/4 CAs.
- Make 3/4 CAs of AxBxCyDy
- Clearly there are N^2 of these
- Make the connection strength great enough so that
3 will activate the fourth, but 2 won't.
- No other 3/4 CA (e.g. AxBzCyDy) gets three
inputs, so no spurious CAs will be activated.
- A similar argument holds for 5/6 CAs making O(N^3),
and k-1/k CAs making O(N^(k/2))
- Note that a 1/2 CA doesn't make sense, and a 3/5 CA will have
O(N^2) also.
- We submitted this one to Theory of Natural Computing.
- Richard has got a simulation of this working and will be submitting
that as the basis of his doctoral thesis.
