NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/theory/cellaut/513

Internet Message Format | 1992-11-11 | 3.7 KB

Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!agate!apple!decwrl!atha!aupair.cs.athabascau.ca!burt
From: [e-mail] (Burt Voorhees)
Newsgroups: comp.theory.cell-automata
Subject: Re: Undecidability of configurations/progression
Message-ID: <[e-mail]>
Date: 11 Nov 92 18:18:56 GMT
References: <[e-mail]> <9211110145.AA23882@math.
Sender: [e-mail]
Distribution: inet
Lines: 67

>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.

What is the reference for this?

I don't think that this can be true, at least in the way that I read it.
That is, suppose that we have a 1-d CA with global rule F and we know that
a configuration x has a predecesksor y, so that F(y) = x.  Does this claim
that there is some other predecessor z of x with some n such that
F^n(z) = x and that z is eventually periodic?

A counter-example to this is the rule D on the spacce of half-infinite
0,1 sequences defined by [D9x0    [D(x)]i = xi+xi+1  (rule 60 or 102,
I forget which).  Every configuration has a predecessor under this rule,
given by solving D9   D(x) = y to get x = x0+Bs^-1(y) where s^-1 is the
left shift and B is a parity operator: [B(y)]i = sum(j=1-i)yj
(ref: Predecessor states for certain cellular automata evolutions,
Burton Voorhees, Commun. Math. Phys. _117_ 431-439)

The operator B has a period doubling property: if y is periodic with
period n then there is a k such that B^k(y) has period 2n.  Based on
this one can eventually show that D maps periodic sequences to periodic
sequences, eventually periodic sequences to eventually periodic
sequences, and non-periodic sequences to non-periodic sequences.
So it seems to me that if x is a non-periodic sequence then all of
the predecessors of x must also be non-periodic.

>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.

If F is a one dimensional rule with state space all half-infinite 0,1
sequences then F defines a map F* of the interval [0,1].

Conjecture: this map has the intermediate value property if and only if
F has no Garden of Eden.  (only if part is easy)

>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.

A related question is: given a finite set of finite strings, is there a
radius k such that there is a k-rule for which this set generates the
GofE (in the sense that every GofE state contains at least one string from
this set)?

burton voorhees
Faculty of Science
Athabasca University
Box 10,000
Athabasca, AB
CANADA   T0G 2R0
[e-mail]