Binary cellular automata and computable functions

Question

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.

Answer 1

In the finite case: no, it's definitely not equivalent to all computable functions. There's only finitely many possible cells, so only finitely many possible outputs; let $K$ be the largest possible output. The constant function $f(x) = K + 1$ is clearly computable, but can't even be expressed under these constraints.

In the general case: also no. Construct a function $f$ as follows: enumerate all possible cellular automaton rule sets $C_0, C_1, C_2, \ldots$. Given input $x$ in the format specified above (binary values in a finite region of the grid, together with $N$), run the $x$th cellular automaton ($C_x$) for $N$ stages, and let $M$ be the resulting output. Let $f(x) = 0$ if $M \neq 0$, and $f(x) = 1$ if $M = 0$. This is a computable function, because we can run the automaton computably; but it can't be computed by a cellular automaton, because if it were computed by $C_i$ for some $i$, then $f(i)$ would be the output of $C_i$, but we've constructed $f$ so that this is not the case.

In general, this sort of trick can be used on any model of computing that (1) allows "programs" to be computably listed and (2) requires every "program" to eventually halt.