Recurrent 2-dimensional sequences can encode counting

Recurrent 2-dimensional sequences can encode counting Mihai Prunescu

∗

Abstract A recurrent 2-dimensional (double) sequence t(m, n) is given by fixing particular sequences t(m, 0), t(0, n) as initial conditions and a rule of recurrence t(m, n) = f (t(m, n − 1), t(m − 1, n − 1), t(m − 1, n)) for m, n ≥ 1. The recurrent double sequences with values in finite sets are known to be Turing complete, in the sense that all possible run of a Turing machine can be encoded in a recurrent double sequence over some finite set (alphabet). We display such sequences with constant initial conditions and values in the set {0, 1, 2} able to model binary counting, successor functions and finite ordinals. The point is that three values prove to be sufficient to model such concepts. Key Words: recurrent 2-dimensional sequence, Turing-complete models of computation, binary counting, successor function, finite ordinal. A.M.S.-Classification: 05B45, 28A80, 03D03.

1

Introduction

The recurrent 2-dimensional (double) sequences over finite sets (alphabets) build a Turing-complete model of computation, see [8] for a proof. In comparison with other models of computation, the recurrent n-dimensional sequences are easier to be visualized - or at least small pieces of them in dimension 2 are so. Their interest is of purely theoretic nature. The study of computability is based on models like Turing or Register Machines, which are complicated multi-sorted objects, because their description contains states, alphabets, bands, heads, registers, movements and so on. In the case of recurrent 2-dimensional sequences, one only studies a finite function which has to be iterated. It is not the case to redevelop the whole theory of computability in this setting, but Turing completeness is an argument for their intrinsic interest. The neighborhood-wise recurrence makes them able to model some natural phenomena: crystals and quasi-crystals (see [6, 7]), mechanical behaviors (see [19]), some other processes described by solutions of differential equations (see [2]), and much more. Stephen Wolfram started in [21] the project to classify the behaviors in similar discrete dynamic processes. He also commented their possibility to model arbitrary natural, fractal or chaotic phenomena. However, the recurrent double sequences over finite sets have the same disadvantages like most of the alternative models of computation, but in a very severe form: it is very hard to program or design them, and their output is difficult to be read (decoded). In this article display such sequences with constant initial conditions and values in the set {0, 1, 2} able to model binary counting, successor functions and finite ordinals. The point is that three values prove to be sufficient to model such concepts. Definition 1.1 Let A be a finite alphabet, 1 ∈ A be a fixed element and f : A3 → A be a function, called rule of recurrence. This rule defines the recurrent 2-dimensional sequence t : N2 → A if t(N, 0) = t(0, N) = 1 and for all i, j ≥ 1, t(i, j) = f (t(i − 1, j), t(i − 1, j − 1), t(i, j − 1)). We refer to this sequence as (A, f, 1, 1). ∗ Simion Stoilow Institute of Mathematics of the Romanian Academy, Research unit 5, P. O. Box 1-764, RO014700 Bucharest, Romania. [email protected], [email protected]

1

We will concentrate on the case A = F3 , the field with two elements. Incidentally we use also the field with two elements F2 . All functions g : Fnp → Fp can be expressed by polynomials with coefficients in Fp . For x ∈ F2 we write ¬x = x + 1. F2 is also seen as a boolean algebra, so the boolean operation symbols will be freely used. All matrices will be indexed starting with i = 0 and j = 0. Most of the time we use the term double sequence for 2-dimensional sequence. If U is some matrix, U (i, j) denotes the corresponding element of U . The same conventions work for infinite matrices, i. e. double sequences. We recall now the term of automatic 2-dimensional sequence in terms of 2-dimensional sequence generated by substitution, see [10], . . . , [14]. A double sequence is called s-automatic if it is the result of a two-dimensional expansive substitution of type a → sa, with a ≥ 1 rules and scaling factor s ≥ 2. This means that there is a set Σ of a × a matrices over the basic alphabet of the sequence. One of those matrices, called M1 , is the start matrix. For every one of the elements of Σ there is a substitution rule of the form:  M11 M21  Mi ;  .  ..

M12 M22 .. .

··· ··· .. .

 M1s M2s   ..  , . 

Ms1

Ms2

···

Mss

where all Mi,j ∈ Σ, such that the substitution may continue next step with all of them. The only one condition to fulfill is that for i = 1, M11 = M1 . This makes the substitution process expansive in the sense that for all n ≥ 1, the matrix Σn−1 (M1 ) is the left upper minor of the matrix Σn−1 (M1 ). As this point we mention that 2-dimensional sequences are represented like matrices, or respecting the praxis in computer graphics. The coordinate x grows from left to right, and the coordinate y grows downwards. Examples of recurrent 2-dimensional sequences that encode counting in binary and the successor have been used by the author as examples of such sequences that are not automatic. See [14] and [15]. While in [14] the example given used 4 values instead of 3, the example in [15] was too far away of explicitly encode counting. The examples given here have their own interest by combining both features of encoding counting with the minimal possible number of values used. The fourth section contains examples of geometric growth obtained by recurrent 2-dimensional sequences which are automatic. The fifth section offers an example of superexponential growth, which makes the transfer to the last section, dedicated to encoding ordinals in three-valued recurrent 2-dimensional sequences.

2

Counting in binary

Counting in binary 0, 1, 10, 11, 100, 101, . . . is fundamental in computer science. It is the most simple way to count using a base of numeration. In binary, like in all other bases of numeration, the words representing numbers have lengths growing logarithmically with the represented value. Binary counting can be modeled already using only two-valued recurrent 2-dimensional sequences, see Figure 1. The recurrence x + y + yz is applied here to initial conditions given by the periodic sequences (01) and (0) instead of constant sequences (1) and (1). In the Figure white cells represent zeros and black cells represent ones.

