Cellular Automata/Decision Problems

From Wikibooks, open books for an open world
Jump to: navigation, search

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 \langle S, Q_D, \delta_D \rangle later remodeled as a finite automaton.

Q_D is the set of all states which are all |Q_D|=2^{k^{2(m-1)}} distinct bolean preimage matrices.

 Q_D = \left \{
\begin{bmatrix}
0 & 0 & \dots 0 \\
0 & 0 & \dots 0 \\
\vdots & \vdots & \ddots \vdots
\end{bmatrix},
\begin{bmatrix}
1 & 0 & \dots 0 \\
0 & 0 & \dots 0 \\
\vdots & \vdots & \ddots \vdots
\end{bmatrix},
\dots,
\begin{bmatrix}
1 & 1 & \dots 1 \\
1 & 1 & \dots 1 \\
\vdots & \vdots & \ddots \vdots
\end{bmatrix}
\right \}

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

 \delta_D : Q_D \times S \rightarrow Q_D

Two transition functions can be constructed, one for the forward direction \delta_{D,f} and one for the backward direction \delta_{D,b}. The transitions on input symbols c\in S are defined by single cell preimage matrices.

 q_{D_{x+1}} = \delta_{D,f}(q_{D_x}, c_x)  \qquad  D_{x+1} = D_x \cdot D(c_x) \quad \mbox{boolean multiplication}
 q_{D_{x-1}} = \delta_{D,b}(q_{D_x}, c_x)  \qquad  D_{x-1}^T = D(c_{x-1}) \cdot D_x^T \quad \mbox{boolean multiplication}

A finite automaton \langle S, Q_D, q_0, \delta_D, F_D \rangle is constructed from the graph \langle S, Q_D, \delta_D \rangle by specifying an initial state q_0 \in Q_D and the set of final states F_D \subset Q_D.

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

\begin{bmatrix}
0 & 0 & \dots 0 \\
0 & 0 & \dots 0 \\
\vdots & \vdots & \ddots \vdots
\end{bmatrix}

Vector subset diagram[edit]

The vector subset diagram is a directed graph \langle S, Q, \delta \rangle later remodeled as an finite automaton. Q is the set of all states which are all |Q|=2^{k^{m-1}} distinct bolean preimage vectors.

 Q_b = \{ 0, 1, \dots, b, \dots ,|Q|-1 \}
 q = \sum_{o=0}^{k^{m-1}-1} b(o) = 2^{k^{m-1}-1} b(k^{m-1}-1) + \cdots + 2^o b(o) + \cdots + 2 b(1) + b(0)

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

 \delta : Q \times S \rightarrow Q

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

 q_{x+1} = \delta_f( q_x, c_x)  \qquad  b_{x+1} = b_x \cdot D(c_x) \quad \mbox{boolean multiplication}
 q_{x-1} = \delta_b( q_x, c_x)  \qquad  b_{x-1}^T = D(c_{x-1}) \cdot b_x^T \quad \mbox{boolean multiplication}

A finite automaton \langle S, Q, q_0, \delta, Q_F \rangle is constructed from the graph \langle S, Q, \delta \rangle by specifying an initial state q_0 \in Q and the set of final states Q_F \subset Q.

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

 b = [ 0, 0, \dots, 0 ]

The full set is the state q=2^{k^{m-1}} where all of the overlaps in the preimage vector b can be used to trace paths.

 b = [ 1, 1, \dots, 1 ]

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 \alpha 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 C^t has at least one preimage C^{t-1}.

 \forall C^t \; \exists C^{t-1} \; : \; F(C^{t-1})=C^t

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

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 l or shorter for a given integer l. By the definition of this problem, testing true for a given cellular automaton rule and given l, 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 l 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 l greater than or equal to wk^{w-1}, where w is the CA's width and k 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 w over k symbols have a shortest non-accepted string no longer than wk^w-1.

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):

 x_1 + x_2 \to x_1 \lor x_2

Multiplication becomes conjunction (logical operator AND):

 x_1 \cdot x_2 \to x_1 \land x_2

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+