2-STATE, R=1 CELLULAR-AUTOMATON THAT CLASSIFIES DENSITY

Authors
CAPCARRERE MS SIPPER M TOMASSINI M
Citation
Ms. Capcarrere et al., 2-STATE, R=1 CELLULAR-AUTOMATON THAT CLASSIFIES DENSITY, Physical review letters, 77(24), 1996, pp. 4969-4971
Citations number
11
Categorie Soggetti
Physics
Journal title
Physical review letters → ACNP
ISSN journal
00319007
Volume
77
Issue
24
Year of publication
1996
Pages
4969 - 4971
Database
ISI
SICI code
0031-9007(1996)77:24<4969:2RCTCD>2.0.ZU;2-F
Abstract
It has recently been shown that no one-dimensional, two-state cellular automaton can classify binary strings according to whether their dens ity of Is exceeds 0.5 or not. We show that by changing the output spec ification, namely, the final pattern toward which the system should co nverge, without increasing its computational complexity, a two-state, r = 1 cellular automaton exists that can perfectly solve the density p roblem.