We consider the problem of establishing gravity in cellular automata. In particular, when cellular automata states can be partitioned into empty, particle, and wall types, with the latter enclosing rectangular areas, we desire rules that will make the particles fall down and pile up on the bottom of each such area. We desire the rules to be both simple and time-efficient. We propose a block rule, and prove that it piles up particles on a grid of height $h$ in time at most $3*h$.
|Models of Computation (acm F.1.1)|
|Theory of computing (msc 68Qxx), Analysis of algorithms and problem complexity (msc 68Q25), Cellular automata (msc 68Q80)|
|Information Systems [INS]|
|Organisation||Quantum Computing and Advanced System Research|
Gruau, F.C, & Tromp, J.T. (1999). Cellular gravity. Information Systems [INS]. CWI.