Phys. Rev. Lett. 77, 4969 - 4971 (1996)Two-state, r = 1 Cellular Automaton that Classifies Density |
Mathieu S. Capcarrere, Moshe Sipper, and Marco Tomassini
Logic Systems Laboratory, Swiss Federal Institute of Technology, IN-Ecublens, CH-1015 Lausanne, Switzerland
Received 26 August 1996
It has recently been shown that no one-dimensional, two-state cellular automaton can classify binary strings according to whether their density of 1s 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.
©1996 The American Physical Society
URL: http://link.aps.org/abstract/PRL/v77/p4969
DOI: 10.1103/PhysRevLett.77.4969
PACS: 89.80.+h, 02.70.Rw, 07.05.Bx
[ Abstract | Previous article | Next article | Issue 24 ]
About PROLA | Terms and Conditions | Subscriptions | Search | Help
Content in PROLA © 2008 by The American Physical Society All rights reserved. PROLA™ is a trademark of The American Physical Society. Use of APS online journals implies that the user has read and agrees to the Terms and Conditions in the Subscription Agreement.