2

Figure 1: (F2 , x + y + yz, (01), 0), 128 × 10. Observation 2.1 The function f : F32 → F2 , f (x, y, z) = x + y + yz, satisfies: ( ¬x if y = 1 ∧ z = 0, f (x, y, z) = x + ¬(y → z) = x else. Recall that 2-dimensional sequences are represented as matrices, such that the second index increases downwards. Using this convention, every application of the rule of recurrence f in t has the form:   y z x f (x, y, z) According to Lemma 2.1 there are in fact only the rules: Alternation A and Repetition R.  A=

1 x

0 ¬x



 ;

R=

y x

z x

 | if (y, z) 6= (1, 0).

Theorem 2.2 Let Ly = (t(i, y) | i ≥ 0) be the y-th row of the recurrent double sequence (F2 , x + y + yz, (01), 0). For y ≥ 0, all the rows Ly are periodic infinite words of period py , where py is the y y word 02 12 . Consequently, for x ≥ 0, the column x (read upwards) consists of an infinite number of zeros, preceding the binary representation of the number x. 0

0

Proof: The proof is done by induction. The first period p0 = 01 = 02 12 , by definition. The induction step works as follows: n ; n + 1: The first two periods of Ln , if concatenated, form the word: n

n

n

n

02 12 02 12 . . . Ln+1 starts with a 0. For the first 2n steps we repeatedly apply the rule R and write zeros. For the first letter of the next block of length 2n we apply the rule A and we write a zero. All other letters of this block are written with the rule R and are zeros. For the first letter of the next block of length 2(n+1) we apply the rule A and we write a one. All other letters of this block are done with the rule R and are ones. (n+1) (n+1) 02 12 ... 2 n

As a consequence, if someone folds a rectangular 2 × n sheet of paper representing this recurrent double sequence in the middle, to get a rectangular sheet 2n−1 × n, every black square falls over a white square and every white square falls over a black square. All such patterns are mirrored in negative. As one can see by direct computation, there is no two-valued recurrent double sequence with constant initial conditions interpreting the binary counting. This can be done however with threevalued sequences. Take a function g : F33 → F3 satisfying the following conditions: g |{0, 2}3 ∼ = f |F32 , where f (x, y, z) = x + y + yz, {0, 2} is seen here as a subset of F3 and 2 ∈ F3 is interpreted as 1 ∈ F2 . Supplementary, the function g must satisfy g(0, 1, 1) = 2 and g(1, 1, 1) = g(1, 1, 0) = 0. The recurrent double sequence with initial conditions t(n, 0) = 1 and t(0, m) = 1 can be seen in Figure 2. It is a three-valued recurrent double sequence with constant initial conditions interpreting the binary counting, see Figure 2. In the Figure, zero = white, one = black and two = gray. We 3

Figure 2: (F3 , g, 1), 128 × 9.

Figure 3: (F3 , 2x2 + y 2 + z 2 + 2z, 1), 129 × 10. do not display a concrete polynomial computing g because all such polynomials have too many monomials. On the other hand, only the given conditions are used in the recurrence. Other triplets do not occur in this recurrence. Of course, when one reads the binary numbers, the first row and the first column must be skipped.

There are also simpler polynomials interpreting the binary counting over F3 . The polynomial 2x2 + y 2 + z 2 + 2z does it for the same constant initial conditions t(n, 0) = 1 and t(0, m) = 1, as one can see in Figure 3. This time the values 1, 2 ∈ F3 are interpreted as the binary 1, and the first row (like the first column) must be skipped.

3

Successors

The successor function S(x) has been introduced in the Axioms of Arithmetic, for example in the axiom systems of Peano, Tarski, or Robinson, see [20]. It is known that those axiom systems (like any other one) can found only fragments of Arithmetic, but we do not follow now this idea. Using the successor, the sequence of natural numbers reads 0, S(0), SS(0), SSS(0), . . . , where we already used a shorter writing, like SS(0) instead of S(S(0)). Introducing the symbol 1 for S(0) and using the fact that S(x) = x + 1 and the associativity of addition, the sequence of numbers reads 0, 1, 1 + 1, 1 + 1 + 1, . . . . In both ways, the words representing numbers have lengths growing linearly with the represented value. The most easy way to get an arithmetic progression in a recurrent double sequence is shown in the Figure 4. Here for k ≥ 1, the column k presents an alternating pattern of length k and then becomes constant 0. However, this simplistic behavior is not sufficient to construct counterexamples to automatic sequences. The sequence is n-automatic for all n ≥ 2. More exactly, it can be generated by square substitutions of the following types. If n = 2k, a substitution of type 3 → 3n with 7 rules generates the sequence. One set of 7 many 3 × 3 matrices representing the basic minors is good for all substitutions with even scaling factor. If n = 2k + 1, a substitution of type 4 → 4n with 10 rules generates the sequence. Again one set of 10 many 4 × 4 matrices representing the basic minors is good for all substitutions with odd scaling factor.

As we have told in the introduction, some recurrent double sequences that used for counterexamples to automatic 2-dimensional sequences encoded arithmetic progressions along their diagonal.

4

Figure 4: (F2 , y + xy, 1). 20 × 20 Definition 3.1 We say that a recurrent double sequence over some finite alphabet interprets a successor function if it contains a sequence of similar patterns growing linearly along the main diagonal. An example with square patterns can be seen in Figure 5.

Theorem 3.2 The recurrent double sequence (F3 , x2 y 2 + y 2 z 2 + 2xy 2 + 2y 2 z + x2 + y 2 + z 2 + xy + xz + yz + x + 2y + z + 1, 1) interprets the successor function by a square pattern along its diagonal. All cells on the main diagonal are red and blue, and the blue cells are ultimately those of coordinates (2n2 + n + 6, 2n2 + n + 6). Proof: We denote the polynomial by f (x, y, z). This polynomial is symmetric in x and z, and the initial condition is symmetric relatively to the main diagonal, so the whole recurrent double sequence has this symmetry. Consequently, it will be sufficient to discuss what happens above the main diagonal. Call S1 the square with vertexes (9, 9)(9, 16)(16, 16)(16, 9). We refer easier to this square as the diagonal square starting at 9 with edge 7. According to Figure 5 we rename the values: zero white, one red and two blue. If the square Sn is the diagonal square starting at xn of edge ln . We call red stair a sequence of red cells of the form (x, y)(x, y + 1)(x + 1, y + 1)(x + 1, y + 2) . . . . Now we will prove by induction the following facts: The horizontal border send inside the double sequence red stairs starting with the cells (11+4n, 6), n ∈ N. Every such red stair goes away from the border since it meets a square Sn . There are no other blue cells in the set [10, ∞) × [10, ∞) as those on the edges of the diagonal squares Sn , and for every diagonal square Sn two more adjacent cells with coordinates (xn + ln + 1, xn + 1) and (xn + 1, xn + ln + 1). All cells on the edges of Sn are blue, excepting (xn + ln − 1, xn ), (xn + ln , xn ), (xn , xn + ln − 1), (xn , xn + ln ) and (xn + ln , xn + ln ), which are white. All interior cells adjacent with the edges (xn , xn )(xn + ln , xn ) and (xn , xn )(xn , xn + ln ) are white, excepting (xn + 1, xn + 1), (xn + 1, xn + ln − 1) and (xn + ln − 1, xn + 1), which are red. All other interior cells are red and white in a chess-like pattern, such that the cells on the main diagonal are red. See Figure 6.

The exterior cells along the edges (xn + ln , xn )(xn + ln , xn + ln ), (xn , xn + ln )(xn + ln , xn + ln ) start with white, blue, red, followed by a sequence of white cells, excepting the last one, which is red. 5

Figure 5: (F3 , x2 y 2 + y 2 z 2 + 2xy 2 + 2y 2 z + x2 + y 2 + z 2 + xy + xz + yz + x + 2y + z + 1, 1). 59 × 59

Figure 6: The square S2 and the adjacent cells.

6

Figure 7: A new square is born.

Figure 8: Meeting of an edge with a red stair. The edge length grows by 4. The exterior cells along the edges (xn , xn )(xn + ln , xn ) and (xn , xn )(xn , xn + ln ) are alternated red, white, red (starting with red), excepting the last three which are red, red and white. The triangle built by two edges of consecutive squares and a red stair is covered by a white - red chess pattern, excepting for the vertical edge, which is doubled by a white segment.

We see that for all n ≥ 1, xn+1 = xn + ln , ln = ln−1 + 4, ln = 4n + 3, xn = 2n2 + n + 6. In particular, the edges build an arithmetic progression and the last vertex cell of the square Sn touches the first vertex cell of Sn+1 only in one vertex. For the verification, one has to consider the key events in the double sequence and apply those rules that operate there. For example, a red stair is born by the rules f (0, 2, 1) = 1 and f (1, 1, 2) = 1 and propagate with the rules f (1, 1, 2) = 0, f (1, 1, 0) = 1), f (1, 0, 0) = 0, etc. Most important repetitive events are the birth of a new square, represented in the Figure 7 and the meeting of an edge with a red stair, see Figure 8. This event makes every edge bigger with 4 units then the last edge and start closing the square.

