From: hurd@math.gatech.EDU (Lyman Hurd)
Subject: Undecidability of configurations/progression
Organization: The Internet
Distribution: inet
Date: Wed, 11 Nov 1992 01:45:00 GMT

There are two distinct categories of questions about CA, yielding four
kinds of decisions.

1) There is a distinction between finite (quiescent outside a bounded
region, and infinite configurations.

2) There is a distinction between 1 and 2 dimensions.  I am not aware of
any problems which get harder as one passes from 2 to 3 but I would be
interested to hear of any!

To the best of my knowledge here is what is known.

1) FINITE - 1 or 2 DIMENSIONAL

In one dimension there is a procedure to decide whether a configuration has
a predecessor.  If there exists one, it can be shown that there is a
predecessor which is eventually periodic.  Furthermore you can decide if a
finite configuration has a finite predecessor.  This result is (to my
knowledge) due to Golze.  Proofs are not difficult.

In 2 dimensions you cannot even determine if the all-quiescent (as finite
as they come) configuration has a predecessor.  This follows immediately
from Berger's theorem which states that there is no general way to decide
if a given set of Wang tiles (square tiles with a preferred orientation and
four colored edges---tilings must have touching edges have the same colors)
admits a plane tiling.  This type of construction appears many places,
including Golze, Kari, Culik, Yu, and me.

2. Decaying into a cycle.  From a finite configuration (in 1-d) it was
shown by Culik and Yu.  The infinite case and in particular if all infinite
configurations decay into the quiescent state was solved by Kari.

A consequence of this result are what Kari and I call aperiodic CA which
have the property that all spatially periodic configurations evolve to a
quiescent state, although NOT in uniform time, but not all configurations
do so.  Also the only temporally periodic state is quiescent.  Such rules
can be made to have highly non-trivial dynamics completely supported off
the periodic points.

3. Injectivity and surjectivity.  In one dimension there are standard
constructions for showing if a CA is onto its image (i.e., has NO gardens
of Eden).  If it is injective (F(x)=F(y) implies x=y) then it must be
reversible (bijective---this is not obvious), and once again in 1-d a
finite procedure starting with a rule table will answer this question.

In 2D Kari in his thesis showed that both questions are undecidable---i.e.,
in 2D we cannot even tell if ANY GOE's exist!

One interesting corollary is the following.  Given two rules (in 1 or 2
dimensions) one can decide whether they are inverses.  In one dimensions if
you know the number of states per site and the radius of the rule (speed of
light) one can get an effective bound on the radius of the inverse and find
it by exhaustion (I am not suggesting this practically).  This bound has
cryptographic implications.  In 2D Kari shows such a recursive bound cannot
exist.  There must be 2D rules whose description in one dimension are
arbitrarily simpler than their description in the other.

My own prejudice lies in describing sets of configurations of dynamical
interest (closed and shift-invariant).  It turns out that any such set is
determined by knowing all finite configurations lying within in.  In 1-d
this forms a language.

The distinction between 1 and 2D is again vast.  In 1-d one way to specify
a set of configurations is to exclude a finite set of substrings.  The
resultant sequences form what is known as a subshift of finite type and has
a regular language description as all bi-infinite walks through a specific
labeled directed graph.  In 2D the undecidability of the tiling problem
says that given a finite set of excluded blocks, one cannot decide whether
the set described is non-empty.

In short I want to reiterate:

1) The questions depend highly on whether one restricts to finite
configurations.

2) There is a dramatic difference between 1 and 2 dimensions.  Ironically
the proofs of undecidability are usually much easier in two dimensions.

My own advice for the future is the exploration of reversible 1-D CA rules.
Almost all of the results I know of are in the irreversible case.  For
example I do not know the answer to the question:

Given a reversible rule F, is it decidable whether there exists N such that
F^N(x)=x for all (infinite) configurations x.

Newsgroups: comp.theory.cell-automata