It is easy to write down formulas for the double exponential number of rules. For example n^n^s rules of CAs with n states and neighborhood of size s.
For locally defined properties it is quite easy as well. But the interesting questions regard some global properties like reversibility, surjectivity, number-conservation, monotonicity and such. Are there any estimates for the size of such CA families?
This doesn't answer your question exactly, but the paper "How Common Can Be Universality for Cellular Automata?" (Theyssier 2005) considers the asymptotic density of intrinsically universal cellular automata when the neighborhood is fixed and the alphabet size grows. The main result is that within the subclass of captive CA, intrinsic universality has asymptotic density 1. It is also shown that captive CA and CA that have an invariant sub-alphabet have asymptotic density 0, and explicit bounds can be deduced from the proofs.
Such papers are not known to me but it might be interesting to know related information, and quite important, that cellular automata belong to complex systems aka complexity. It would be really worth to try to search in those waters (you can try to start with the book that I edited in 2010 on the topic).
As we all know complex systems are expressing self-organization, emergence, emergent multilevel and virtual emergent structures, self-repair, self-replication, we can go on for a long in this way.
What does it mean with respect to your question? Unless we do possess a theory of complex systems, we have very few mathematical tools in our hands to make reasonable predictions about CA and their behavior.
There are not existing simple formulas because the behavior of CS is pretty convoluted and hence we do not know where to start.
This answer aims to open a wider view of your question and search.
- Badges
- Science topic
- Similar topics
- Papers