To those uninitiated, Cell Machine is a game developed by Sam Hogan for the Game Maker's Toolkit's 2020 game jam. Its premise was inspired by Conway's Game of Life, with it being a "zero-player game" and cells acting on their own terms, like one cell moving forwards and another rotating those around it. It's had many offshoots since then—the GIFs in this post are from a descendant called CelLua Machine—but the idea remains the same.
Recently, someone posted a video making a new "cellular automaton" inspired by Hogan's Cell Machine, but was noted by the audience that it isn't a cellular automaton, which struck me as very odd. The reasoning goes that cellular automata are supposed to be local, where cells aren't able to have an effect that travels an arbitrary distance instantaneously, and Cell Machine is notorious for having information passed at speeds faster than one cell per tick. The GIF below is an example of this, where the Mover (the blue cell) begins pushing the row of Pushables (the yellow cells), and instantaneously destroys the Enemy (the red cell) at the end of it in a single tick as a result of the push, violating locality.
In terms of ticks, this appears to be a non-local effect. However, it's better to look into what happens at smaller subdivisions. When the Mover exerts a pushing force, the force propagates forward one cell at a time, with the new force checking the cell it's on for pushability. This takes multiple steps to calculate, and it can't be done any faster as every cell must be checked. Once there are no more cells to push or any cell fails to push, the propagation is complete. This is all local, and there's a maximum speed at which propagation can be done: one cell per "microtick". I coined this kind of automaton to be a "force automaton".
Now, I would've stopped there and concluded that Cell Machine is a cellular automaton. But, with the two polls that I ran, the majority had voted that they were similar but not equal. Giving it a little more thought (and chatting with someone else), I realized that what I'm really trying to get at is that cellular automata and force automata are under the same family of "automata", but aren't equivalent, and it's best compared through what "rules" are and how cells operate.
In a cellular automaton, cells are independent of those around it and cannot directly influence the state of other cells, instead in charge of observing its neighbors and determining its own state. The "rules" govern how each cell chooses to update based on its neighborhood, and this makes the locality the neighborhood respective of each cell. For a force automaton, cells aren't independent of other cells and can directly influence what happens to the things around it in terms of forces, where the "rules" are how those forces act upon cells and propagate (if they do at all). Locality is gained by the forces in respect to the cells that invoked them (and unlike CAs, FAs require a set order).
I think I'm heading in the correct direction with this, but I don't actually study automata theory and all of this is just my own assumptions based on what I know about the two (honestly, I know more about FAs than CAs; I write a wiki about one!) I'm posting here to get input from those who have more insight into this kind of work. Honestly, I'd love to formalize "force automata".
