This question is inspired by a comment Jukka Suomela made on another question.
What are examples of infinitely large but locally finite computation problems (and algorithms)?
In other words, what are examples of computations that halt in finite time, in which each Turing Machine reads and processes only finite data, but altogether the computation solves an infinite-size problem if there are infinitely-many Turing machines networked together?
Just to give some ideas of what is possible (but somewhat non-trivial), here is one example: a distributed algorithm that finds a maximal edge packing on a bounded-degree graph.
Given a simple undirected graph $G = (V,E)$, an edge packing (or fractional matching) associates a weight $w(e)$ with each edge $e \in E$ such that for each node $v \in V$, the total weight of edges incident to $v$ is at most $1$. A node is saturated if the total weight of incident edges is equal to $1$. An edge packing is maximal if all edges have at least one saturated endpoint (i.e., none of the weights can be greedily extended).
Observe that a maximal matching $M \subseteq E$ defines a maximal edge packing (set $w(e) = 1$ iff $e \in M$); hence it is easy to solve in a classical centralised setting (assuming $G$ is finite).
Edge packings actually have some applications, at least if one defines an application in the usual TCS sense: the set of saturated nodes forms a $2$-approximation of a minimum vertex cover (of course this makes only sense in the case of a finite $G$).
We will assume that there is a global constant $\Delta$ such that the degree of any $v \in V$ is at most $\Delta$.
To keep this as close to the spirit of the original question, let us define the model of computation as follows. We assume that each node $v \in V$ is a Turing machine, and an edge $\{u,v\} \in E$ is a communication channel between $u$ and $v$. The input tape of $v$ encodes the degree $\deg(v)$ of $v$. For each $v \in V$, the edges incident to $v$ are labelled (in an arbitrary order) with integers $1,2,\dotsc,\deg(v)$; these are called local edge labels (the label of $\{u,v\} \in E$ can be different for $u$ and $v$). The machine has instructions with which it can send and receive messages through each of these edges; a machine can address its neighbours by using the local edge labels.
We require that the machines compute a valid edge packing $w$ for $G$. More precisely, each $v \in V$ has to print on its output tape an encoding of $w(e)$ for each edge $e$ incident to $v$, ordered by the local edge labels, and then halt.
We say that a distributed algorithm $A$ finds a maximal edge packing in time $T$, if the following holds for any graph $G$ of maximum degree $\Delta$, and for any local edge labelling of $G$: if we replace each node of $G$ with an identical copy of the Turing machine $A$ and start the machines, then after $T$ steps all machines have printed a valid (globally consistent) solution and halted.
Now all of the above makes perfect sense even if the set of nodes $V$ is countably infinite.
The problem formulation and the model of computation do not have any references to $|V|$, directly or indirectly. The length of the input for each Turing machine is bounded by a constant.
The problem can be solved in finite time even if $G$ is infinite.
The problem is non-trivial in the sense that some communication is necessary. Moreover, the running time depends on $\Delta$. However, for any fixed $\Delta$, the problem can be solved in constant time regardless of the size of $G$; in particular, the problem is solvable on infinitely large graphs.
I have not checked what is the best known running time in the model defined above (which is not the usual model used in the field). Nevertheless, a running time that is polynomial in $\Delta$ should be fairly easy to achieve, and I think a running time that is sublinear in $\Delta$ is impossible.
Finding the next generation of a Cellular Automaton.
This can be solved as you described in constant time. $\;$ (i.e., independent of the input)
Essentially, every problem that is at least as hard as coloring requires an algorithm with a running time dependent on the number of nodes in the network and thus cannot work in an infinite but locally finite graph. This follows from Linial's seminal log*n lower bound.
This doesn't quite fit your definition, but I think only because of non-uniformity. Before showing parity was not in $AC^0$, Sipser (I believe it was) showed that any infinite parity function (a function on countably many variables that changes output whenever any single input is changed) could not be solved in "infinitary $AC^0$."