In consequence, the edge lengths build an arithmetic progression with ratio 4, so ln = 7+4(n−1) = 4n + 3 and the start points of the squares are given by:

xn+1 = xn + ln = xn−1 + (ln + ln−1 ) = · · · = x1 + (ln + · · · + l1 ) = x1 + 7n + 2n(n − 1) = 2n2 + 5n + 9 2

So xn = 2n2 + n + 6, as it was to prove. 7

Figure 9: (F3 , x2 y 2 + y 2 z 2 + 2xy 2 + 2y 2 z + x2 + y 2 + z 2 + xy + xz + yz + x + 2y + z + 1, 1). 243 × 243

The arithmetic progression and (implicitly) the counting by successor are easily seen in a bigger segment, like in Figure 9.

8

Figure 10: (F3 , x2 y 2 + y 2 z 2 + 2x2 y + 2yz 2 + 2xy + 2yz + 2y + x2 + z 2 + 2x + 2z + 2, 1). 729 × 729

There are also other three-valued recurrent double sequences modeling counting by successors along the diagonal, but not by square patterns. See Figure 10, where a sequence of rhombuses growing in arithmetic progression occurs.

9

Figure 11: (F3 , 2y 2 + 2z + y + 2x2 y + 2xz 2 + xyz + 2, 0). 729 × 729

In Figure 11 there one sees a recurrent double sequence representing counting by successor in a non-symmetric manner. The stair has steps growing in arithmetic progression, and between two consecutive steps there are 1, 2, 3, 4, . . . , n, . . . red cords. After counting the red rectangular threecell corners occurring in every step of the stair, we observe that this double sequence interprets in the same time counting with successor and the sequence of triangular numbers.

10

Figure 12: (F3 , x2 z + xz 2 + 2xz + y 2 + 2x2 y + 2yz 2 + 2xy + 2yz + 2x2 + 2z 2 + x + z + 2, 1). 243 × 243

