It has recently been shown that no one-dimensional, two-state cellular automaton can classify binary strings according to whether their density of $1$s exceeds $0.5$ or not. We show that by changing the output specification, namely, the final pattern toward which the system should converge, without increasing its computational complexity, a two-state, $r=1\mathrm{}$ cellular automaton exists that can perfectly solve the density problem.

• Received 26 August 1996

DOI:https://doi.org/10.1103/PhysRevLett.77.4969