Cellular Automata/Boundary Conditions

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

On bounded lattices the information about preimages outside the boundaries of the observed string can be described by two boundary preimage vectors (left and right ). The observed string can be seen as part of an infinite string . Boundary vector describes preimages of the semi-infinite string and boundary vector describes preimages of the semi-infinite string . Vector elements are the numbers of preimages that can be traced from the boundary to infinity for each of the overlaps at the boundaries. Element at position in the left boundary vector specifies the number of preimages that can be traced from left infinity to the overlap at the left boundary of the observed string. The definition of the right boundary vector is similar.

Since we usually don't care about the state of the CA outside the observed string, unrestricted boundary vectors can be used. \paragraph{Definition} For the \emph{unrestricted boundary vector} it is assumed that each of the boundary overlaps can be used to trace exactly one path to infinity. Therefore the unrestricted boundary vector contains all ones.

Note The below definitions rely on assumptions that are not proved yet, so the definitions my be wrong.

General boundary vectors and describe general infinite strings and . It is assumed that this strings end with an unrestricted boundary vector in the infinity.

Since an infinite string can have an infinite number of preimages, this definition is rarely useful. Boolean values can be used instead of integers to state if the overlap can be used for tracing or not. The equations are identical, only the scalar multiplication operator used for matrix multiplication is replaced by an XOR logical operation. Another option is using probabilities.

Another common boundary is an infinite periodic string with a finite period. Some commonly used boundaries can be defined this way. The periodic boundary vectors and describe infinite periodic strings with finite periods and . This strings end with the same boundary vector and in the infinity. The preimage matrix of a sting of period strings is computed as .

The problem with this definition is thet there may by many different vectors that fulfil the criteria. There is an example of periodic boundaries with a finite number of preimages at the end of the paper.