Density Proof
- We start out with n neurons. Divide these into N
primitive non-overlapping CAs.
- Divide these into 3 groups called A, B, and, C with individual
members being A1, A2 etc.
- A 2/3 CA is made up of three primitive CAs, one from each
group. If either 2 are activated, the third will become
activated (completion).
- There are O(N^2) of these 2/3 CAs.
- Add one 2/3 CA (say A1-B1-C1).
- This eliminates pairs with (A1-B1, A1-C1, and B1-C1)
- For each 2/3 CA ~3N triples are eliminated, but there
N^3 triples and N^2 pairs.
- Another way to put this is that each primitive CA can
participate in O(N) 2/3 CAs because each 2/3 CA just
eliminates 2 that it can participate in.
- A similar argument holds for 3/4 CAs making O(N^3),
and k/k+1 CAs making O(N^k)
- Note that a 1/2 CA doesn't make sense, and a 3/5 CA will have
O(N^3) also.
- We haven't submitted this one for publication, but Richard Bowles
and are working on it right now.
