Abstract: von Neumann introduced a model of parallel computing consisting of copies of a finite state automaton connected together in a regular fashion. In such computers a self-organizing structure called clerks can be useful, enabling one to simulate a more powerful computer for which optimal algorithms are easier to design. The computation proceeds by having the cellular automata organize themselves into clerks, and then a stepwise simulation of the more powerful computer is performed. For a system of n automata, each clerk contains Θ(log n) automata, so first they need to determine log(n), despite the fact that no single automata can count higher than a fixed number.

One could think of each automata initially being in an undifferentiated stem cell state. Only the ones on the edges have special input (namely, one or two of their neighbors is missing), unlike the others. The corners start a process whereby a sequence of stages results in some automata becoming the leftmost in a clerk, some become the leftmost of a sequence representing memory location 1 within the clerk, others become part of the interior of memory location 1, another becomes the rightmost of memory cell 1, etc. Note the similarities to biological processes and cell differentiation.

Clerks are used here to give optimal parallel algorithms for a connected 1s problem on a cellular array, and a circle construction problem on a pyramid cellular automaton.

In the connected 1s problem, the input is a white/black grid stored one point per processor, with two specially marked points, and the goal is to decide if the two marked points are in the same connected component (equivalently, viewing the input as a maze with black indicating walls, the problem is to decide if one can go from one marked point to the other within the maze). The 2-dimensional problem had been solved in the 1960s by W.T. Beyer, who showed that an n x n cellular automata could solve it in Θ(n) time. His elegant solution was later independently discovered by Levialdi. Beyer was a student of Seymour Papert, and Marvin Minsky was on his PhD committee, and they included his 2-dimensional result in their 1969 book Perceptrons: An Introduction to Computational Geometry. They also noted ``We do not know any equivalent process for three dimensions. (Consider knots!)''.

This paper resolves this question, showing that for any dimension d, a d-dimensional n x n ... x n cellular automata can solve the d-dimensional connected ones problem in Θ(n) time. In 1979 S.R. Kosarju called this a ``classic'' open problem. However, the approach used is radically different (and far more complicated) than Beyer's.

Decades later, some closely related problems are still open. For dimension 2, it is known that a mesh computer can mark a shortest path connecting the marked points (if they can be connected) in Θ(n) time (see, for example, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, Theorem 3.15). In a mesh computer each processor can perform constant-time calculations on words of logarithmic length, as opposed to the constant-length words in a celluar automata, but can store only a constant number of words. Can cellular automata mark a shortest path in this time? Can it even mark a simple path in this time? It is easy for the cellular automata to find a shortest path in Θ(n²) time by a breadth-first ``spreading wave'' approach. For dimensions ≥ 3 it isn't known if a mesh computer can solve this in Θ(n) time even if each processor is allowed polynomially much storage (i.e., all that it could address, given its word size).

Complete paper. This paper appears in Proceedings 23rd IEEE Symposium on Foundations of Computer Science (1982), pp. 272-279.

Related work:

• A paper utilizing clerks for a cellular automaton arranged as a mesh-connected computer, and one for a pyramid computer.
• My papers in parallel computing, and an overview of my research
• An explanation of parallel computing, Parallel Computing 101, a tutorial and a list of parallel computing resources.

Copyright © 2005-2024 Quentin F. Stout