Solving the Density Classification Task Using Cellular Automaton 184 with Memory
Christopher Stone
Department of Computer Science
University of the West of England
Bristol, BS16 1QY, United Kingdom
christopher3.stone@uwe.ac.uk
Larry Bull
Department of Computer Science
University of the West of England
Bristol, BS16 1QY, United Kingdom
larry.bull@uwe.ac.uk
Abstract
A type of memory based on the least mean square algorithm is explored on the density classification task, which is a well-known test problem for two-state discrete dynamical systems. In the absence of memory, there is no elementary cellular automaton that can solve this task. However, when augmented with memory, the performance of elementary cellular automaton 184 approaches that of the best-known radius three cellular automata found in the literature. It is found that rule 184 transforms spatial information about the neighborhood into temporal information that memory is able to retain and present to the rule's transition function. This causes the cell to transition to a different state compared to the case when no memory is present, which extends blocks of cells having a common state to facilitate a solution of the task.
