Cellular Automata/Decision Problems

The study of decision problems for 1D CA is based on the subset diagram of the de Bruijn diagram. The subset diagram is interpreted as an finite automaton and analysed accordingly. Most decision problems are defined using the larger matrix subset diagram, but they can be redefined using the smaller vector subset diagram.

The subset diagram

edit

Nodes in the subset diagram are all possible preimage matrices or vectors that can be written using boolean elements.

Matrix subset diagram

edit

The matrix subset diagram is a directed graph   later remodeled as a finite automaton.

  is the set of all states which are all   distinct bolean preimage matrices.

 

The set of available cell states   is used for link labes and as the automaton alphabet. The automaton state transition function   defines links between states and their labes.

 

Two transition functions can be constructed, one for the forward direction   and one for the backward direction  . The transitions on input symbols   are defined by single cell preimage matrices.

 
 

A finite automaton   is constructed from the graph   by specifying an initial state   and the set of final states  .

The empty set is the state   where all preimage matrix elements are 0.

 

Vector subset diagram

edit

The vector subset diagram is a directed graph   later remodeled as an finite automaton.   is the set of all states which are all   distinct bolean preimage vectors.

 
 

The set of available cell states   is used for link labes and as the automaton alphabet. The automaton state transition function   defines links between states and their labes.

 

Two transition functions can be constructed, one for the forward direction   and one for the backward direction  . The transitions on input symbols   are defined by single cell preimage matrices.

 
 

A finite automaton   is constructed from the graph   by specifying an initial state   and the set of final states  .

The empty set is the state   where none of the overlaps in the preimage vector   can be used to trace paths.

 

The full set is the state   where all of the overlaps in the preimage vector   can be used to trace paths.

 

Transformations from the matrix subset automaton into the vector subset automaton

edit

Decision Problems

edit

To observe a decision problem the subset diagram is transformed into an automaton. A word defined as a string of cells   is accepted if it connects the specified initial state to one of the final states.

De Bruijn subset diagram, are used to answer injectivity and surjectivity problems, regular expression for preimages...

Surjectivity of CA rules

edit

The global transition function is surjective if each present configuration   has at least one preimage  .

 

Since preimages are paths in the preimage network, there must always exist at least a single path between the boundaries of any cell string  .

Shortest non-accepted string

edit

Another problem related to the subset diagram is the shortest string that is not accepted by the subset diagram. This can easily be rephrased as a decision problem: does the subset diagram have a string of length   or shorter for a given integer  . By the definition of this problem, testing true for a given cellular automaton rule and given  , the same cellular automaton will test true for l+1. In the case that a cellular automaton is surjective, there will be no such string.

It was alluded to by Wolfram that what Sutner called the 1-permutative cellular automata most likely will test false for the highest   within the set of cellular automata with the same number of characters and the same width. Kingsbery proved in his undergraduate thesis that 1-permutative CA will test true for all   greater than or equal to  , where   is the CA's width and   is the number of symbols. Assuming that this is true for all CA (and the work of Wolfram and Sutner seem to indicate that it should be), this ensures that any certificate for this decision problem can be verified in time polynomial to the size of the CA's rule table. It is not known whether such a certificate can be constructed in polynomial time.

Theorem: 1-permutative CA with a width   over   symbols have a shortest non-accepted string no longer than  .

Proof: TODO

Definitions and Proofs

edit

Boolean matrix and vector operations

edit

All mathematical addition and multiplications are exchanged with their Boolean counterparts disjunction and conjunction.

Addition become disjunction (logical operator OR):

 

Multiplication becomes conjunction (logical operator AND):

 

This basic Boolean operations are than used to define matrix and vector operations.

Examples

edit

Regular language of Garden of Eden configurations for 1D CA

edit

References

edit
  1. Tobias Gärtner, Timo von Oertzen, and Jan Schwinghammer, Efficiently Computing the Density of Regular Languages, Proceedings of Latin American INformatics (LATIN'04), pages 262-270, Buenos Aires.
  2. Etienne Grandjean, Complexity of the first-order theory of almost all finite structures, Information and Control, 57(2/3):180-204, May/June 1983

Tools

edit
  1. Grail+