Two-state, r= 1 cellular automaton that classifies density Academic Article uri icon


  • Abstract 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 cellular automaton exists that can perfectly solve the density problem.

publication date

  • January 1, 1996