Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic automata at each node. There is no such published paper on MathSciNet, and I have no record of this theorem other than my own faulty memory.
I'd like to ask whether there exists a preprint somewhere, or some other reference.
Although I cannot quite reproduce the theorem's exact statement, here's what I roughly remember. Caveat: please take this all with a grain or three of salt, because I am sure my memory has gaps and/or errors.
The parallel processors of this class are built on an underlying framework consisting of a connected graph with finite valence at each vertex. At each node of this graph one places a finite deterministic automaton. This automaton has some special capabilities. After each computation, it can send one of finitely many outputs along each adjacent edge. Also, before each computation it can receive inputs along each adjacent edge (which have previously been sent by adjacent automata, or have been set up as part of an initialization) and it uses those inputs together with the current state to compute its next state and its next outputs.
I believe there are strong regularity constraints. The graph should have an automorphism group which is transitive on vertices. In fact the entire setup, including the automata themselves and how their inputs and outputs are associated to the adjacent edges, should have an automorphism group that is transitive on vertices. The reason for these constraints is so that the entire network can be "finitely described" or "finitely programmed", and perhaps that is the true constraint, however it may be formalized.
One programs or initializes the processor by choosing initial states and initial inputs. I believe there must be some finiteness condition, for example outside of some bounded region the initial states and initial inputs are perhaps in some default position. Then one lets the processor run until some point (I don't remember the halting conditions), at which time one reads off the terminal states and outputs.
I remember Thurston proved two theorems about universal machines in this class (subject to some restrictions about how to encode or program one machine within another, which I totally do not remember; but this argues for some strong regularity constraints in the class of machines).
One theorem is that a processor of this type whose underlying graph is the Cayley graph of a free group cannot be universal. Roughly speaking the reason one might expect this to be a universal processor is because of exponential growth of nodes, but the trouble is that there is too much bottlenecking at each node.
The main theorem is that there exists a processor of this type whose underlying graph is any Cayley graph of a lattice in the 3-dimensional solvable Lie group. For example, one such lattice is the Cayley graph of the semidirect product $$\mathbb{Z}^2 \rtimes_M \mathbb{Z} $$ using the action of $\mathbb{Z}$ on $\mathbb{Z}^2$ generated by the matrix $M = \pmatrix{2 & 1 \\ 1 & 1}$. Here the rough idea is that one still has exponential growth of nodes, but the bottlenecking phemonenon has been avoided.
Added: I'm convinced now that so far this is just a description of computable functions in the ordinary sense. But this jogs a really dim memory that what's missing is a way to constrain or measure how the programming process is allowed to compress information. I'm still hoping that someone will have a more accurate record of this theorem.
