Quentin F. Stout

EECS Department, University of Michigan

**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^{2}) 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-2022 Quentin F. Stout |