There are also more complicated related phenomena. In Figure 12 a recurrent double sequence generates a sequence of similar rhombuses. The rhombuses are alternating bigger with a quantity ∆ and smaller with a quantity δ, where δ < ∆.

4

Geometric progressions

Geometric progressions are not really a way to count. They appear frequently in recurrent double sequences over finite alphabets, specially when the sequences happen to be automatic. However, after we have seen the main example of the precedent section, where a sequence of squares growing in arithmetic progression has been emulated by a three-valued recurrent double sequence, we find worth to show a recurrent double sequence producing a sequence of diagonal squares growing in geometric progression (see Figure 13). We recall the convention that white cells represent the value 0, red cells the value 1 and blue cells the value 2. Theorem 4.1 The recurrent double sequence (F3 , 2z + 2x + z 2 + x2 + 2y + yz 2 + x2 y + 2y 2 z + 2xy 2 + 2xz 2 + 2x2 z, 1) interprets a geometric progression by a square pattern along its diagonal. All cells on the main diagonal are ultimately red and white, and the red cells are ultimately only those of coordinates (5 · 2n , 5 · 2n ). 11

Figure 13: (F3 , 2z + 2x + z 2 + x2 + 2y + yz 2 + x2 y + 2y 2 z + 2xy 2 + 2xz 2 + 2x2 z, 1). 243 × 243

Proof: This polynomial is again symmetric in x and z, and the initial condition is symmetric relatively to the main diagonal, so the whole recurrent double sequence has this symmetry. Consequently, it will be again sufficient to discuss what happens above the main diagonal. For n ≥ 0, call Rn the square with vertexes An Bn Cn Dn where An = (5 · 2n , 5 · 2n ), Bn = (5 · 2n+1 − 1, 5 · 2n ), Cn = (5 · 2n+1 − 1, 5 · 2n+1 − 1), Dn = (5 · 2n , 5 · 2n+1 − 1). This is exactly the square starting at (5 · 2n , 5 · 2n ) with his left upper cell, and edge length equal with 5 · 2n . We call blue stripes the alternating white - blue stripe pattern occurring along the borders. Now we will prove by induction the following facts: The blue stripes start at x ≥ 1. For k ≥ 1 and x = 2k + 1, the stripe starting at x is white and has length k. It always ends with a red cell of coordinates (2k + 1, k + 1). For k ≥ 1 and x = 2k, the stripe starting at x is blue and has length k. All cells on the edges of the square Rn are blue for n ≥ 1, with the following exceptions: The cells An , Bn , Dn , Bn + (1, 0) and Dn + (0, 1) are red. The cells Cn , Bn − (1, 0) and Dn − (0, 1) are white. 12

Figure 14: The square R2 , starting in (20, 20) with edge length equal 20, and the adjacent cells.

Figure 15: Here one sees why the edge length of the square Rn+1 is exactly two times the edge length of the square Rn . This configuration repeats with every new generation of a square.

All cells inside Rn are white for n ≥ 1, excepting Bn + (−1, 1) and Dn + (1, −1), which are red. All cells touching Rn from outside are white for n ≥ 1, with following exceptions: An − (1, 0), An − (0, 1), Bn − (3, 1), Cn + (1, 0), Cn + (1, 1), Cn + (0, 1) and Dn − (1, 3) are red. Bn − (1, 1), Bn + (1, −1), Bn + (0, 1), Dn − (1, 1), Dn + (−1, 1) and Dn + (1, 0) are blue. We observe that the configurations around Bn and Dn are due to the meeting between the square and the blue stripes, and the configurations around An and Cn are due to the closure of the square Rn−1 and the beginning of Rn+1 . The proof in detail consists of checking the action of the recurrence rules, as already sketched in the section on arithmetic progressions (successors). 2

Using the method developed in [10, 11, 12, 13, 14, 15] it is easy to show that the recurrent double sequence analyzed in Theorem 4.1 is 2-automatic. More exactly, it is the result of a twodimensional expansive substitution of type 5 → 10 with 29 rules. This means that there is a set Σ of 29 many 5 × 5 matrices over F3 . One of them, called M1 , is the start matrix. For every one of the 29 matrices there is a substitution rule of the form: Mi ;



Mj Ml 13

 Mk . Mm

Figure 16: (F3 , 1 + 2z + 2x + y + 2y 2 z 2 + 2x2 y 2 + 2xz 2 + 2x2 z, 1), 243 × 243 Here the matrix on the right-hand side is 10 × 10 and consists of four blocks that are matrices from the set Σ, such that the substitution might continue. There are also other three-valued sequences producing squares on the diagonal, that grow in geometric progression.

In Figure 16 is shown a recurrent double sequence of diagonal adjacent squares whose initial edges are middle edges in the central triangles of a substitution pattern which is similar to Pascal’s Triangle mod 2. This sequence is 2-automatic. It can be also produced by a substitution of type 8 → 16 with 17 rules.

14

Figure 17: (F3 , 1 + 2x + y + y 2 + 2z + 2xy + 2xz + 2yz + xyz, 1), 729 × 729

In Figure 17 is shown a recurrent double sequence producing a sequence of diagonal non-adjacent blue squares, growing with ratio 3. This sequence, which is a surprising combination between Pascal’s Triangle modulo 3 and Sierpinski’s Carpet (see [9]), is 3-automatic. More exactly, it can be constructed also by a two-dimensional expansive substitution of type 3 → 9 with only 6 rules. At this point we stress the fact that Sierpinski’s Carpet is not at all a good example of diagonal sequence of squares in geometric progression. Although it can be given by the recurrence (F3 , x+y+z, 1) and is 3-automatic, because it can be generated by a substitution of type 1 → 3 with three rules (a plane morphism), and although it contains arbitrarily big squares on its diagonal, big squares alternate there with small and tiny squares.

