I'm working on cellular automation simulation. Rule are the following:
It's not necessary for a certain programming language so we only have basic datatypes i.e. bool, int, their's n-dimensional array, etc. in this algorithm.
I have an initial value of any cell that I can load into the memory whenever I wanted. Is there any algorithm to calculate its stabilized value without looping the whole infinite grid?
To be specific, what I'm working on is a rule B5678/S45678 2 dimensional life-like cellular automation.
Is there any algorithm to calculate [a particular cell's] stabilized value without looping the whole infinite grid?
For this particular CA rule, yes, sort of. In particular, you can almost surely determine the final stable state of any given cell on the lattice by inspecting only a finite number of surrounding cells. However, the number of cells you may need to inspect can be arbitrarily large.
First, let me note that the life-like cellular automaton rule code "B5678/S45678" denotes a "majority vote" rule where the state of each cell on the next time step is the current majority state among the nine cells comprised of itself and its eight neighbors.
This rule happens to satisfy a monotonicity property: flipping the initial state of one or more cells from "off" to "on" cannot cause the future state of any cell to flip from "on" to "off", or vice versa. In other words, the future state of the lattice is a monotone increasing function of the current state.
This monotonicity has some important consequences. In particular, it implies that if you have a cluster of cells in the "on" state that is surrounded on all sides by cells in the "off" state (or vice versa), and if this cluster is currently stable (in the sense that applying the CA update rule once will not lead to any cells in the cluster changing state), then it will in fact be forever stable regardless of what else happens elsewhere on the lattice.
This is because the only way that events elsewhere could possibly affect the cluster is by changing the state of one or more cells surrounding it. And since all those surrounding cells are in the "off" state while the cells in the cluster are in the "on" state, monotonicity ensures that changing the state of any surrounding cells to "on" cannot cause the future state of any cell in the cluster to change to "off". (Of course the same argument also applies mutatis mutandis to clusters of "off" cells surrounded by "on" cells.)
(In fact, you don't really need the cluster of "on" cells to be actually surrounded by "off" cells, or vice versa — all that's required for stability is that the cluster would be stable even if all cells surrounding it were in the opposite state.)
Thus, in general, to determine the final state of a cell it suffices to simulate the time evolution of its surrounding cells until it becomes part of such a stable cluster.
One way to do this in (almost surely) finite time is to treat the sequence of 2D lattices at successive time steps as forming a 3D lattice of stacked 2D slices, and to calculate successive "pyramid-shaped" sections of this 3D lattice consisting of the states of the central cell up to time step n, its neighbors up to time step n − 1, their neighbors up to time step n − 2, and so on. At regular intervals, examine each layer of this growing pyramid to see if any of them includes a stable cluster (in the sense described above) containing the central cells.
Assuming that the central cell in fact eventually becomes part of such a stable finite cluster (which almost all cells on a randomly initialized lattice eventually do under this rule; proof left as exercise!), this method will eventually find that cluster. However, depending on the initial states of the surrounding cells, such stabilization could take an arbitrarily long time and the final state of the cell might depend on the states of other cells arbitrarily far away.
For example, let's assume that the cell we're interested in happens to be located in a region of the lattice where the initial cell states, just by chance, are arranged like the squares on a checkerboard: the four orthogonal neighbors of each cell are in the opposite state, while the four diagonal neighbors are all in the same state as the central cell. Clearly such a checkerboard arrangement is locally stable, since each cell is (barely!) in the majority among its neighbors, but any deviations in either direction from this precarious balance around the edges of the checkerboard will propagate as a chain reaction throughout it. Thus the final stable state of any particular cell on the checkerboard will depend on the state of cells surrounding the checkerboard region, which could be arbitrarily far away.