Abstract
Recently there have been many attempts to evolve one-dimensional two-state cellular automata which classify binary strings according to their densities of 1's and 0's. The current best-known approaches involve particle-based systems of information transfer. A proof is given that there does not exist a two-state cellular automata which performs the task perfectly. This is true even in multiple dimensions.
- Received 9 January 1995
DOI:https://doi.org/10.1103/PhysRevLett.74.5148
©1995 American Physical Society