15

Figure 18: (F3 , z + x + yz + xy + 2yz 2 + 2x2 y + 2y 2 z + 2xy 2 + y 2 z 2 + x2 y 2 , 1), 243 × 243

In Figure 18 one sees a recurrent double sequence producing a part of the borders of the previous example. This sequence is also 3-automatic. It can be a generated by a substitution of type 3 → 9 with 5 rules. This example has the following property: all diagonal cells of coordinates (3k , 3k ) are blue. All other diagonal cells, excepting (0, 0) which is red, are white. For general properties and plenty of aspects and applications of automatic sequences see [1, 2, 4, 5, 16, 17, 18, 19].

5

A super-exponential behavior

We complete the last two sections with a short observation. There is a three-valued recurrent double sequence that displays a sequence of left-upper squares with a super-exponential rate of increment. This sequence is given by (F3 , z + x + yz + xy + yz 2 + x2 y + 2y 2 z + 2xy 2 + xz + 2xz 2 + 2x2 z, 1). See Figure 19.

Theorem 5.1 Consider the sequence (xn ) defined by x1 = 1 and xn+1 = xn + 2xn . The recurrent double sequence (F3 , z +x+yz +xy +yz 2 +x2 y +2y 2 z +2xy 2 +xz +2xz 2 +2x2 z, 1) defines for n ≥ 1 16

Figure 19: (F3 , z + x + yz + xy + yz 2 + x2 y + 2y 2 z + 2xy 2 + xz + 2xz 2 + 2x2 z, 1), 243 × 50 the sequence of squares (Bn ) with vertexes of coordinates (2, 2) + 3 · [(0, 0)(xn , 0)(xn , xn )(0, xn )]. Proof: The double sequence is again symmetric about the main diagonal. Starting with the cell of coordinates (2, 2) the margins send parallel red lines towards the interior. Successive red lines have mutual distances equal 3 cells. The vertical red lines send horizontal parallel blue lines with mutual distances equal also 3 cells. Every red line stops if it meets a blue line orthogonally or one cell after meeting a red line orthogonally. Every blue line stops after meeting a red line orthogonally. If the square Bn arose, a next square is possible only when all xn many blue lines sent by Bn to the right side (or downwards) are dead, but this happens only after 3 · 2xn many cells to the right (downwards). If there is no more blue line, then two (vertical and horizontal) red lines live until they meet on the main diagonal and create a new square. 2 Consequently, the first values of xn are 1, 3 = 1 + 21 , 11 = 3 + 23 . The next value will be 11 + 211 = 2059 and the next square can be seen by the coordinate x = 6179. Remarkably, this sequence combines the features of binary counting with square building and realizes a superexponential increment. The general term of the sequence (xn ) looks like:

1

1

xn = 1 + 21 + 21+2 + 21+2

1

+21+2

1

+ 21+2

1

1 +21+21

+21+2 +21+2

+ . . . [n − 1 main additions]

If En is the expression in +, 2x and ”1”, representing xn , then En = En−1 + 2En−1 . This fact already introduces a kind of fore-taste for the next Section: Ordinals.

6

Ordinals

The sequence of ordinals (or ordinal numbers) has been introduced by Georg Cantor in [3], and is the sequence of all sets, as constructed also nowadays in Set Theory. Those ordinals which are finite sets represent the natural numbers and enumerating them is again nothing else as counting. The first ordinal is the empty set ∅. An ordinal is the set of all ordinals built before. Applying these two rules, the sequence of finite ordinals reads ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, . . . . The words representing ordinals have lengths growing exponentially in the represented value. Since now, the author did not find any recurrent double sequence with three values interpreting the sequence of finite ordinals. This problem remains open. However, there are some sequences interpreting a related concept, the mirrored finite ordinals with n initial symbols, for n = 2 and n = 3. Definition 6.1 Let n ≥ 1 be a natural number, and ∅1 , . . . , ∅n some new different symbols. The sequence of finite ordinals with initial symbols ∅1 , . . . , ∅n is the sequence of expressions (and sets) (om ) defined by om = ∅m for 1 ≤ m ≤ n and om = {o1 , . . . , om−n } for m ≥ n + 1. So the sequence of finite ordinals with initial symbol ∅1 = ∅ is exactly the sequence of finite ordinals introduced before. The sequence of finite ordinals with initial symbols ∅1 and ∅2 17

