Negative results on density determination with one-dimensional cellular automata with block-sequential asynchronous updates.

A large number of research efforts have been made in trying to solve global decision problems with cellular automata by means of their cells reaching a distributed consensus via their local action. Among them, the determination of the most frequent state in configurations with arbitrary size, i.e., the density classification task, has been the most widely approached benchmark problem. The literature abounds with cases demonstrating that, depending on how it is formulated, a solution can be shown to exist or not. Here we address the problem in terms of deterministic, block-sequential asynchronous updates, over cyclic configurations, by which the possibility of a solution remains open. Our main results are negative in terms of the possibility of solving the problem with such formulation, encompassing the cases of any cellular automaton with any sequential update, and any elementary cellular automaton with any block-sequential update; furthermore, we uncover some properties that any potential solution with block-sequential update should have in order for it to be a candidate to solving the problem. Incidentally, we also give a new, very simple proof of the impossibility of solving the problem with any synchronous rule. • The solvability of the DCT by CAs under block-sequential updates is addressed • The DCT cannot be solved by any binary CA under a fully sequential update. • No elementary CA is capable of solving the DCT for any block-sequential update. • Conditions for a CA to solve the DCT under some block-sequential update are supplied. [ABSTRACT FROM AUTHOR]