Fig. 1. A graph superimposed
on a checkerboard grid.
Random Explorations in Automata Theory
Gary J. Shannon
Mar. 2, 2003
Matrix Automata: Exploring Alternate Spaces
The usual cellular automaton is pictured as a space-filling grid of some sort where a cell's neighbors are taken to be adjacent cells that can be reached by crossing a common edge or by crossing a common vertex. Such space-filling grids have an obvious dimensionality based on the dimensionality of the space in which they are drawn. Square cells fill a plane space and cubical cells fill a 3-dimensional space. But there is another way to conceptualize a cellular automaton which makes the question of dimensionality less straightforward. The space in which the cellular automaton is implemented can be represented as a graph of vertices connected by edges. In this case it is the vertices that contain the state information and the edges which define the neighborhood. Any ordinary space-filling grid of cells can be converted into an equivalent graph, but not every graph can be converted into a uniform space-filling grid of cells. Figure 1 shows the graph equivalent of the square 2-dimensional grid using the Moore neighborhood, which is the neighborhood where both diagonal and orthagonal neighbors are counted. [See cellular neighborhoods.]
Fig. 1. A graph superimposed
on a checkerboard grid.
Clearly each node of the graph (called a vertex in graph theory) is connected to eight neighboring nodes in the same way that each cell of the checkerboard is connected to its eight neighbors. Thus the graph defines the same topological connectivity as the checkerboard. But what about the dimensionality of the graph?
The dimensionality of a Euclidean space can be determined by counting the number of points that can be placed such that each point is equidistant from all other points. In a 1-dimensional Euclidean space two points can be placed at a distance of 1 from each other (figure 2A). In a 2-dimensional space we can place 3 such points (figure 2B), and 4 such points can be placed in a three dimensional space (figure 2C). In general, if we can only place N points that satisfy the equal distance condition then the space in which we are placing them has N-1 dimensions.
Fig 2. Dimensionality in Euclidean space.
In graph theory the distinction is made between a planar and non-planar graphs, where a planar graph is one that can be drawn on a plane surface without any edges that cross. All other graphs are simply considered to be non-planar. However, we can extend the notion of dimensionality to graphs and determine the dimensionality of a graph by counting the number of points that can be placed so that they are all a distance of 1 from each other. Figure 3 shows a complete graph with 5 vertices.
Fig 3.
In graph theory distances are measured by counting the number of edges between two vertices. Every vertex in figure 3 is, therefore, a distance of 1 from every other vertex. Since this graph has 5 vertices each a distance of one from every other vertex, this graph can be thought of as being a 4-dimensional graph because in order to draw this graph in a Euclidean space while maintaining the equality of all distances would require a space of 4 dimensions.
The Shapes of Space
Since we are going to be building some structures that have properties somewhat different from those seen in graph theory or space-filling grids, rather than building a grid of cells or a graph of vertices and edges, we will be building a matrix of nodes and links. The difference in terminology might seem superfluous but it would be confusing to continue calling something a cell when it has been extrapolated in such a way that it no longer resembles the cell of a grid except in the most abstract topological way. The new terminology is to avoid such confusion.
If we now convert common CA grids to their equivalent graphs we immediately run into some problems. The simple square grid using the Moore neighborhood results in the graph of figure 1, which is not planar because it has edges that cross one another. This checkerboard CA grid is usually refered to as 2-dimensional, but according to graph theory it is not a 2-dimensional graph and so cannot be a 2-dimensional matrix.
However, the matrix is not quite 3-dimensional either since it only needs to borrow a thin slice out of the third dimension in order to satisfy the requirement that all links are of equal length. (The reason this equal distance requirement must be satisfied will be discussed a bit later.) The resulting not-quite-3D matrix is shown in figure 4. The matrix has unlimited, or arbitrary size in two dimensions but has a thickness of only 1. (The thickness of a matrix is measured in the graph theory manner of counting connecting links so that a true 2-dimensional matrix has a thickness of zero in all higher dimensions.)
Fig 4. A sheet matrix.
A matrix that can have any arbitrary size in two dimensions but has a fixed, finite size in the third (or higher) dimension will be refered to as a sheet, to distinguish it from true 2-D and true 3-D matrices. In general any matrix which is of restricted size in all but two of its dimensions will be refered to as a sheet, thus a 4-dimensional sheet would have two unrestricted dimensions and two thin, or restricted ones.
Now consider the matrix shown in figure 5. This might also be classified as a 2-dimensional matrix, but it has fixed limited extent in one dimension and unlimited or arbitrary extent in the second dimension. Being more than 1-dimensional but less than 2-dimensional, we can call such a matrix a ribbon.
Fig 5. A ribbon matrix.
In figure 6 we have expanded the neighborhood of each cell to include the diagonals. As we saw in figure 4 this is no longer a planar graph, but a 3-dimensional one. Unlike a sheet, which is limited to a fixed, finite thickness in one of its dimensions, this matrix is limited in two of its dimensions and gives the appearance of a fat ribbon or string. (See figure 7.) In general, we will call any matrix which is restricted to a fixed, finite size in all but one of its dimensions a string.
Fig 6. A 2-dimensional projection
of a 3-dimensional string.
There could, in addition to 3-dimensional strings, be 4, 5, or N-dimensional strings if that many dimensions are necessary to satisfy the equal length of links requirement. So long as only one dimension remains unconstrained then it is a string. It should be noted that ribbons may also be refered to as 2-dimensional strings.
Fig. 7. The same string as it appears in
3-dimensional Euclidean space.
What Dimensionality Really Means
It might seem rather pointless to fret over the dimensionality of a matrix if that matrix can be drawn schematically on a flat sheet of paper or built out of real-world commponents in a 3-dimensional space. How does it matter that a particular matrix is 6-dimensional if we can still build a working version of it 3-dimensional space? In fact there is no need to resort to higher dimensions or to insist that all links are of equal length because none of this will affect the dimensionality of the matrix. It is perfectly alright for us to compromise on the link lengths in order to build a 6-dimensional matrix out of 3-dimensional components. However, if there were an intelligent being living inside that matirx such a creature would preceive his world to be a 6-dimensional one. Regardless of the apparent dimensionality of the components or of the model that we build of the matrix, internally, from the inside, the matrix will be experienced as having dimensionality as we have defined it here. The hypothetical digital creature living in the matrix could not refer to outside standards of measurement and dimensionality because such a creature would not only be in the matrix, but would be of the matrix and would perceive only those things that were themselves of the matrix.
Fig. 8.
The matrix of figure 8 may appear distorted when viewed from our perspective as outsiders, but to an inhabitant of the matrix every link has the same uniform length, namely 1, and his space appears uniform in every direction that exists to him. This is because the only unit of measure available to someone inside the matrix is the distance across a link to a neighbor and the only way to measure that distance is to meausre the time it takes for a node to react to a change in a neighboring node. However, since time is measured by an integer count of clock ticks the smallest quantum of time is 1 tick and the only length that can meaningfully be assigned to a link from the inside is 1. Therefore all links appear from the inside to be of equal length. Thus to the creature living inside an N-dimensional matrix it will appear uniform and have all the properties of a space of N-dimensions.
For this reason it is not necessary to draw a matrix with all edges equal in length as long as it is understood that internally to the matrix, and to any digital creatures inhabiting that matrix, all edges will be seen as being equal in length, and space will have the dimensionality of the matrix.
A Few Additional Geometries
Some other interesting matrix geometries include loops in their structure. The simplest looped matrix is the ring. A ring is formed by connecting one end of a 1-dimensional matrix to the other end. (See figure 9.)
Fig. 9. A Ring.
The band is made by looping a ribbon matrix. Bands can either be untwisted or twisted, as in a Moebius strip.
Fig 10. A Band.
In like manner a sheet can be looped to form a tube, and a string or tube can be looped to form a filled or hollow torus. Like a band a torus my be twisted or untwisted. A torus formed of a tube or string with a circumference of N can be twisted in N different ways specified as 0, 1/N, 2/N, ... 1.
At first it might appear that a tube is the same thing as a string, but this is not the case. A string has a solid core filled with nodes and/or links whereas a tube is a two dimensional thin sheet wrapped around to form a completely hollow space in the center. In figure 11 the matrix A has no internal diagonals and retains the local connectivity of a plane. Thus it is a tube. Matrix B is identical except for the addition of internal diagonals. These diagonals prevent the string from being sliced down its length and laid flat as a planar graph. The connectivity is no longer that of a bent plane, but is truly 3-dimensional in nature and is, therefore, a string.
fig 11. Tube and String Compared.
Solid figures such as polyhedra and geodesic globes can also serve as the basis for a matrix. All of the Platonic solids have vertices of only one degree and these polyhedra can form the basis of regular matrices. Geodesic spheres generally have vertices of both degree 5 and degree 6 but by placing a node in the center of each triangular face and a link crossing each edge a regular spherical matrix of degree 3 can be constructed.