reads: ∅1 , ∅2 , {∅1 }, {∅1 , ∅2 }, {∅1 , ∅2 , {∅1 }}, {∅1 , ∅2 , {∅1 }, {∅1 , ∅2 }}, . . . . The sequence of finite ordinals with initial symbols ∅1 , ∅2 and ∅3 reads: ∅1 , ∅2 , ∅3 , {∅1 }, {∅1 , ∅2 }, {∅1 , ∅2 , ∅3 }, {∅1 , ∅2 , ∅3 , {∅1 }}, {∅1 , ∅2 , ∅3 , {∅1 }{∅1 , ∅2 }}, {∅1 , ∅2 , ∅3 , {∅1 }, {∅1 , ∅2 }, {∅1 , ∅2 , ∅3 }} . . . . We observe that the concept of ordinal with n ≥ 2 many initial symbols is not appropriate for infinite ordinals and transfinite induction, because it does not support the limit steps of transfinite induction. However, we use this concept only over finite ordinals. The ordinals will appear in recurrent double sequences in shape which is not the most economic way to write them down. This shape is complicated enough to justify a new definition. We recall the convention that when someone writes down a set, repeated elements are not considered new elements, and the order in which they occur in the list is not relevant. By convention, {4, 2, 2, 1, 3, 4, 3} = {1, 2, 3, 4}. The following definition makes intensively use of this convention. Definition 6.2 Let n ≥ 1 be a natural number, and ∅1 , . . . , ∅n some new different symbols. We introduce also a new symbol ”−” (the mirror). If ”−” appears between two elements of a set given as list of its elements, it has the same meaning as a comma. The sequence of finite mirrored ordinals with initial symbols ∅1 , . . . , ∅n is the sequence of expressions (sm ) defined by sm = ∅m for 1 ≤ m ≤ n and sm = {sn−m , . . . , s1 − s1 , . . . , sm−n } for m ≥ n + 1. So the sequence of finite ordinals with initial symbol ∅1 = ∅ starts with ∅, {∅ − ∅}, {{∅ − ∅}, ∅ − ∅, {∅−∅}}, etc. The finite mirrored ordinals with m initial symbols become much more complicated. However, the rule of neglecting order and repeated elements acts inductively. For given number m of initial symbols and for every n ≥ 1, one has the equality on = sn , understood as equality of sets. Lemma 6.3 Consider the sequence (sn ) of finite mirrored ordinals with two initial symbols ∅1 and ∅2 . For n = 2k + 1 ∈ N, sn starts with k many opening parentheses followed by the symbol ∅1 , respectively ends with the symbol ∅1 followed by k many closing parentheses. For n = 2k, k ≥ 1, sn starts with k many opening parentheses followed by the symbol ∅2 , respectively ends with the symbol ∅2 followed by k many closing parentheses. Proof: Both statements (for n odd and for n even) are proven by induction, using only the definition. In both cases the induction step is 2. 2 Theorem 6.4 The recurrent double sequence (F3 , x2 y 2 + y 2 z 2 + y 2 + xz + 2y + 2, 1) interprets the finite mirrored ordinals with two initial symbols in white rectangles. See Figure 20.

Proof: The recurrence f (x, y, z) : F33 → F3 is again symmetric in x and z, so the whole sequence is symmetric along the main diagonal. The symmetry is the mapping σ : N2 → N2 given as (u, v) ; (v, u). In the proof we will call ordinals all closed rectangles with coordinates (u, v), (u + k, v + k), (v + k, u + k), (v, u), u, v, k ∈ N, whose border cells contains only the value 0 (respectively, are white). We will call main ordinals those ordinals which are not contained in the inner of other ordinals. All other ordinals are called inner ordinals. If an ordinal b lies in some ordinal a and there is no other ordinal between them, we say that b is a direct subordinate of a. The main ordinals form a sequence S1 , S2 , S3 , ... as they arise along the main diagonal. Let the edges of Sn be denoted as An , Bn , σ(Bn ), σ(An ), where the notation is compatible with the definition given above. We call the lattice 2Z × 2Z + (0, 1) upper lattice, the lattice 2Z × 2Z + (1, 0) lower lattice and the lattice 2Z × 2Z central lattice. We say that an ordinal is in increasing mood if on those edges that are parallel with the main diagonal, the first, third, fifth, and all the odd cells, touch outer red cells in one vertex. We say that an ordinal is in decreasing mood if on those edges that are parallel 18

Figure 20: (F3 , x2 y 2 + y 2 z 2 + y 2 + xz + 2y + 2, 1), 150 × 150 with the main diagonal, the second, fourth, sixth, and all the even cells, touch outer red cells in one vertex. Following statements are proven simultaneously by induction: For n ≥ 1, An = (2n+1 +1, 2n+1 −2n+2). For n ≥ 2, Bn−1 = An −(3, 1) = (2n+1 −2, 2n+1 −2n+1). For n ≥ 1, those edges of Sn , that are parallel with the main diagonal, consist of 2n+1 − 2 cells, and the other two edges consist of 2n cells. All ordinals (main and inner) have vertexes of coordinates mod 2 equal respectively with (1, 0), (0, 1), (1, 0), (0, 1). The main ordinals lie in the following environment: Between the main ordinals and the line y = 2 all cells are blue, excepting those that belong to the upper lattice, which are red. Between the main ordinals and the line x = 2, all cells are blue, excepting those that belong to the lower lattice, that are red. Consequently, all main ordinals are in increasing mood. For n ≥ 3, the first ordinal lying in Sn is a full copy by translation of Sn−2 (border and inner). It is followed successively by a full copy by translation of Sn−3 , a full copy by translation of Sn−4 , and so on, and finally a full copy by translation of S1 . All these direct subordinates of Sn lie in the following environment: The cells with y < x inside Sn and outside of those direct subordinates of Sn are blue, excepting the cells that belong to the lower (!) lattice, which are red. The cells with y > x inside Sn and outside of those direct subordinates of 19

