Review Article - (2017) Volume 6, Issue 2
The proof of the perfection for the first 91 normal Masks in one dimension and for the seven normal Masks in two dimensions is completed (all the centrally symmetric masks are not differentiated and are counted as one). A method is indicated for proving the Perfection of (presumably) any appropriate Mask (which is Perfect).
Keywords: Cellular automaton; Automaton; Transliteration; Transition tables
This study is a continuation of the studies and includes the complete proof of the Perfection of Masks (Neighborhoods) shown in Figures 1-3. Let us briefly discuss the proof (Figure 1).
Figure 1: The set of the first Perfect Masks in one (left panel) and two (right panel) dimensions. On the top of the left panel, a few examples of 1D Perfect Masks are shown, on its bottom-the colored diagram indicating properties if the first 1D Perfect Masks. Two numbers in the colored squares in the left panel stand for n (n is the number of cells in a particular Mask) and с1/2=(c-1)/2 (c is the number of rows in a Transition Table build for that Mask).
First, one small but important Lemma will be proven: The lemma for all normal Masks. Then the proof of perfection will be carried out separately for each Mask. The perfection proof will be aided by the computer and completed in three stages. The first two stages have been described in detail [1]. We will briefly revise these stages and then talk about the “third” stage. Also, we will talk about the important “problem of the number 3”.
We define an ordinary (traditional) CA as a Cellular Automaton (CA) which is single-plane in time. In general, it operates on the N-dimensional Lattice. The Lattice space can be closed (for instance, it can form a torus) or continue ad infinitum. The state of a cell in this Lattice at the time point t+1 depends on states of the cells in its neighborhood at time point t. A majority of Cellular Automata are ordinary.
To operate ordinary Cellular Automaton, one needs to specify (define) five things (Figure 2).
In this figure, there 5 panels (I-V). Below we specify the content of each panel.
I. N- dimensionality of the Lattice and the dimensions of the boundaries of Cellular Automaton.
II. k- the number of possible cell states.
III. n- the number of cells (cells are numbered from 0 to n) forming the Neighborhood including “central” cell. Example is shown of a particular cell numbering for some 2D Mask.
IV. The transition tables R with the corresponding index. The transition tables determine the state of CA at the next time point (t+1). Both the index of the Table and its content (elements) belong to the set from II. For each cell and at each time point, we write out (in accordance with the numbering III) a string and compare it to the content of the Transition Tables. When we find the matching row in TT we choose this row index as the next state of the Automaton.
V. The Initial Conditions.
After establishing the above definitions, we can start the operation of our CA and monitor its changes.
Also it is important to mention properties of a Transition Table (TT) [1]:
1. The row position in TT does not matter.
2. The number of columns in TT is equal to n+1, where n is the number of points in the “numbered” neighborhood.
3. Each TT has a “rightmost selected” column (which represents the central point). In the figures below, it is highlighted in grey.
4. All the rows, both in one TT and in the other ones, differ among themselves.
5. The maximum number of all rows of TTs must be less or equal to kn+1. (22+1=4+4 is true for the Automaton called “Rule 30”, 28+1=372+140 is true for the Automaton called “Life”). If some row(s) is (are) missing, then one should explain why this row(s) cannot appear during the operation of the CA (Figure 3).
In Figure 3 one can see some examples of ordinary Cas (Figure 3):
Let us consider Figure 3. Panel C describes Fredkin’s Automaton (we call this type of Automaton by the name of its inventor it) [4]. Fredkin’s Automaton has three states: A, B and C. In it, we calculate a certain Boolean function, that depends only on cells C, which fall into neighborhood “f(C)” and then we make the corresponding transformations depending on function f (Figure 3).
Let us define transliteration as a replacement of all C’s by B’s and B’s by C’s. Then it is easy to prove the following statement: (i) we make a transliteration in the Fredkin’s Automaton, then (ii) we make one time step forward and after that (iii) another transliteration, we will be in the previous state [5]. That means that this Automaton is reversible.
Let us consider the situation when the initial state of Fredkin’s CA comprises cells A and/or B. That is, there are no C cells at all. (Let us assume that f(C) is equal to 0 in this case. This is another condition we impose on the Automaton). That is, the Automaton (with no C cells) will be transformed as follows: A=>A and B=>C, that is, to its transliteration. Then we should watch two movements synchronously: The first is directed forward in time, the second is directed backward. At each new step, the “forward and backward” states will be transliterations of each other. If the number of states is finite, there will necessarily be a moment when with the next move forward, we will get its transliteration, that is, the “backward” move. We can say that we have reached the Mirror Point or the Half-Period Point (point of return).Then the motion is repeated (Figure 3).
Let us “facilitate” the Fredkin’s Automaton, that is, we will remove the word “any” from definition of the f (C) function and will consider f (C)=0, if there are NO C cells in the given neighborhood and f (C)=1, if they ARE C cells in the given neighborhood (Figure 4).
This kind of Fredkin’s Automaton will be a subject of following discussions because exactly this kind of Fredkin Automaton demonstrates, rather than any other Fredkin’s Automata, a completely surprising and paradoxical behavior [6]. All other FA (and that can be shown) “deteriorate” over time. Most of the “random” FA is “broken” at the moment the FA is created.
Only SFA can, roughly speaking, run indefinitely. It does not “die in the Hyper cycle” (the cycle where an ordinary FA goes on has an unimaginably large number of steps), but it appears again in the initial state.
In an informal way, we will call this circumstance the “problem of the number 3”. This problem is related to a profound strangeness of the behavior of large enough number of SFAs. We refer to number three because we choose only three states for CA. This number will appear more than once in our text. To explain a remarkable behavior of SFA (for example, it can produce puzzling objects resembling “rivers” flowing in two dimensions) is a separate task, we will not deal with it now. Yet, we will prove a very interesting theorem related to these SFAs.
Normal Masks, Two-dimensional Automaton Plot (2D-AP), the main Lemma, a strict Formulation of the “X-Problem of Number 3”
Let us give a mathematically strict definition of the “X-problem of number 3”, but let us first talk about what kind of SFAs and their corresponding Masks (neighborhoods) we will consider.
Further on, we will consider only the Masks containing the Neumann Mask in N dimensions. Let us call these Masks normal.
At this point, we are going to limit our Automaton from all sides. Let us imagine a chess figure. This figure can (i) walk on the N-dimensional Lattice one step forward or backward along any of the axes (that is, just along the Neumann neighborhood) and (ii) step into positions (fields) where it has been before. It is obvious that such a figure can visit all the cells in any finite Lattice (ZN) and eventually, return to the starting point (Figure 5).
Figure 5: Panel ‘A’ presents the Neumann Mask (Neighbourhood) for two dimensions (2D). Panel ‘B’ presents the moves of a “chess figure” unfolding the 2D lattice into 1D “string”. Panel ‘C’ presents two dimensional automaton plot (or test plot) illustrating the effect of non-intersection of the CB bands. The picture refers to a onedimensional Mask.
Ignoring (or not permitting) any meaningless moves (e.g. forward and immediately backward) of this figure, we unfold (or transform) an N-dimensional bounded (e.g. closed as in torus) area into one dimension. After that, we place every next position of the CA under the previous one and by doing so we build in the end a so-called “Twodimensional Automaton Plot” (2D-AP) using two variables. On the x-axis, the sweep of the CA into one dimension made with our chess figure. We name this sweep as r. In dimensions with large N, the Neighborhood itself will somehow spread itself along the x-axis, but it does not matter which manner it spreads [7]. The y-axis in 2D-AP is directed downwards and shows the time evolution. Now, let us prove the preliminary Lemma.
The lemma
If SFA contains Neumann Mask, then the following is true:
1) The Mirror Point (for any non-trivial SFA with a return period >2) is not equal to the Start Point.
2) Like the Start Point, the Mirror Point contains exclusively A and B cells.
3) Each C cell on the Test Plot (2D-AP) necessarily touches another C cell on each side and only once. That is, the CB rows run across the Test Plot as non-intersecting strips (Figure 5).
This not very complicated lemma has been proved in [2]. At this point, we will give a strict definition of the “X-problem of number 3”.
We take some Masks (later on, we will call them Perfect), any size of CA and any initial conditions. Then we consider the following: (i) take any arbitrary initial conditions consisting only of A and B cells and remove all the B cells from it on the 2D-AP (it is very convenient to remove B cells (thus making cell space “vacant”) layer by layer from top to bottom: “first”, “second”, “third”, etc…), (ii) “lift” all the cells (they can be either A or C cells) from the lower layers up into the vacant spaces [1].
By doing so, we will build a matrix (from the Start Point to the Mirror Point) having Θ rows along the y-axis and filled with cells A and C. Now, let us take an “additional” initial coloring. That is, we change all the A cells to B cells and B cells to A cells. Now, we will do the same procedure. We will build a matrix having Θ∗ rows along the y-axis also filled with cells A and C as well.
We need to prove the following statement: For any Perfect Mask Θ will always be equal to Θ∗ and the obtained matrices will coincide with each other when all the A cells are replaced by C cells and the C cells are replaced by A cells (Figure 1).
“X- problem of number 3” means exactly this statement.
First, let us note that in the previous study this Axial Automaton has been called Table [1]. We decided to change its name in order to emphasize its central position between “the Ordinary World” and “the Complementary (Parallel) World” and rename is as Axial.
In the study the following has been proven [1]:
Theorem 1 (the correctness theorem):
This theorem states that for all the Masks in figure 1, which are not shaded in black color and for which n<9, there is a Axial Automaton with k=6 and with corresponding Transition Tables (TTs) R-x, R-y, R-z, R+x, R+y, R+z which are obtained from R-x by corresponding substitutions (Figure 4).
First stage
TTs from the above are calculated under the assumption that the corresponding Mask is perfect as follows. Tests are carried out with a random (finite) Lattice size and random initial conditions. After the Automaton reaches its Mirror Point (its Half-Period Point), a “selection” is carried out as described in Chapter 3, with the parameter F retained (F represents the number of the step at which the MP has been reached) and F has index A or C (i.e., FA or FC) depending on what was written on this “dice”. After that, the following substitutions are made: FA (mod 3)=0 ↔&d-x”, FA (mod 3)=1 ↔ ”-y”, FA (mod 3)=2 ↔ ”-z”, FC (mod 3)=0 ↔ ”+x”, FC (mod 3)=1 ↔”+y”, FC (mod 3)=2 ↔ ”+z” [1].
The results serve to construct the corresponding Transition Tables: R-x, R-y, R-z, R+x, R+y, R+z [1].
Second stage
Thus, a new CA is defined. It starts on the same Lattice as the SFA, but with the corresponding replacement of the initials A and B by “-x” and “+x”. This CA has a very small “density”, the latter refers to the ratio of “the number of rows in all the matrices R” to “the maximum number of possible rows” (6n+1). This ratio is rather small for most of Perfect Masks. Yet, it is proven by the method of induction that no other rows can appear during the operation of the CA. (It is also proven by the induction that the Axial Automaton is reversible and the matrices for the inverse R-1 -x, R-1 -y…transformation are also obtained from R-x by the corresponding substitutions [1]. We call Correct a Masks for which there exists an Axial Automaton (Figure 1).
What is the only interesting point in this proof, it always comes to an end. There are no exceptional ideas in it. This is a traditional proof made by an “exhaustive search” and “by induction”.
Axial Automata have their own value. These Automata manifest some new symmetry and there are, in fact, a lot of those symmetries.
In a spirit of study, let us take a certain neighborhood [3] (Figure 6).
Let us ask a mathematician what kind of symmetry it has? The answer will be-the symmetry of a square: Symmetry along the axes “x” and “y” and along the diagonals. Yet, it turns out not to be a complete answer [8].
There exist also some other (!) symmetry. In fact, this new symmetry is represented by R-x Transition Table which is very interesting by itself. We are 100% convinced that there is such symmetry-the R-x Table, an Axial Automaton-exists for a huge number of Masks that are not symmetric. It surely exists for all centrally-symmetric Masks (it is clear from indirect data) and of course the same is true for Masks that have the symmetry of a square. One needs just a very good computer to determine the R-x table. In order to prove the Correctness of this R-x table, by using a brute force search by exhaustion, one needs to exploit an extremely powerful computer (the author has a doubt that such a computer can be built, in principle). “A nested cycle of several thousand values with a depth equal to 53…” it is indeed very challenging! Yet, when n is small enough (n<9), the personal computer copes without difficulty with all the three tasks: (i) finding the TT, (ii) finding the proof of the Correctness, (iii) and finding the proof of the Perfection (it will be shown in the next chapter).
Let us move on to the third stage: The proof of the perfection from the correctness.
What we have called “half-strings” in, we now call “Reduced Lines” [1].
We will call a United Two-dimensional Automaton Plot (U2D-AP) the combination of two passes on one Automaton Plot (2D-AP): The first pass with some initial conditions (fABC(t, r)) and the second one with condition (f*ABC(t, r)) which are additional or complimentary to the (fABC (t, r)) conditions. In figures, one can see examples of several U2D-APs. One can see U2D-APs in the form of an animation (Figures 7 and 8).
Figure 7: On the left, there is U2D-AP for a normal but Imperfect Mask. Black and white lines show the reduced lines for the first few τ values. One can see that Pf and Pf* are not symmetrical with respect to the “centerline”, which is an abscissa with the coordinate t=3τ/2. The “errors” of the symmetry are shown with a thick line.
Figure 8: Panel A-United two-dimensional automaton plot (U2D-AP) for the Correct Mask (3,1) with three examples of the reduced lines (P and V, without “f”) constructed according to the formulas from Panel D of the same figure for τ=2, τ=4 and τ=5. One can see that they are symmetrical with respect to the straight line (t=3τ/2) and coincide with Pf and Vf. Panel B-table R-x for the Mask (3,1). Panel C is a result of axial automaton operation (AAP as well). Panel D shows formulas from describing the operation of axial automaton.
*The arrows show the relationship between Panels A, B, and C by the example of one point (t=6, τ=2, r=1, initial conditions are “arbitrary”). The ovals show those areas that are taken out into the other figures
Let us introduce the concept of a Reduced Line with the index f: (Pf, Pf*) and the Value function on the Reduced Lines (Vf, Vf*). Here, index “f” shows that the Reduced Lines will be determined from the U2D-AP. In principle, it can be introduced for any Fredkin’s Automaton, but we will consider it only for SFAs with normal Perfect or normal Imperfect Masks.
Definition
Reduced Line Pf (τ, r, “In.”) is an integer function (Pf ϵ Z) from three variables τ, r, “In.”, where τ, r ϵ Z and “In.” are some (any) initial conditions. The definition is given by the induction Pf (0, r, “In.”)=0, with an induction step:
In fact, this is the “lift up” mentioned before. A similar definition is valid for function Pf* (τ, r, “In.*”) [1] (Figure 7).
Let us introduce the sgn (sign) function for the quantities {-x, -y...} (sgn (-x)=-1, sgn (+x)=1, sgn (-y)=-1…) and the SGN function for cells A and C: SGN(A)=-1, SGN (C)=1, (SGN (B)-not determined). Let us use these indications to write the Value function on the Reduced Line for “arbitrary” initial conditions: Vf (t, r, “In.”)=SGN (fABC (Pf (t, r, “In.”), r)) and the analogous function Vf* (t, r, “In.”)=SGN (fABC (Pf*(t, r, “In.*”), r)) for the “additional” initials. These are the values that we would obtain from the “lifting up” procedure described in Chapter 3 of reference [1]. There is no connection found between values Vf and Vf* for Imperfect Masks (Figure 7).
Theorem 1 says that for those Masks for which there exists an Axial Automaton (that is, for Correct Masks), we can determine what we now call the Axial Automaton Plot (AAP) [1]. It is obtained by entering the result of the Axial Automaton operation each time into a new row with the number τ. The Reduced Lines on the Test Plot (U2D-AP) with their values (P, P*, V, V*) without index “f” are obtained from the known formulas [1] (Figures 8 and 9).
Figure 9: A detailed calculation of the quantities P (5.1) and V (5.1) from Figure 8. Panel A of two colored images shows 2D-AP (Test Plot) for “arbitrary” initial conditions and for the Reduced Line with τ=5. Panel B shows the formulas and performed calculations. Panel C shows AAP of the Axial Automaton in our case.
We want to prove that for any Correct Mask Pf (τ, r)=P (τ, r) and Vf (τ, r)=V (τ, r). Let us see what other tests of the Transition Tables need to be done in order to assert the above equalities.
Theorem 2 (the perfection theorem).
Let us prove using the method of induction that for any Correct Mask from figure 1 with n<9 and for any τ, the Reduced Lines with index “f” (Pf, Vf, Pf*, Vf*; i.e., the Reduced Lines of U2D-AP) will coincide with the Reduced Lines without index “f” (P, V, P*, V*; the Reduced Lines of AAP). (We talk only about the Reduced Lines Pf, Vf, P, V, because the theorem can be proven similarly for the Reduced Lines Pf*, Vf*, P*, V*).
Test 1
We will call those pairs of cells (columns) of TT which have no pairs (-x, y), (+x, - z), (-y, +z) as Good and we will construct not directed Graph on all the cells of the Mask using these pairs. If one can pass using the edges of the Graph from the central cell to all other cells of the Mask, then Test 1 for the Mask is declared valid. All Correct Masks, with n<9, from the figure 1 will pass this test. In all one-dimensional Masks with "natural" numbering of cells (that is the one made in a row) there are two simple passages from the central cells to the left and to the right (Figure 10).
The induction is related to τ, it will be proven simultaneously that condition 3 continues to be valid. The condition is as follows: For all vectors and for all the passages where ra is vector’s origin and rb is vector’s end the following comes true (Figure 11):
Formula 3 bears two functions for our proof.
On one hand, fulfillment of a Formula 3 will allow us to place correctly initial letters of A and С for an induction step (Figure 12).
On the other hand, if we prove that for all rows of TT, the letter lying under the central cell is correctly restored only from the content of the row under consideration, then this will prove the entire Theorem and, further on, validity of formula 3! We will explain it in more detail below.
Let us assume that Test 1 and Test 2 (the restoration of the subsequent letter from our row; see further on) are passed. Then let us assume that the formula 3 ceased to be met. We will take the first step of τ on which δab is equal to two (Figure 13).
In one move (i.e., when τ increases by 1), if the letter has a “+” sign, then the Reduced Automaton Line is shifted down by two cells (on a 2D-AP) and if the letter’s sign is “-“, then it is shifted down by one cell. Therefore, it is clear that δ cannot immediately become equal to, say, three. It must necessarily pass through δ=2.
It turns out that δ can become equal to 2 only for a few pairs. These are pairs: (-x, +y), (+x, -z), (-y, +z) where one of the values is the beginning of a vector of the bypass passage, and the second is its end. Yet, these pairs do not appear in our TT in a process of the bypass passage. It turns out that they cannot appear there in principle (see Theorem 1). So we have encountered a contradiction. Therefore, the absolute value of δ is and will remain less than two.
It was necessary to make the last decisive check.
Test 2
Let us perform the test for generally complex Mask in N dimensions. Let us consider the way it is carried out? In this test, the rows from TT are taken one by one (note that the test is carried out for all the rows of the TT). First, we build four empty N-dimensional Lattices (we choose four as a start point; and if it turns out that four is not enough, we will add one more Lattice and will start checking from the beginning), which in all directions are several-fold larger than the Mask under consideration (to start with, say, 3-fold larger Lattices, If it happens that we go beyond the limits, we can increase the Lattice size and repeat the test again from the beginning). Let us number these four Lattices according to time t’: …t’=-2, t’=-1, t’ = 0, t’=1, t’=2 …. Then, we begin to “restore” our truncated “Automaton Plot” from what we have at the moment.
The letters A or C are placed into the center of Lattice 0 (t’=0) dependently on a sign of the state (x, y or z) existing in the central (zero) point of the row of the Transition Table under the test: If sign=-1, then we fill the center of Lattice 0 with letter A and if sgn=+1, we fill the center of Lattice 0 with letter C (Figure 12).
The corresponding letters for Hypercubes with numbers … -2,- 1, +1, +2 … are written in the manner shown in figure 11. All letters of our rows proceeding from the shifts are brought to the cells of the Hypercube, as we perform the bypass passage. In all other cells of Hypercube are filled with "-1". It represents the fact that the value is not known yet (Figure 14).
Figure 14: The beginning of testing of two rows from TT R+z and R-x for the Mask (5, 3). Rows can happen to be either simple or difficult for the analysis. The majority of rows in any TT (678 of 702 for a mask (5, 3)) are simple. This means that the value we expect to obtain is calculated directly from the row. But there are also a few difficult cases (24 of 702 for a mask (5, 3)). Then it is necessary to address to the proof of Theorem 1 and study how such a row could appear, in general.
Now let us begin the restoration of the “truncated” Test Plot under conditions of lack of information. First, we look through all the cells in all the Lattices that are filled with “-1” and for which we can determine value f(C) and, correspondingly, which of letters A, B or C are placed in the given cell of the Lattice(s). The ultimate goal is to fill the Lattices with letters (we need to find whether letter A or C goes into Lattice 1 or 2) and what is the letter immediately below the zero point of Lattice 0.
If we cannot determine which of letters A or C lie under the zero point of Lattice 0 (we still have “-1” there) or (another plausible scenario) the letter (A or C) with corresponding “+” or “-“signs does not match the index of the Transition Table from which we took the row under the test, then Test 1 (for the entire Mask!) is considered as failed (Figure 15).
So, one by one we check all the 6C rows and, eventually, we find that all the Correct Masks from figure 1 have passed the test! Fig 16 shows the checking of TT R-x of our “favorite Mask (3, 1) (Figure 16).
Figure 16: Panel А shows Table R-x for the Mask (3.1). Panel B shows how this Table is sorted (for clarity) and collected in similar clusters. Panel C shows those parts of the rows that do not participate in the restoration are closed with white “curtains”. Panel D shows the restoration of the letter according to what was written before. Actions are performed from left to right. After performing the next action, the letters are shown “white”, the newly appeared ones are shown “black”. It is seen that in all the cases, the letter “-x” is restored correctly.
This, taking into account earlier considerations, proves the Theorem! In more details, for all τ and r the following is valid:
Corollary
All the Correct Masks with n<9 from figure 1 are Perfect.
In accordance to the formulas presented in Figure 9 for the Axial Automaton, the content of rows (and their arrangement) in the “lifted up matrices” for the SFAs will repeat that for matrixes L and L* where all the “negative” letters are replaced by A and all the “positive” letters, by C [1]. On the other hand, we know that L and L* are connected by relation L=S (L*), where S is a substitution (+x, +z, +y, -x, -y, -z). That is, the pluses change to minuses and vice versa. Consequently, all the considered Masks in figure 1 are perfect.
The concept of “normality” is a bit excessive, so let us introduce the concept of “Generalized Normality”.
Definition
A Mask of Generalized Normality is such a Mask in N-dimensions that has one of the corresponding elements in the direction of each of the axes: Either element 1, see its depiction in figure 14 (it is the same as in normal Mask) or element 2 (symmetrically placed “dominos”, in the direction of the corresponding axis). It is obvious that this is enough for the preliminary Lemma to work (Figure 17).
There are two obvious problems arising.
Problem 1
Is it possible to prove (or disprove) that any Generalized Centrally- Symmetric Normal Mask is Perfect?
Problem 2
Is it possible to determine the Perfection of the Mask directly from the type of the Mask?
We propose to name the new mathematical discipline which we are developing the discrete N-dimensional Geometry. We believe that it can be an appropriate term.
In mathematics, there are finite simple groups. As the mathematical textbooks say that all this is about the rotation of several polyhedra in the N-dimensional space.
We acted differently: We penetrated into one cell of an N-dimensional lattice and looked at things “from there”. After that, we have suddenly discovered a multitude of most unexpected and surprising symmetries. Using the computer, we learned about some properties of those symmetries, yet the inner essence of those symmetries remains unclear.
The author is grateful to Drs. V.Belyaev and E.Moskovets for reading this article and for their assistance.