1) Let's consider a set of all binary cellular automata on a finite (and finite dimensional) rectangular* grid.
- The state of a cell in the next generation is determined by the state of the cell itself and/or a finite number of other (specified) cells during a finite number of previous steps by a finite logical expression (i.e., informally, there is a 'finite' deterministic rule).
- The appropriate boundary conditions are introduced, or more generally, the rules for each cell can only reference the existing cells.
- The rules for every cell stay the same for each generation (so the CA is deterministic, otherwise we would have to introduce an additional rule for the changing of rules).
We consider the binary values (states) of all the cells and an integer number $N$ of generations as input (a finte string of integers).
We consider the sum of values of the cells in the generation $N$ as the output.
Would this set of cellular automata be equivalent to the set of all computable functions $f(X)$?
Here $X$ is the input string of integers.
Can we narrow the definition above and still obtain the set of all computable functions? How?
Now for the more complicated case of cellular automata on an infinite grid (beloved by Stephen Wolfram).
- There is an infinite (rectangular, finite dimensional) grid with almost all the cells initially in the $0$ state.
- The input is given by the binary values of a finite number of cells in a finite region of the grid and the number of the generation $N$. The output is the sum of values of all cells in the infinite grid in the generation $N$.
- The state of a cell in the next generation is determined by the state of the cell itself and/or a finite number of other cells in a finite neighborhood (meaning they are separated by a finite taxicab distance) during a finite number of previous steps.
- If all the 'reference cells' of a given cell have the state $0$ in all the 'reference generations', then the cell's state is unchanged. (In this way we deal with the infinite size of the grid, so we really only have to 'track' a finite number of cells in any generation with finite $N$).
Would this set of cellular automata be equivalent to all computable functions?
* it could also be another regular grid, like hexagonal on the plane but let's take rectangular, since it generalizes for any dimension in Euclidean space, and the choice of grid doesn't affect the argument here anyway.