Sn are blue, excepting the cells that belong to the upper (!) lattice, which are red. The exclamation marks emphasize here the fact that the situation is reversed: the upper lattice arises here below the main diagonal and the lower lattice arises here above the diagonal. Consequently, all the direct subordinates mentioned here are in decreasing mood. After the full copy by translation of S1 mentioned above, Sn contains (for n ≥ 3) a switching phase, consisting of a square with edges of length 2n − 3 consisting of blue cells, excepting those belonging to the central lattice, which are red. The edges are parallel with the axes, the main diagonal of the square lies on the main diagonal of the double sequence, and the four corners are red cells. Every edge of this square contains exactly n − 1 red cells. After the switching phase, Sn contains (for n ≥ 3) a full copy by translation of S1 , followed by a full copy by translation of S2 , and so on, and finally a full copy by translation of Sn−2 . All these direct subordinates of Sn lie in the following environment: The cells with y < x inside Sn and outside of those direct subordinates of Sn are blue, excepting the cells that belong to the upper (!) lattice, which are red. The cells with y > x inside Sn and outside of those direct subordinates of Sn are blue, excepting the cells that belong to the lower (!) lattice, which are red. The exclamation marks emphasize here the fact that the situation is reversed again: the upper lattice and the lower lattice have places which correspond again to their names. They have been switched by the switching phase. Consequently, all the direct subordinates mentioned here are in increasing mood. For n = 2k + 1 ∈ N, Sn starts with k many opening boxes followed by a full copy by translation of S1 , respectively ends with a full copy by translation of S1 followed by k many closing boxes. For n = 2k, k ≥ 1, Sn starts with k many opening boxes followed by a full copy by translation of S2 , respectively ends with a full copy by translation of S2 followed by k many closing boxes. If S1 is interpreted as ∅1 and S2 is interpreted as ∅2 , where ∅1 and ∅2 are the two initial symbols used to define the respective sequence of finite mirrored ordinals (sn ), then the sequences (Sn ) and (sn ) are isomorphic both as sequences of sets and sequences of words. Here the ∈-relation (according to the interpretation of sn as sets) is simulated by the relation of direct subordination between inner ordinals or inner and principal. The mirroring graphic line in the middle (according to the interpretation of sn as expressions) is simulated by the switching phases in inner and principal ordinals.

There are two key configurations that must be understood in order to prove these statements. First of all, one must understand the transition squares between ordinals. There are four types of such transition squares: the increasing transition from an odd ordinal to an even ordinal, the increasing transition from an even ordinal to an odd ordinal, the decreasing transition from odd to even and finally the decreasing transition from even to odd. Of course, one must also understand the switching phases in both even ad odd ordinals, although switching phases in odd and even are not really different. The induction starts with two special cases: S1 and S2 , two ordinals that do not contain inner ordinals, and correspond to the initial symbols when constructing the ordinal sequence. S1 has no transition phase at all. S2 has a minimal transition phase, containing one red cell that belongs to the central lattice. As will be seen later, transition phases are always started and closed by two red three-cell rectangular configurations. This is already the case in S2 . We start with the increasing transition square from even to odd. It is illustrated in Figure 22 by the transition square from S6 to S7 . In general the transition square from S2k to S2k+1 is a square of edge length 2k + 3. Seen from the left upper corner, it starts with a blue cell surrounded by the red three-cell rectangular configuration that closes the switching phase in the last copy 20

Figure 21: The principal ordinal S6 . of S2 arising in S2k according to the hypothesis and to Lemma 6.3. This generates a first white line, parallel to the second diagonal of the square, consisting of 4 white cells. This is the closing short edge of the copy of S2 in which the square started. This edge produces a repetitive red-blue pattern, consisting of a red stair with steps of length and heights of 3 cells. The stair produces the next white line parallel to the second diagonal of the square, consisting of 8 cells. This is the closing edge of the last copy of S4 arising in S2k , whose direct subordinate was the copy of S2 mentioned above. This continues in this way, and closing edges of all even ordinals at the end of S2k are produced. They contain respectively 4, 8, 12, . . . , 4k cells. At this moment we observe that S2k was in increasing mood, and this means that the upper and the lower lattices touched last time S2k in odd positions (and not on the vertex cells!). Consequently, the next white edge produced consists of 4k + 2 cells and is the first edge of the ordinal S2k+1 , that starts here. The square continues by producing edges consisting of 4k − 2, 4k − 6, . . . , 6, 2 cells. This last edge corresponds to the first copy of S1 arising in S2k+2 . We finally observe that all inner ordinals started now are in decreasing mood, while S2k+1 itself is in increasing mood. The last right lower cell of the square is the interior blue cell of the last copy of S1 just produced. The increasing transition square from even to odd can be described as follows: it starts on the principal diagonal of the sequence and has edge length 2k + 3. All vertex cells are blue. The initial edges are colored with the period blue, red, blue, white. The final edges are colored with the period blue, white, blue, red. Corresponding white cells on the two initial edges (on the two final edges) are linked with diagonal white segments. Corresponding red cells on the two initial edges (on the two final edges) are linked by stairs with steps of lengths 2, 3, 3, . . . , 3, 2 - but those red

21

stairs that start on the initial edges have second steps going backward and the remaining stairs have second steps going forward. All other cells inside the square are blue.

Figure 22: The increasing transition square from S6 to S7 .

Now on the increasing transition square from odd to even. It is illustrated in Figure 23 by the transition square from S7 to S8 . In general the transition square from S2k−1 to S2k is a square of edge length 2k + 1. Seen from the left upper corner, it starts with a blue cell surrounded by the white short edge consisting of 2 cells that closes the last copy of S1 arising in S2k−1 according to the hypothesis and to Lemma 6.3. The white edges continue arising, containing respectively 6, 10, . . . , 4k − 2 many cells. At this moment we observe that S2k−1 was in increasing mood, and this means that the upper and the lower lattices touched last time S2k−1 in odd positions (and not on the vertex cells!). Consequently, the next white edge produced consists of 4k cells and is the first edge of the ordinal S2k , that starts here. The square continues by producing edges consisting of 4k − 4, 4k − 8, . . . , 4 cells. This last edge corresponds to the first copy of S2 arising in S2k . We finally observe that all inner ordinals started now are in decreasing mood, while S2k itself is in increasing mood. The last right lower cell of the square is the blue cell surrounded by the red three-cell rectangular configuration that starts the switching phase in the last copy of S2 just produced. The increasing transition square from odd to even can be described as follows: it starts on the principal diagonal of the sequence and has edge length 2k + 1. All vertex cells are blue. The initial edges are colored with the period blue, white, blue, red. The final edges are colored with the (this time the same!) period blue, white, blue, red. Corresponding white cells on the two initial edges (on the two final edges) are linked with diagonal white segments. Corresponding red cells on the two initial edges (on the two final edges) are linked by stairs with steps of lengths 2, 3, 3, . . . , 3, 2 - but those red stairs that start on the initial edges have second steps going backward and the remaining stairs have second steps going forward. All other cells inside the square are blue.

