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