The Value Collision Problem in Neural Cellular Automata

Bubble sort is a purely local algorithm, making it a natural candidate for implementation in Neural Cellular Automata (NCAs), which are also governed by local rules. We investigate whether NCAs can replicate sorting through local interactions, systematically testing eight architectural variants. We identify a fundamental computational barrier we term the \emph{value collision problem}: when multiple elements attempt to swap simultaneously, the NCA averages conflicting writes to a shared cell rather than routing them sequentially, destroying information that no subsequent step can recover. While some variants achieve partial success, all value-routing approaches ultimately fail because precision degrades cumulatively across iterations. This result defines a computational boundary: NCAs can perform routing for tasks that require diffusion, but fail at exact value routing when writes collide and no collision-avoidance mechanism is present.