The decreasing transition squares from a copy of Sn to a copy of Sn−1 are quite similar with the increasing transition squares, but the presence of a red cell on the both sides of the short edge of Sn forces the corresponding squares to be smaller with 2 units. We have called this phenomenon decreasing mood of the copy of Sn . In Figure 24 we illustrate the decreasing transition square from a full copy of S2k+1 to a full copy of S2k . This is a square of edge length 2k + 1. It contains white diagonal segments consisting of 22

Figure 23: The increasing transition square from S7 to S8 . 2, 6, . . . , 4k + 2, 4k, 4k − 4, . . . , 4 cells. All vertex cells are blue. The initial edges are colored with the period blue, white, blue, red. The final edges are colored with the period blue, red, blue, white.

Figure 24: The decreasing transition square from a full copy of S7 to a full copy of S6 inside S8 .

In Figure 25 we illustrate the decreasing transition square from a full copy of S2k to a full copy of S2k−1 . This is a square of edge length 2k + 1. It contains white diagonal segments consisting of 4, 8, . . . , 4k, 4k − 2, 4k − 6, . . . , 2 cells. All vertex cells are blue. The initial edges are colored with the period blue, red, blue, white, and the final edges are colored with the period blue, red, blue, white also. I found also three-valued recurrent 2-dimensional sequences encoding ordinals with three initial letters, but still no such sequence encoding the classical ordinals, with one initial letter. However I believe that this sequence exists and is waiting for us to discover it.

23

Figure 25: The decreasing transition square from a full copy of S8 to a full copy of S7 inside S9 .

References [1] J.-P. Allouche, J. Shallit: Automatic sequences - theory, applications, generalizations. Cambridge University Press, 2003. [2] Jean-Francois Bertazzon: Resolution of an integral equation with the Thue-Morse sequence. Indagationes Mathematicae 23, 327 - 336, 2012. [3] Georg Cantor Beitrage zur Begr¨ undung der transfiniten Mengenlehre II Mathematische Annalen 49, 207-246, 1897. [4] Alan Cobham: Uniform tag sequences. Mathematical Systems Theory, 6, 164 - 192, 1972. [5] G. Christol, T. Kamae, M. Mend` es France and G. Rauzy: Suites algebriques, automates et substitutions. Bull. Soc. Math. France, 108, 401419, 1980. [6] Benoˆıt B. Mandelbrot: The Fractal Geometry of Nature. W. H. Freeman and Company, San Francisco, 1982. [7] R. V. Moody (editor): The Mathematics of Aperiodic Order. Proceedings of the NATO Advanced Study Institute on Long Range Aperiodic Order. Kluwer Academic Publishings, 1997. [8] Mihai Prunescu: An undecidable properties of recurrent double sequences. Notre Dame Journal of Formal Logic, 49, 2, 143 - 151, 2008. [9] Mihai Prunescu: Self-similar carpets over finite fields. European Journal of Combinatorics, 30, 4, 866 - 878, 2009. [10] Mihai Prunescu: Recurrent double sequences that can be generated by context-free substitutions. Fractals, 18, 1, 65 - 73, 2010. [11] Mihai Prunescu: Recurrent two-dimensional sequences generated by homomorphisms of finite abelian p-groups with periodic initial conditions. Fractals, 19, 4, 431 - 442, 2011. [12] Mihai Prunescu: Linear recurrent double sequences with constant border in M2 (F2 ) are classified according to their geometric content. Symmetry, 3, 3, 402 - 442, 2011. [13] Mihai Prunescu: The Thue-Morse-Pascal double sequence and similar structures. Comptes Rendus - Math´ematique 349, 939-942, 2011. 24

[14] Mihai Prunescu: Fp -affine recurrent n-dimensional sequences over Fq are p-automatic. European Journal of Combinatorics 34, 260 - 284, 2013. [15] Mihai Prunescu: A two-valued recurrent double sequence that is not automatic. Theoretical Computer Science, 528, 32 - 39, 2014. [16] Eric Rowland, Reem Yassawi: A characterization of p-automatic sequences as columns of linear cellular automata. http://arxiv.org/abs/1209.6008 [17] Olivier Salon: Suites automatiques ` a multi-indices. S´eminaire de Th´eorie des Nombres de Bordeaux, Expos´e 4, (1986 - 1987), 4-01-4-27; followed by an Appendix by J. Shallit, 4-29A-4-36A. [18] Olivier Salon: Suites automatiques ` a multi-indices et alg´ebricit´e. Comptes Rendus de l’Acad´emie des Sciences de Paris, S´erie I, 305, 501 - 504, 1987. [19] M. K. Weir, A. P. Wale: Revealing non-analytic kinematic shifts in smooth goal-directed behaviour. Biological cybernetics 105, 89 - 119, 2011. [20] Alfred tarski, Andrzej Mostowski, Raphael M. Robinson: Undecidable Theories. North-Holland Publising Company, 1971. [21] Stephen Wolfram: A new kind of science. Wolfram Media Inc. 2002.

25