Amelia Carolina Sparavigna

Lidia Dastrù

The Sunlight and the Hidden Paintings in the Church of San Lorenzo in Torino

Keywords: Architecture, Archaeostronomy, Photographer's Ephemeris Software

The Real Chiesa di San Lorenzo is a church designed and built by Guarino Guarini. This church, adjacent to the Royal Palace in Piazza Castello, is one of the most beautiful churches in Torino. It possesses a remarkable cupola, made by a series of nested octagons. The lower part of the church has no windows. The natural light is coming from large windows above the base of the dome and other smaller openings in it. Besides the high altar, we find in the church two lateral altars and four radial chapels. In the chapels, Guarino Guarini has hidden some paintings inside their double vaults. These paintings are visible only when the sunlight is passing through a specific oculus in the front of the chapel. This happens when the sun has the right azimuth and altitude. Actually, the architect had used his knowledge of astronomy and geometrical optics to create this effect. Here we discuss it and the required position of the sun, using software for evaluating solar altitude and azimuth.

In several publications, we find discussed the astronomical orientations of churches and cathedrals and the possible alignments of them along the directions of sunrise [START_REF] Heilbron | The sun in the church: cathedrals as solar observatories[END_REF][START_REF] Abril | Evidence of Churches Aligned to the Sun on the Patron Saint's Day in Southern Spain after the Twelfth Century[END_REF][START_REF] Liritzis | Does sunrise day correlate with eastern orientation of byzantine churches on significant solar dates and saint's days? A preliminary study[END_REF][START_REF] Hinton | Church alignment and patronal saint's days[END_REF][START_REF] Caval | Astronomical orientations of Sacred Architecture during the Medieval period in Slovenia[END_REF][START_REF] Ali | The orientation of churches: some new evidence[END_REF][START_REF] Ali | The Church East and West: Orienting the Queen Anne Churches, 1711-34[END_REF][START_REF] Hoare | The orientation of early medieval churches in England[END_REF][START_REF] Hinton | Aspects of the alignment and location of medieval rural churches[END_REF][START_REF] Sassin Allen | Church Orientation in the Landscape: a Perspective from Medieval Wales[END_REF][START_REF] Mccluskey | Orientation of Christian Churches[END_REF][START_REF] Hutton | The stations of the sun: a history of the ritual year in Britain[END_REF][START_REF] Dallas | On the Orientation of Byzantine Churches in Thessalonike[END_REF][START_REF] Frincu | Astronomical Alignments of Paleo-Christian Basilicas in Romania[END_REF][START_REF] Gangui | Archaeoastronomy and the orientation of old churches[END_REF][START_REF] Spinazzè | The alignment of medieval churches in northern-central Italy and in the Alps and the path of light inside the chrch on the patron saint's day[END_REF][START_REF] Gangui | The orientation as a signature of cultural identity: The historic churches of Lanzarote[END_REF][START_REF] Sparavigna | Ad Orientem: the Orientation of Gothic Cathedrals of France[END_REF][START_REF] Sparavigna | The Solar Orientation of the Gothic Cathedrals of France[END_REF]. However, religious buildings can be linked to the sunlight by other optical effects, and these effects that can be evidenced by some research work, such as in [START_REF] Benfer | Light beams and architecture marked celestial events in colonial churches and missions in New Spain and Peru: New evidence from Morelia[END_REF][START_REF] Sparavigna | Light and Shadows in Bernini's Oval of Saint Peter's Square[END_REF]. Here, we consider an example that we can find in a church designed by Guarino Guarini (1624Guarini ( -1683)). This church, adjacent to the Royal Palace in Piazza Castello, is one of the most beautiful churches in Torino. It is the Real Chiesa di San Lorenzo. Guarino Guarini started to build the church in 1668. The building was finished in 1687, after the death of the architect. In San Lorenzo, Guarini used his knowledges of astronomy and of the apparent motion of the sun, to enhance the role of the light in the building. In fact, this architect, who was a great innovator of the Baroque style, had a special attention to optical effects and to their related symbolisms [START_REF] Badillo | Ocularium Lucis: Light and Optical Theory in Guarino Guarini's Church of San Lorenzo[END_REF]. Let us also note that, besides a treatise on architecture that was published posthumously, Guarini wrote some works on natural philosophy, geometry and astronomy. For what concerns the geometry of its layout, the church of San Lorenzo is a square at the basement, which becomes an octagon inside the church at the level of the entablatures. Then the design becomes a Greek cross at the level of the pendentives of the cupola [START_REF] Vv | Wikipedia[END_REF]. The base of the cupola is circular in plan, but the cupola itself is a series of nested octagons. The dome "is supported by eight ribs forming a lattice similar to those found in mosques and Romanesque churches in Spain" [START_REF] Vv | Wikipedia[END_REF]. From the outside, the church and the cupola appear as in the Figure 1, whereas, on the inside, the cupola is as shown in the Figure 2. Actually, in the layout of this church, Guarini used a sequence of square, octagon and circle to represent the world and the heavens [START_REF] Mandelli | Disegnare il tempo e l'armonia: il disegno di architettura osservatorio nell[END_REF]. The lower part of the church has no windows. We find in it the high altar, two lateral altars and four radial chapels. The high altar, which is separated from the nave by an archway, receives natural light from a hidden smaller dome. Above the lower part of the church, some large windows exist (see again Figures 1 and2). As explained in [25], Guarini designed the plan of the lower part of the church (the octagon) as a metaphor of our earthly life. However, by means of its dome, the architect is remarking that God is offering us an opportunity of salvation: when we raise our eyes to see the light of the cupola, we raise our thoughts toward His Divine Light. Let us continue discussing the chapels. The radial chapels have an oculus which is placed in the front of them (see Figure 3). The chapels have a peculiarity. In their vault we can see a six-pointed star with another oculus at the center, a hole which seems totally useless (see Figure 4). But it is not so. As told in [26], there is a little secret in these chapels. Inside the vaults, which are double vaults, there are some hidden paintings visible only at certain conditions. The paintings are visible when the hole in front of the chapel is illuminated by the sunlight. This happens at given moments of the year and only under good weather conditions. In fact, besides being a genius of architecture, Guarino Guarini was also an astronomer, and in San Lorenzo he proved his geniality in linking the church to the apparent motion of the sun in the sky. To continue our discussion it is necessary to consider the plan of the church (Figure 5), in particular of the chapels, and give the name of them (Figure 6). Let us consider the oculus in the center of the six-pointed star of the Chapel of the Immacolata [27]. It is designed to remain in the dark and cannot be seen inside. But, about noon of a few days around the Spring and Autumn Equinoxes, the sunlight comes from one of the large windows and hits the oculus in front of the chapel. The secret fresco inside the double vault, that of God the Father blessing the world in His hand, becomes visible. Moreover, the appearance of another fresco occurs in the opposite chapel. "The reflection of the light also makes visible another fresco, diametrically opposite, above the altar of the Souls in Purgatory, with Jesus Christ in the act of Blessing" [27]. The same reference is telling that "In the early morning during the same periods of the year, the same effect can be seen above the other two lateral altars of the Nativity and the Crucifix" [27]. Actually, the phenomenon for these two chapels does not happen as described by [27], but in the afternoon of a few days in May and July. Therefore, let us study the two cases and given some data and dates for the phenomenon. We start from a detailed exam of the phenomenon for the Chapel of the Immacolata. First, what is the window through which the sunlight is passing to hit the oculus in the front of this chapel? To answer the question we can use a Guarini's drawing of San Lorenzo, that we can find in his book [START_REF] Guarini | Architettura civile[END_REF], here given in the Figure 7. From the drawing, we can see that the light, which hits the oculus of the chapel, is coming from one of the large windows in the cupola, and this can happen when the sun has an altitude of about 43°. Let us use software "The Photographer's Ephemeris" to see azimuth and altitude of the sun, on 20 March 2017, the Spring Equinox. This software gives azimuths of sun and moon on satellite images. The altitudes are given in a graph as a function of time. In the image (Figure 8), we see the directions of sunrise (thick yellow line) and sunset (orange thick line). The blue lines are corresponding to moonrise and moonset. The thin yellow line, which gives the direction of the sun at 11:38, is passing through one of the large windows. The pivot is coincident to the position of the oculus in the front of the chapel of Immacolata. It means that, if the altitude of the sun is close to the angle given in the Figure 7, the sun beam can reach the oculus and illuminate the hidden vault of the chapel. In the lower part of the image in the Figure 8, software is giving us the altitude of the sun. It is of about 43°, at 11:38. In this manner, we have analysed the phenomenon described in [27], and, by means of the software Photographer's Ephemeris, determined date, time, and required azimuth and altitude of the sun. To observe the phenomenon in the chapel of the Crucifix, we need to be in the same condition. That is, the oculus in the front of the chapel needs being reached by the sunlight passing through the opposite large window. And we need an altitude of the sun of 43°. Let us use again The Photographer's Ephemeris. After some simulations, we found the proper conditions on 12 May 2017 (see Figure 9). The phenomenon is possible at 16:30, therefore in the afternoon. We are in the same condition in the afternoon of July 25. We are planning to visit the church in different periods of the year to evidence the above-mentioned phenomena, linked to the hidden paintings in the chapels, and, possibly, to find other effects of the sunlight that Guarino Guarini had eventually hidden in his architecture. We can see a six-pointed star depicted on it with an oculus at the center, a hole which seems totally useless. As told in [26], there is a little secret here. Inside the double vault there is a hidden painting, visible only when the hole in front of the chapel is illuminated by the sun beams. This happens at specific moments of the year and only under good weather conditions.

Figure 1 :

 1 Figure 1: Guarino Guarini's San Lorenzo in the images from Google Earth.

Figure 2 :

 2 Figure 2: The cupola of San Lorenzo.

Figure 3 .

 3 Figure 3. One of the radial chapels in San Lorenzo. Note the oculus in the front of the chapel.

Figure 4 :

 4 Figure 4: Detail of the vault of the chapel shown in the Figure3. Let us remark that the chapel has a double vault. We can see a six-pointed star depicted on it with an oculus at the center, a hole which seems totally useless. As told in[26], there is a little secret here. Inside the double vault there is a hidden painting, visible only when the hole in front of the chapel is illuminated by the sun beams. This happens at specific moments of the year and only under good weather conditions.

Figure 5 :

 5 Figure 5: Plan of the church given on the satellite image.

Figure 6 :

 6 Figure 6: The radial chapels.

Figure 7 :

 7 Figure 7: To have the sunlight hitting the oculus of the chapel, the altitude of the sun must be of about 43°.

Figure 8 :

 8 Figure 8: To investigate the phenomenon in the chapel of the Immacolata, let us use software "The Photographer's Ephemeris". It allows us to see the direction of the sun on 20 March 2017, the Spring Equinox. In the image we see the directions of sunrise (thick yellow line) and sunset (orange thick line). The blue lines are corresponding to moonrise and moonset. The thin yellow line, whichgives the direction of the sun at 11:38, is passing through one of the large windows. The pivot is coincident to the position of the oculus in the front of the chapel of Immacolata. It means that, if the altitude of the sun is close to the angle given in the Figure7, the sun beam can reach the oculus and illuminate the hidden vault of the chapel. In the lower part of the image, software is giving us the altitude of the sun. It is of about 43°. So the phenomenon is possible. Of course, the same is true for the Autumn Equinox.

Figure 9 :

 9 Figure 9: To investigate the phenomenon in the chapel of the Crucifix, let us use again software "The Photographer's Ephemeris". After some simulations, we found the proper condition on 12 May 2017. The pivot is coincident to the position of the oculus in the front of the chapel of the Crucifix. If the altitude of the sun is close to the angle of 43°, given in the Figure 7, the sun beams can reach the oculus and illuminate the hidden vault of the chapel. In the lower part of the image, software is giving us the altitude of the sun. It is of about 43°. So the phenomenon is possible at 16:30, therefore in the afternoon. We are in the same condition on July 25.


Amelia Carolina Sparavigna

The Zenith Passage of the Sun at the Mesoamerican Sites of Tula and Chichen Itza

Using software SunCalc.org we can easily observe the alignments of buildings along the direction of the sunset on the day of the zenith passage of the sun, at two Mesoamerican sites. These sites are those of Tula and Chichen Itza.

The tropics are the regions of the Earth that lie between the latitude lines of the Tropic of Cancer and the Tropic of Capricorn. In this zone of the Earth, we have the opportunity to see the zenith passage of the sun, that is, we can see the sun passing at noon directly overhead. The zenith passage happens on two days in the year. These days depend upon the latitude of the place of observation. Let us note that, at the Tropic of Cancer, the zenith passage happens on the day of the June solstice and at the Tropic of Capricorn on that of the December solstice; at the equator, the zenithal sun is observed on the two equinoxes.

When the sun passes overhead, the shadows of objects and persons disappear. As explained in [START_REF] Vv | Zenith Passage of the Sun[END_REF], the days when this happens assume a sacred significance for the people that live and lived within the tropics. "A number of legends identify it as a time when the way is open into the upper world" [START_REF] Vv | Zenith Passage of the Sun[END_REF]. In some Guatemalan villages, the two dates of zenith passage, which are coincident to the period of rains, are marked by ancient rituals. Also in ancient Hawai'i -Ref.1 explains -the zenith passage of the sun was a moment of great sacred power.

Being the zenith passage so important for people in the tropical zone [START_REF] Aveni | Skywatchers of Ancient Mexico, 2nd Edition[END_REF][START_REF] Aveni | The Observation of the Sun at the Times of Passage through the Zenith in Mesoamerica[END_REF][START_REF] Broda | Zenith Observations and the Conceptualization of Geographical Latitude in Ancient Mesoamerica: A Historical and Interdisciplinary Approach[END_REF][START_REF] Freidel | Maya Cosmos: Three Thousand Years on the Shaman's Path[END_REF][START_REF] Mendez | Centering the world: zenith and nadir passages at Palenque[END_REF][START_REF] Malmström | Cycles of the Sun, Mysteries of the Moon: The Calendar in Mesoamerican Civilization[END_REF][START_REF] Selin | Encyclopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures[END_REF], it is not surprising that we can find it evidenced by the local architectures too [START_REF] Aveni | The Observation of the Sun at the Times of Passage through the Zenith in Mesoamerica[END_REF][START_REF] Aveni | Chichen Itza's legacy in the astronomically oriented architecture of Mayapan[END_REF][START_REF] Barnhart | The Importance of Zenith Passage at Angkor, Cambodia[END_REF][START_REF] Šprajc | Astronomical Alignments in Río Bec Architecture[END_REF][START_REF] Aveni | On the orientation of precolumbian buildings in central Mexico[END_REF][START_REF] Aveni | Tropical archaeoastronomy[END_REF]. We have, for instance, that some monuments possess a "zenith tube" at their apex [START_REF] Barnhart | The Importance of Zenith Passage at Angkor, Cambodia[END_REF][START_REF] Sparavigna | The Zenith Passage of the Sun and the Architectures of the Tropical Zone[END_REF]. It is a vertical sighting tube inserted in the vault of the structure , which produces in a dark chamber a perfectly perpendicular beam of light when the sun is at the local zenith. Alignments of monuments are also possible: we observed them at Sanchi, India [START_REF] Kameswara Rao | History of Astronomy: Astronomy with Buddhist stupas of Sanchi[END_REF][START_REF] Sparavigna | On the alignment of Sanchi monuments[END_REF], at the Lion Rock in Sri Lanka [START_REF] Sparavigna | The Solar Orientation of the Lion Rock Complex in Sri Lanka[END_REF], at Angkor Wat [START_REF] Sparavigna | Solar Alignments of the Planning of Angkor Wat Temple Complex[END_REF] and at the Sewu, Prambanan and Borobudur Temples in Java [START_REF] Sparavigna | The Sewu Temple and the Zenithal Passage of the Sun[END_REF][START_REF] Sparavigna | A Short Note About the Zenithal Sun and the Sewu, Prambanan and Borobudur Temples in Java[END_REF].

Alignments of the monuments in the Mesoamerican site of Chichen Itza are well known [START_REF] Vv | Passage of the Sun[END_REF][START_REF] Mendez | Astronomical Observations from the Temple of the Sun[END_REF]. "El Castillo appears to be oriented so that the west plane of the pyramid faces the "Zenith passage" [START_REF] Vv | Passage of the Sun[END_REF]. Here we show this alignment using software SunCalc.org and satellite images. This software is an online application used to "to ascertain the sun movement with interactive map, sunrise, sunset, shadow length", and other data. About the use in archaeoastronomy for the simulation of shadows by means of SunCalc.org, we discussed in [START_REF] Sparavigna | The Role of the Shadows in a Bronze Age Stone Circle[END_REF] Before observing the alignment of El Castillo, let us consider the site of Tula. Here we show the alignment of the Palacio Quemado (the Burnt Palace) along the sunset on the day of the zenith passage of the sun. In this manner, we can add the site of Tula to the other sites where a worship of the zenithal sun existed.

The site of Tula. Tula was an important regional center, that became the capital of the Toltec Empire in the period between the fall of Teotihuacan and the rise of Tenochtitlan [START_REF] Vv | Tula (Mesoamerican site)[END_REF]. The site is close to the city of Tula de Allende. "The main attraction is the Pyramid of Quetzalcoatl which is topped by four, four metre high basalt columns carved in the shape of Toltec warriors … The feathered serpent god Quetzalcoatl is linked to this city, whose worship was widespread from central Mexico to Central America at the time the Spanish arrived" [START_REF] Vv | Tula (Mesoamerican site)[END_REF].

The pyramid of Quetzalcoatl is also known as the pyramid of the Morning Star [START_REF] Vv | Tula, The Temple Trail[END_REF]. The other main structures of the site include another pyramid, two Mesoamerican ballcourts and several large buildings. One of them is the Palacio Quemado (the Burnt Palace) [START_REF] Vv | Tula, The Temple Trail[END_REF]. If we used the SunCalc.org software, we can see that the Palacio Quemado has an orientation along the sunset on the two days of the zenith passage of the sun. The Figure 1 is a screenshot of the result given by the software. We see two lines giving the directions of sunrise and sunset. We have also the curve representing the apparent motion of the sun in the sky. When this line is passing through the site, it means that at noon the sun passes through the zenith. In the Figure 1, we can see that the sunset direction corresponds to the long axis of the Palace. Influence of Tula. In [START_REF] Vv | Tula (Mesoamerican site)[END_REF], we find mentioned that there is evidence of Tula influence in other parts of Mesoamerica [START_REF] Smith | Tula and Chichen Itza: Are we Asking the Right Questions?. Twin Tollans: Chichen Itza, Tula and the Epiclassic to Early Postclassic Mesoamerican World[END_REF]. "One of the most debated questions is what, if any, relationship there might be between Tula and Chichen Itza far to the south in the Yucatan Peninsula". This debate exists because there are similarities in various art and architectural styles. "It is certain that neither could have conquered the other, but there is evidence that they may have been connected through trade networks " [START_REF] Smith | Tula and Chichen Itza: Are we Asking the Right Questions?. Twin Tollans: Chichen Itza, Tula and the Epiclassic to Early Postclassic Mesoamerican World[END_REF]. Ref.24 tells also that the planning of Tula was adopted by some Aztec city-state rulers for their urban centers [START_REF] Smith | Tula and Chichen Itza: Are we Asking the Right Questions?. Twin Tollans: Chichen Itza, Tula and the Epiclassic to Early Postclassic Mesoamerican World[END_REF].

After observing the Figure 1, we can add the alignment along the sunset of the zenithal sun as a link to the architecture of Chichen Itza.

Chichen Itza. It was a large pre-Columbian city built by the Maya people. The archaeological site is located in the Yucatan. As told in [START_REF] Vv | Chichen Itza, in Wikipedia[END_REF], the site displays several architectural styles, "reminiscent of styles seen in central Mexico and of the Puuc and Chenes styles of the Northern Maya lowlands. The presence of central Mexican styles was once thought to have been representative of direct migration or even conquest from central Mexico, but most contemporary interpretations view the presence of these non-Maya styles more as the result of cultural diffusion" [START_REF] Vv | Chichen Itza, in Wikipedia[END_REF].

We have mentioned above one of the monuments of the site, El Castillo. It is the Temple of Kukulkan, a Maya deity represented as a feathered serpent similar to the Aztec Quetzalcoatl. It has the form of a step pyramid, consisting of a series of nine square terraces. This pyramid was superimposed to an old temple [START_REF] Vv | Chichen Itza, in Wikipedia[END_REF][START_REF] Willard | Kukulcan, the Bearded Conqueror : New Mayan Discoveries[END_REF]. In the Figure 2, we see a screenshot of software SunCalc.org. We see the alignment mentioned in [START_REF] Vv | Passage of the Sun[END_REF][START_REF] Mendez | Astronomical Observations from the Temple of the Sun[END_REF].

Conclusion.

Here we have shown the peculiar alignment of El Castillo at Chichen Itza using software SunCalc.org and satellite images. By means of this software, we can find that another Mesoamerican site, that of Tula, exists where a building is aligned along the sunset on the day of the zenith passage of the sun. This building is the Palacio Quemado. This reference to the zenithal sun is an architectural aspect which is notably linking the two Mesoamerican sites.

Figure 1 :

 1 Figure 1: Alignment of the Palacio Quemado (Tula) along the sunset on the day of the zenith passage of the sun.

Figure 2 :

 2 Figure 2: Alignment of El Castillo (Chichen Itza) along the sunset on the day of the zenith passage of the sun.

Information about this Article Published on Saturday 18th November, 2017 at 19:00:34.

The full citation for this


Pierre Gillibert

AN AUTOMATON GROUP WITH UNDECIDABLE ORDER AND ENGEL PROBLEMS

Keywords: Mathematics Subject Classification. 20F10. Secondary: 68Q80, 68Q05 Mealy automaton, automaton group, order problem, Engel problem, cellular automaton. 1

For every Turing machine, we construct an automaton group that simulates it. Precisely, starting from an initial configuration of the Turing machine, we explicitly construct an element of the group such that the Turing machine stops if, and only if, this element is of finite order. If the Turing machine is universal, the corresponding automaton group has an undecidable order problem. This solves a problem raised by Grigorchuk.

The above group also has an undecidable Engel problem: there is no algorithm that, given g, h in the group, decides whether there exists an integer n such that the n-iterated commutator [. . . [[g, h], h], . . . , h] is the identity or not. This solves a problem raised by Bartholdi.

Introduction

Our goal in this paper is to prove the following result, which answers questions raised by Grigorchuk, Nekrashevych, and Sushchanskiȋ in [START_REF] Grigorchuk | Automata, dynamical systems, and groups, Trudy Matematicheskogo Instituta Imeni[END_REF]Problem 7.2(a)] and [START_REF] Grigorchuk | Self-similarity and branching in group theory[END_REF]Problem 2(b)] Theorem 1.1. Recognizing in an automaton group whether an element is of finite order is an undecidable problem.

We also obtain a negative result for the Engel problem for such groups, raised by Bartholdi in [START_REF] Bartholdi | Algorithmic decidability of Engel's property for automaton groups[END_REF][START_REF] Bartholdi | Decidability problems in automaton semigroups[END_REF]: Theorem 1.2. Recognizing in an automaton group whether an n-iterated commutator [• • • [[v, w], w], . . . , w] is trivial for some n is an undecidable problem.

As an application of Theorem 1.1, we obtain a new example of a finitely presented group with decidable word problem and undecidable order problem (McCool's theorem [START_REF] Mccool | Unsolvable problems in groups with solvable word problem[END_REF]). Indeed, as an automaton group is finitely generated and has decidable word problem, it has a recursive presentation with a finite set of generators. It follows from Higman's representation theorem [START_REF] Higman | Subgroups of finitely presented groups[END_REF] that an automaton group can be embedded in a finitely presented group. Moreover, using Clapham's theorem [START_REF] Clapham | Finitely presented groups with word problems of arbitrary degrees of insolubility[END_REF], we can choose a finitely presented group with a decidable word problem. Hence our automaton group embeds in a finitely presented group with a decidable word problem and an undecidable order problem.

The principle of our proof. Our method is to show that an arbitrary cellular automaton can be simulated using a Mealy automaton. As all Turing machines can be simulated using cellular automata, we deduce, for every Turing machine M , a Mealy automaton that generates an automaton group G(M ), and we can prove that, for each word w there is a (computable) element g of G(M ) such that M stops on w if, and only if, g is of finite order (then a power of 2) in G(M ). As the halting problem is undecidable (Turing [55]), if M is a universal Turing machine, the order problem in the associated automaton group G(M ) is undecidable (Theorem 1.1). Moreover, there exists a special element h such that, for all possible elements g constructed above, we have [. . . , [[g, h], h], . . . , h] = g ±2 n (n commutators). It follows that the Engel problem for the group G(M ) is also undecidable (Theorem 1.2).

The principle for constructing the group G(M ) is as follows. First, we note that a Turing machine can be simulated using a cellular automaton. Call its alphabet T , and add a separator symbol $ and a counter on each symbols, that is, put Σ = (T ∪ {$}) × {0, 1}. For the moment, we skip the description of the state set. The point is that, for every w in T * , we can construct an element g of the automaton group with the following behavior. Set w 0 = w, and define inductively w k+1 as the finite configuration (increasing the length by one) obtained by applying one step of the cellular automaton to w k (completed with some default symbol). Consider the word w 0 $w 1 $ • • • and set the counters to zero, obtaining a word x in Σ ω . The construction of g is such that, when g is applied once to x, it only modifies the counters and keeps them synchronized. If we take any element y that is not in the gorbit of x, the counters are not synchronized, at least one letter is different, or one specific end-state appears. Then g, applied enough times, "finds" the difference and reverses the counter, so we obtain g 2 n (y) = y, for some n only depending on the position of the first discrepancy. The undecidability of the order problem follows.

The key point in our encoding is to ensure that updating once a configuration of the initial cellular automaton corresponds to squaring the associated element in the final group. This explains how elements whose order in the group is a high power of 2 arise, making the order problem of that group undecidable.

The general context. To give a general perspective, let us review some of the many known decidability and, mainly, undecidability results involving automata groups and semigroups. We recall that a Mealy automaton is an automaton with an additional output map. Each state of such an automaton gives rise to an endomorphism of the tree of all words in the involved alphabet. By definition, the (semi)group generated by such endomorphisms is an automaton (semi)group.

Automaton groups proved to be efficient tools for constructing counterexamples to various conjectures. Alešin in [START_REF] Alešin | Finite automata and the Burnside problem for periodic groups (Russian)[END_REF] gives an example of an infinite, finitely generated torsion group (Burnside group for short). Golod and Shafarevich already constructed a Burnside group in [START_REF] Golod | On nil-algebras and finitely approximable p-groups (Russian)[END_REF][START_REF] Golod | On the class field tower (Russian)[END_REF], however Alešin's group is much simpler, being a 2-generator subgroup of an automaton group. Similarly, using a Mealy automaton, Sushchanskiȋ [START_REF] Sushchanskiȋ | Periodic p-groups of permutations and the unrestricted Burnside problem (Russian)[END_REF] constructed for every prime p a Burnside p-group.

Grigorchuk gave another example of a Burnside 2-group in [START_REF] Grigorchuk | On Burnside's problem on periodic groups (Russian)[END_REF]; in this case, the group is the whole automaton group. This group has many remarkable properties. Grigorchuk proved in [START_REF] Grigorchuk | On the Milnor problem of group growth (Russian)[END_REF] that the group has intermediate growth (neither polynomial, nor exponential), solving a problem by Milnor [START_REF] Carlitz | Problems and Solutions: Advanced Problems: 5600-5609[END_REF]Problem 5603]. The group is also amenable but not elementary amenable, answering a question by Day [START_REF] Day | Amenable semigroups[END_REF]. Grigorchuk generalized his construction obtaining in [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means (Russian)[END_REF] and obtained p-groups with intermediate growth. We refer to Żuk in [START_REF] Żuk | Automata groups[END_REF] for further examples of interesting automaton groups, see also Brough and Cain [8,[START_REF] Brough | Automaton semigroups: new constructions results and examples of non-automaton semigroups[END_REF] for several examples of automaton semigroup constructions.

We proved in [START_REF] Gillibert | The finiteness problem for automaton semigroups is undecidable[END_REF] that the finiteness problem and the order problem for reset automaton semigroups are undecidable. Our proof consists in reducing the problems to the tiling problem by a NW-deterministic tile set, which is proved to be undecidable by Kari in [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF]. The encoding is such that any large product of generators either yields a (quasi) nilpotent element, or encodes a large tiling of the plane. Using similar techniques, we could encode the computation of an arbitrary one-way cellular automaton, see for example Delacourt and Ollinger [START_REF] Delacourt | Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups[END_REF].

Concerning the order problem, which we shall tackle below, and closely related problems, several undecidability results are known. Belk and Bleak constructed in [START_REF] Belk | Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V[END_REF] a group generated by an asynchronous automaton with an undecidable order problem. However, the construction relies on asynchronicity deeply (typically, at the expense of forgetting the first letter, one can simulates any reversible Turing machine).

Delacourt and Ollinger proved in [START_REF] Delacourt | Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups[END_REF] that the periodicity problem for onedimensional one-way cellular automata starting from a given initial almost constant configuration is undecidable. They also pointed that the uniform periodicity problem is equivalent to the finiteness problem for reset automaton groups, see also Silva and Steinberg [50,Theorem 4.2]. Kari and Ollinger proved in [START_REF] Kari | Periodicity and immortality in reversible computing[END_REF] that the periodicity problem for one-dimensional cellular automata is undecidable. We refer to Kari [START_REF] Kari | Theory of cellular automata: A survey[END_REF][START_REF] Kari | Decidability and undecidability in cellular automata[END_REF][START_REF] Kari | Tiling problem and undecidability in cellular automata[END_REF][START_REF] Kari | Cellular automata, tilings and (un)computability[END_REF] for more related results for cellular automata.

On the other hand, there are positive results. Bondarenko, Bondarenko, Sidki, and Zapata proved in [START_REF] Bondarenko | On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix[END_REF] that the order problem is solvable in bounded automaton groups.

For reversible Mealy automata, although the order problem was not solved so far, several positive results have been established. It is worth noting that all results mentioned in this paragraph are effective, thus providing decidability criteria. Klimann proved in [START_REF] Klimann | Automaton semigroups: the two-state case[END_REF] that an automaton semigroup generated by a 2-state reversible Mealy automaton is either finite or free. Godin, Klimann, and Picantin studied in [START_REF] Godin | On torsion-free semigroups generated by invertible reversible Mealy automata[END_REF] the torsion part of the automaton semigroup associated with an invertible reversible automaton. In particular an invertible reversible Mealy automaton with no bireversible component generates a torsion-free semigroup. Similarly Klimann, Picantin, and Savchuk gave in [START_REF] Klimann | Orbit automata as a new tool to attack the order problem in automaton groups[END_REF] a method to find elements of infinite order in some automaton groups. Finally, Godin and Klimann proved in [START_REF] Godin | Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups[END_REF] that a connected bireversible Mealy automaton of prime size generates either a finite group or a group with an element of infinite order, extending a result of Klimann, Picantin, and Savchuk in [START_REF] Klimann | A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group[END_REF].

Although the classes of reset and reversible Mealy automata are disjoint, some of their properties are similar. In particular, Olukoya proved in [START_REF] Olukoya | The growth rates of automaton groups generated by reset automata[END_REF] that an automaton group generated by a reset Mealy automaton is either finite or contains a free semigroup over two generators, and, therefore, it has exponential growth and contains an element of infinite order. However, it is not known whether those conditions are decidable for groups, and they are known to be undecidable for semigroups.

On the other hand, it is well known that the word problem is solvable for automaton groups. The argument relies on the Eilenberg's reduction algorithm of [START_REF] Eilenberg | Automata, languages, and machines[END_REF]Chapter XII]. Also see Steinberg [START_REF] Steinberg | On some algorithmic properties of finite state automorphisms of rooted trees[END_REF], D'Angeli, Rodaro, and Wächter [START_REF] Angeli | On the complexity of the word problem for automaton semigroups and automaton groups[END_REF] for more about the complexity of the word problem. For further decidability results, we refer to Akhavi, Klimann, Lombardy, Mairesse, and Picantin [START_REF] Akhavi | On the finiteness problem for automaton (semi)groups[END_REF], to Bartholdi [3], or to Grigorchuk and Šunić [START_REF] Grigorchuk | Self-similarity and branching in group theory[END_REF] for related questions. Furthermore, Šunić and Ventura constructed in [START_REF] Šunić | The conjugacy problem in automaton groups is not solvable[END_REF] an automaton group with undecidable conjugacy problem, and D'Angeli, Godin, Klimann, Picantin, and Rodaro proved in [START_REF] Angeli | Freeness of automaton groups vs boundary dynamics[END_REF][START_REF] Angeli | Boundary action of automaton groups without singular points and Wang tilings[END_REF] that the existence of non-elementary commuting pairs of elements is undecidable.

About this text. The constructions of this paper and the undecidability of the order problem for automaton groups were exposed in July 2017 at the MealyM Final Event [START_REF] Gillibert | Simulating Turing machines with invertible Mealy automata[END_REF]. After the first version of this paper was posted [START_REF] Gillibert | An automaton group with undecidable order and Engel problems[END_REF], Laurent Bartholdi and Ivan Mitrofanov announced another proof, extending the undecidability result to contracting groups generated by Mealy automata [START_REF] Bartholdi | The word and order problems for self-similar and automata groups[END_REF] and appealing to an encoding of Minsky machines. In this way, they deduce the undecidability of the word problem in self-similar groups.

On the other hand, in an ongoing work with Dmitri Savchuk, we use an encoding of cellular automaton similar to the one of the current paper to obtain a self-similar group with an undecidable word problem.

Acknowledgement. I thank Ines Klimann and Matthieu Picantin for helpful comments, suggestions, and corrections.

Basic concepts and notations

The three main decision problems investigated in this paper are:

Problem. Let G be a group, generated by a finite set Σ.

(1) Word problem: given a word w ∈ Σ * , does w represent the identity in G?

(2) Order problem: given a word w ∈ Σ * , does w represent an element of finite order in G? (3) Engel problem: given words v, w ∈ Σ * , does there exist n ≥ 1 such that the n-iterated commutator [. . . [[v, w], w], . . . , w], represents the identity in G?

Note that the decidability of the three problems does not depend on the choice of the generating set: if a problem is decidable for a generating set Σ, then it is also decidable for any other finite generating set. As mentioned by McCool in [START_REF] Mccool | The order problem and the power problem for free product sixth-groups[END_REF], if the order of an element can be computed, then the word problem is solvable. Conversely, if the order problem and the word problem are solvable, then the order can be computed.

When an alphabet is given, we generally use thin symbols a, b, p, q, x, y for the letters and bold symbols a, b, p, q, x, y for the words in the alphabet. We denote by Σ * the set of all words in the alphabet Σ.

A Mealy automaton is a tuple A = (A, Σ, δ, σ), where A and Σ are finite sets and δ : A × Σ → A and σ : A × Σ → Σ are maps. The elements of A are called the states of A, while Σ is the alphabet of A. The map δ is the transition map, and the map σ is the output map. We extend δ : A * × Σ * → A * , and σ : A * × Σ * → Σ * , using (2.1)-(2.4) inductively, where we put σ p (x) = σ(p, x), and δ x (p) = δ(p, x) for all p ∈ A * and x ∈ Σ * . Note that σ defines a right action of A * on Σ * . σ p (xy) = σ p (x)σ δx(p) (y) , for all x ∈ A * , p ∈ Σ * , and y ∈ Σ * .

(2.1)

δ x (pq) = δ x (p)δ σp(x) (q)
, for all x ∈ Σ * , p ∈ A * , and q ∈ A * .

(2.2)

σ pq = σ q • σ p , for all p, q ∈ A * . (2.
3)

δ xy = δ y • δ x , for all x, y ∈ Σ * . (2.4)
The semigroup generated by A is the subsemigroup of End Σ * generated by all σ p with p ∈ A. If all the maps σ p with p ∈ A are bijective, then the group generated by A is the subgroup of Aut Σ * generated by all σ p with p ∈ A. An automaton group is a group generated by a Mealy automaton.

In order to visualize the image of σ and δ, we use the notation of cross diagrams defined below. For all p, p ′ ∈ A * and all x, x ′ ∈ Σ * , we say that the following cross diagram holds x p / / p ′

x ′ if, and only if, x ′ = σ p (x) and p ′ = δ x (p). The equalities (2.1)-(2.4) are summarized in the following cross diagrams

x p / / δ x (p) σ p (x) q / / δ σp(x) (q) σ pq (x) x y p / / δ y (p) / / δ xy (p) σ p (x) σ δx(p) (y)
Given p, q ∈ A * , we write p ≡ q if, and only if, σ p = σ q . We write p ≡ id if, and only if, σ p is the identity.

Given a group G, and g, h in G, the commutator of g and h is [g, h] = g -1 h -1 gh. We say that (g, h) is an Engel pair if there exists an integer n ≥ 1 such that the n-iterated commutator [. . . [[g, h], h], . . . , h] is the identity.

Let m ≤ n be integers. A one-dimensional cellular automaton with neighborhood {m, m + 1, . . . , n -1, n} is a tuple (T, t), where T is a finite set and t : T m-n+1 → T is a partial map. We say that (T, t) is complete if t is defined everywhere. We call the element of T the states of the cellular automaton, we call t the transition map. A configuration of (T, t) is a map c : Z → T . Given a configuration c, the updated or next configuration is c ′ : Z → T , defined for all k ∈ Z by

c ′ (k) = t(c(k + m), c(k + m + 1), . . . , c(k + n -1), c(k + n -1)).
Due to the local nature of a Turing machine computation, for each Turing Machine M , we can construct a cellular automaton such that each configuration of M can be encoded in a configuration of the cellular automaton, and such that the processes of updating the configuration for M and for the cellular automaton coincide. We refer to the beginning of Section 6 for references.

Unless otherwise specified, a cellular automaton is a one-dimensional complete cellular automaton with neighborhood {-1, 0, 1}. Consider a cellular automaton (T, t), with a distinguished default state e ∈ T , and a set of final states F ⊆ T . A finite configuration of (T, t) is a word a = a 1 . . . a n ∈ T * . To update a finite configuration, we first pad the configuration with the symbol e, update the configuration as an infinite configuration, then restrict the result to a finite configuration. The exact definition is:

Notation 2.1. Let a = a 1 . . . a n ∈ T * be a finite configuration. Set a 0 = a n+1 = a n+2 = e. For all 1 ≤ k ≤ n + 1 set b k = t(a k-1 , a k , a k+1 ). The updated or next configuration is τ (a) = b 1 . . . b n b n+1 .
This construction is easier to understand in terms of Turing machines. Every configuration of a Turing machine only needs a finite tape, but, as the computation goes on, the amount of required memory increases. The right-left asymmetry in the definition corresponds to Turing machine working on a one-way infinite tape.

A cellular automaton halts from the finite initial configuration a = a 1 . . . a n if there exists k ∈ N such that a symbol of F appears in τ k (a). It is known that there exists a universal cellular automaton for which the halting problem, from a given finite configuration, is undecidable. We give an example of a universal cellular automaton in Section 6.

Simulating Cellular Automata

Starting from a cellular automaton, we construct a Mealy automaton simulating transitions between finite configurations. In this section we only give the construction, a few basic properties, and the main tool needed to construct elements of the group simulating the cellular automaton.

Fix a cellular automaton (T, t), where t :

T 3 → T . Fix e ∈ T and F ⊆ T . Take a symbol $ which is not in T . Set T ′ = T ∪ {$}.
The state e should be understood as the blank or default state (i.e. finite configurations of the cellular automaton are completed with this state). The states of F should be understood as final states.

Let C, W, P , and ¬ be new symbols. Consider the Mealy automaton which has alphabet Σ = T ′ × {0, 1}, and state set

A = {¬} ∪ ({C} × T × T ′ ) ∪ ({W } × T × T ) ∪ ({P } × T )
The states in {C}×T ×T ′ are called counting states. A modifying state is a state which is either ¬ or a counting state. Thus, each counting state is a modifying state and ¬ is the only modifying non-counting state, all other states are non-modifying (and thus also non-counting). We put

C b a = (C, a, b) ∈ {C} × T × T ′ , and, similarly, W b a = (W, a, b) ∈ {W } × T × T , and P a = (P, a) ∈ {P } × T . Define ⊥ : Σ → Σ by x = (a, ε) → x ⊥ = (a, 1 -ε).
So, we have (a, 0) ⊥ = (a, 1), and (a, 1) ⊥ = (a, 0). In particular, the map ⊥ defines a bijection. Consider now the map σ :

A × Σ → Σ defined by (s, x) → x ⊥ , if s is a modifying state.
x , otherwise.

All modifying states have the same action on one letter (exchanging 0 and 1). All non-modifying states act like identity on one letter.

Next, define δ : A × Σ → A, for all (p, x) ∈ A × Σ, all a ∈ T , all b, d ∈ T ′ , and all ε ∈ {0, 1}, in the following way, where we agree that (3.1) has priority over all other clauses when it applies: We extend σ :

δ(p, x) =                                              ¬ if p = ¬ or x ∈ F × {0, 1}. ( 3
A * × Σ * → Σ * and δ : A * × Σ * → A * using (2.1)-(2.4
). Herafter, and in the rest of the paper, we denote by A = (A, Σ, δ, σ) the Mealy automaton we are constructing, and by G the associated automaton group

The name counting state can be understood when we look at the action on a word. In a "generic everything is working case", a counting state simply adds 1 in binary, of course depending on the control character the action will be different. The only modifying non-counting state is ¬, which acts like a negation (keeps exchanging 0 and 1 for the whole word). A non-modifying state does not change the word, until it reads some specific control character. As ⊥ is an involution, the action of a word in A * on a single letter in Σ is straightforward to describe. Lemma 3.2. For p ∈ A * and x ∈ Σ, the equality σ p (x) = x ⊥ holds if, and only if, the number of modifying states in p is odd.

) If p is not in {C} × T × {$}, then δ x (p) is not in {C} × T × {$}. See (3.1), ( 6
The following lemma illustrates how ¬ reverses the simulation. Lemma 3.3. For every p ∈ A, we have p¬p ≡ ¬.

Proof. Let p ∈ A and x ∈ Σ. Note that, in p¬p, the number of modifying states is odd, hence Lemma 3.2 implies σ p¬p (x) = x ⊥ = σ ¬ (x).

Assume there exists an integer n such that σ p¬p (x) = σ ¬ (x) for all x ∈ Σ n and all p ∈ A.

Let p ∈ A. Let x ∈ Σ and y ∈ Σ n . Assume that p is not a modifying state. Therefore, by Remark 3.1(1), the following equalities hold

δ x (p¬p) = δ x (p)δ σp(x) (¬p) = δ x (p)δ x (¬p) = δ x (p)¬δ x ⊥ (p) = δ x (p)¬δ x (p) .
On the other hand, if p is a modifying state, we find

δ x (p¬p) = δ x (p)δ σp(x) (¬p) = δ x (p)δ x ⊥ (¬p) = δ x (p)¬δ σ¬(x ⊥ ) (p) = δ x (p)¬δ x (p) .
Therefore, in both cases, we have δ x (p¬p) = δ x (p)¬δ x (p). Thus the following equalities hold

σ p¬p (xy) = σ p¬p (x)σ δx(p¬p) (y) = σ ¬ (x)σ δx (p)¬δx(p) (y) = σ ¬ (x)σ ¬ (y) = σ ¬ (xy) .
The result then follows using an induction.

As an immediate consequence of Lemma 3.3, we obtain the following description of inverses.

Corollary 3.4. Let p ∈ A * be a palindrome. Then the inverse of σ p is σ ¬p¬ .

Furthermore, we obtain a connection between commutators and powers. Corollary 3.5. Let p, q be palindromes in A * . Let n ≥ 1 be an integer. Then [. . . [[σ pq , σ ¬q ], σ ¬q ], . . . , σ ¬q ] ≡ (σ pq ) (-2) n , where there are n commutators.

Proof. Let k be an integer. The following equalities hold

[σ k pq , σ ¬q ] = σ -k pq • σ -1 ¬q • σ k pq • σ ¬q = σ -k pq • (σ q • σ ¬ ) -1 • (σ q • σ p ) k • σ q • σ ¬ , by (2.3). = σ -k pq • σ ¬ • σ -1 q • (σ q • σ p ) k • σ q • σ ¬ , as σ ¬ = σ -1 ¬ . = σ -k pq • σ ¬ • (σ p • σ q ) k • σ ¬ = σ -k pq • (σ ¬ • σ p • σ ¬ • σ ¬ • σ q • σ ¬ ) k , as σ ¬ = σ -1 ¬ . = σ -k pq • (σ -1 p • σ -1 q ) k , by Corollary 3.4. = σ -k pq • (σ q • σ p ) -k = σ -k pq • σ -k pq , by (2.3). = σ -2k pq
The result follows using an induction.

We now fix some notation for various words that will be used many times in the sequel. Notation 3.6. We define Q : A * → A * , inductively by Q(p) = p, and Q(qp) = Q(q)pQ(q) where q ∈ A * and p ∈ A.

Given a ∈ T , we set C(a) = C a e . We extend the notation to all words a = a

1 . . . a n in T * by C(a 1 a 2 . . . a n ) = C(a 1 )C(a 2 ) . . . C(a n ). Set Z(a 1 a 2 . . . a n , ε) = (a 1 , ε)(a 2 , ε) . . . (a n , ε) Set P (a 1 a 2 . . . a n ) = P a1 P a2 . . . P an . Note that the definition of Q is equivalent to putting Q(p 1 . . . p n ) = p i1 p i2 . . . p i 2 m -1
, where i k is the position of the first 0 that turns to 1 when one goes from k -1 to k in binary, assuming that the digit with lowest weight is on the left. Equivalently, i k corresponds to the position where the carry is cleared when adding 1. For instance, counting 000, 100, 010, 110, 001, 101, 011, 111, we find Q(p 1 p 2 p 3 ) = p 1 p 2 p 1 p 3 p 1 p 2 p 1 . This definition is not essential in the paper, but it might help to understand the way counters work, and the construction of our elements in the group.

We obtain a short description of the inverse of Q(p).

Lemma 3.7. For every p ∈ A * , we have

Q(p¬) = Q(p)¬Q(p) ≡ ¬.
Proof. The result follows from Lemma 3.3 and Q(p) being a palindrome.

Definition 3.8. A word p ∈ A * is regular if we can write p = qr where r has only modifying states and q has only non-counting states. The potential of p is ∞ if ¬ appears in r, otherwise the potential of p is the length of r.

If we assume that q does not end with ¬, then a decomposition p = qr as above is unique.

For each word x, we now introduce a map ρ x on the set of regular words. Let p = p 1 . . . p m+n be a regular word, such that p 1 . . . p m are non-counting states, p m = ¬, and p m+1 . . . p m+n are modifying states. For x in Σ, we set

ρ x (p) = ρ x (p) = δ x (p 1 )δ x (p 2 ) . . . δ x (p m ) for n = 0, δ x (p 1 )δ x (p 2 ) . . . δ x (p m )δ x (p m+1 )δ x ⊥ (p m+2 ) . . . δ x ⊥ (p m+n ) for n ≥ 1.
Then, for x = x 1 . . . x k in Σ * , we set

ρ x = ρ x k • ρ x k-1 • • • • • ρ x1 .
We give a few basic properties of regular words and of ρ.

Lemma 3.9. Let p ∈ A * and q ∈ A. Then the following statements hold.

(1) If p is regular with potential zero, then pq is regular, and

ρ x (pq) = ρ x (p)δ x (q) .
(

) 2
If p is regular with potential at least one, and q ∈ A is modifying, then pq is regular with potential at least two, and

ρ x (pq) = ρ x (p)δ x ⊥ (q) . ( 3
)
If p is regular with potential zero and a ∈ T \ F , then ρ (a,0) (p) is regular with potential zero.

Proof. Points (1) and ( 2) are direct consequences of the definition of ρ x . Assume that p = p 1 . . . p n has potential zero, hence p n is a non-modifying state and p 1 . . . p n-1 are non-counting states. Let a ∈ T \ F . We have

ρ (a,0) (p) = δ (a,0) (p 1 ) . . . δ (a,0) (p n ).
From Remark 3.1(2), δ (a,0) (p 1 ) . . . δ (a,0) (p n-1 ) are non-counting and, by Remark 3.1(5), the state δ (a,0) (p n ) is non-modifying, hence ρ (a,0) (p) is regular with potential zero.

We now describe the action of Q(p) on a single letter. Lemma 3.10. Let p ∈ A * of length at least one, and We can now specify the cross diagram of a regular word with potential zero completely.

x ∈ Σ. Then σ Q(p) (x) = x ⊥ if,
Lemma 3.11. Let p = p 1 . . . p m ∈ A * , be without counting states. Let x ∈ Σ. Then the following statements hold.

(1)

δ x ⊥ (p) = δ x (p) = δ x (p 1 )δ x (p 2 ) . . . δ x (p m ) = ρ x (p) = ρ x ⊥ (p). ( 2
) If x ∈ T × {0, 1}, then there is no counting state in δ x (p). ( 3
) δ x (Q(p)) = δ x ⊥ (Q(p)) = Q(ρ x (p)).
If p is a regular word with potential zero, then we have the following cross diagram

x Q(p) / / Q(ρ x (p))
x (3.12)

Proof. Let x ∈ Σ. As observed in Remark 3.1(1), we have δ x (p) = δ x ⊥ (p) for every non-counting state p. Ttherefore, for every p = p 1 . . . p m without counting states, we have

δ x (p 1 ) . . . δ x (p m ) = δ x ⊥ (p 1 ) . . . δ x ⊥ (p m ) = ρ x (p 1 . . . p m ) = ρ x ⊥ (p 1 . . . p m ) .
Assume that (1) holds for a given p = p 1 . . . p m . Let q ∈ A be a non-counting state. Either q = ¬, then σ q (x) = x ⊥ , or q is not modifying, then σ q (x) = x. In both cases, we find δ σq (x) (p) = δ x (p). Therefore, the following equalities hold δ x (qp) = δ x (q)δ σq (x) (p) = δ x (q)δ x (p) = δ x (q)δ x (p 1 )δ x (p 2 ) . . . δ x (p m ) .

Moreover, we have δ x (q) = δ x ⊥ (q), hence

δ x ⊥ (qp) = δ x ⊥ (q)δ σq (x ⊥ ) (p) = δ x (q)δ x (p 1 )δ x (p 2 ) . . . δ x (p m ) .
Therefore, we find

δ x ⊥ (qp) = δ x (qp) = δ x (q)δ x (p 1 ) . . . δ x (p m ) .
Then, (1) follows using an induction.

Assume that x ∈ T × {0, 1}. Note that δ x (p) = δ x (p 1 ) . . . δ x (p m ). So, using Remark 3.1(2), we see that no state in δ x (p) is counting, thus (2) holds.

Assume that δ x (Q(p)) = Q(ρ x (p)) for some p. Let q ∈ A be a non-counting state. The following equalities hold

δ x (Q(pq)) = δ x (Q(p)qQ(p)) by definition of Q, = δ x (Q(p))δ x (q)δ x (Q(p)) by (1) for the word Q(p)qQ(p), = Q(ρ x (p))δ x (q)Q(ρ x (p)) by induction hypothesis, = Q(ρ x (p)δ x (q)) by definition of Q, = Q(ρ x (pq)) by definition of ρ x .
Statement (3) follows using an induction. If p is regular with potential zero, then the last letter of p is non-modifying. Then, Lemma 3.10 implies that σ Q(p) (x) = x, hence the cross diagram is as indicated in (3.12).

We now show that the action of ρ (a,0) on a regular word either reduces the potential by one, or it turns the latter to ∞. Lemma 3.12. Let p ∈ A * be a regular word with potential n ≥ 1. Let a ∈ T . Then ρ (a,0) (p) is regular with potential either n -1 or ∞.

Proof. Write p = p 1 . . . p m . Pick k such that p 1 . . . p k are not counting, p k = ¬, and p k+1 . . . p m are modifying. The following equality holds

ρ (a,0) (p) = δ (a,0) (p 1 ) . . . δ (a,0) (p k )δ (a,0) (p k+1 )δ (a,1) (p k+2 ) . . . δ (a,1) (p m ) .
By Remark 3.1(3), the states δ (a,0) (p 1 ) . . . δ (a,0) (p k )δ (a,0) (p k+1 ) are not counting. By Remark 3.1(4), the states δ (a,1) (p k+2 ) . . . δ (a,1) (p m ) are modifying, hence ρ (a,0) (p) is regular. If δ (a,0) (p k+1 ) = ¬, then ρ (a,0) (p) is regular with potential ∞. Similarly, if some letter in δ (a,1) (p k+2 ) . . . δ (a,1) (p m ) is ¬, then ρ (a,0) (p) has potential ∞.

Assume that δ (a,0) (p k+1 ) = ¬, and that no letter in δ (a,1) (p k+2 ) . . . δ (a,1) (p m ) is ¬. Thus ρ (a,0) (p) is regular with potential mk -1. We note that there is no letter ¬ in p k+1 . . . p m . Hence the potential of p is n = mk, and the potential of

ρ (a,0) (p) is m -k -1 = n -1.
We can now specify the cross diagram of a regular word with potential at least one completely. Proof. Let q ∈ A * be a regular word with potential zero. Let p ∈ A be a modifying state. Then we have the following cross diagram

x Q(q) / / (3.12) Q(ρ x (q)) x p / / δ x (p) x ⊥ Q(q) / / (3.12) Q(ρ x (q))
x ⊥

We deduce

δ x (Q(qp)) = δ x (Q(q)pQ(q))) = Q(ρ x (q))δ x (p)Q(ρ x (q)) = Q(ρ x (q)δ x (p)) = Q(ρ x (qp)).
Let p ∈ A * be a regular word with potential at least one. Assume δ x (Q(p)) = Q(ρ x (p)). As the last letter of p is modifying, Lemma 3.10 implies σ Q(p) (x) = x ⊥ .

Next, if r ∈ A is a modifying state, we find σ r (x ⊥ ) = x ⊥⊥ = x. The above equalities can be summarized in the following cross diagram.

x Q(p) / / Q(ρ x (p)) x ⊥ r / / δ x ⊥ (r) x Q(p) / / Q(ρ x (p))
x ⊥ Therefore, we find

δ x (Q(pr)) = δ x (Q(p)rQ(p)) = Q(ρ x (p))δ x ⊥ (r)Q(ρ x (p)) = Q(ρ x (p)δ x ⊥ (r)) = Q(ρ x (pr)) .
An induction then gives δ x (Q(p)) = Q(ρ x (p)) for all regular p ∈ A * with potential at least one.

The next step is to prove that a regular word whose potential n is large enough transforms at least n digits 0 to 1. We refer to Notation 3.6 for the definition of Z(a, 0) and Z(a, 1).

Q(p) / / Q(ρ Z(a,0) (p)) Z(a, 1) (3.14)
Moreover ρ Z(a,0) (p) is regular with potential either nm or ∞.

Proof. Assume a is a length m word of T * and the property of the lemma holds for all p ∈ A * with potential n ≥ m. Let p be a word with potential n ≥ m + 1.

Then, the word ρ Z(a,0) (p) is regular with potential either nm or ∞, in particular ρ Z(a,0) (p) has potential at least one. Let b ∈ T . Then we have ρ Z(ab,0) (p) = ρ (b,0) (ρ Z(a,0) (p)). It follows from Lemma 3.12 that ρ Z(ab,0) (p) is a regular word with potential either nm -1 or ∞. We have the following cross diagram, where the first cross is the induction hypothesis.

Z(a, 0) (b, 0)

Q(p) / / Q(ρ Z(a,0) (p)) / / (3.13) Q(ρ (b,0) (ρ Z(a,0) (p))) = Q(ρ Z(ab,0) (p)) Z(a, 1) (b, 1)
The result follows using an induction.

Q(ρ Z(a,0) (p)) (a 1 , 1) . . . (a n , 1) (a n+1 , 1) . . . (a m , 1)
as announced.

A lower bound on the order

The goal of this section is to show that an element of our automaton group simulates the cellular automaton when acting on the appropriate words. We start with a word a = a

k = t(a k-1 , a k , a k+1 ) for 2 ≤ k ≤ n -1, b 1 = t(e, a 1 , a 2 ), b n = t(a n-1 , a n , e)
, and b n+1 = t(a n , e, e).

Our aim is to establish the correctness of the following cross diagram

Z(a$, 0) (Q(C(a))C($)) 2 / / Q(C(b))C($) Z(a$, 0) (4.1)
The element Q(C(a))C($) of our automaton group encodes the configuration a.

The cross diagram connects the square of

Q(C(a))C($) with the element Q(C(b))C($)
encoding the next configuration. Thus, squaring the element of the group corresponds to one step of computation in the cellular automaton-and this is the point of our construction. We begin with a description of the first part of our cross diagram. We recall from Notation 2.1 that, in the above situation, we write b = τ (a). The result then follows using an induction.

b k-1 W a k a k-1 C a k+1 a k . . . C an a k ) by induction hypothesis, = P b1 . . . P b k-1 δ (a k+1 ,0) (W a k a k-1 )δ (a k+1 ,0) (C a k+1 a k )δ (a k+1 ,1) (C a k+2 a k ) . . . δ (a k+1 ,
We now investigate what happens when there is a discrepancy between the "ideal" tape and the given tape: one of the state is transformed to ¬, yielding a regular word with infinite potential.

ρ (c1,0)(c2,0)...(c k ,0) (C a1 e . . . C an e ) = P b1 . . . P b k-1 W a k a k-1 C a k+1 a k . . . C an a k . (4.2)
We deduce We now make the next step toward the cross diagram of (4.1).

ρ (c1,0)...(c k ,0)(c k+1 ,0) (C a1 e . . . C an e ) = ρ (c k+1 ,0) (ρ (c1,0)...(c k ,0) (C a1 e . . . C an e )) by definition of ρ, = ρ (c k+1 ,0) (P b1 . . . P b k-1 W a k a k-1 C a k+1 a k . . . C an a k ) by (4.2), = P b1 . . . P b k-1 δ (c k+1 ,0) (W a k a k-1 )δ (c k+1 ,0) (C a k+1 a k )δ (c k+1 ,1) (C a k+2 a k ) . . . δ (c k+1 ,1) (C
Z(a, 0) Q(C(a)) / / Q(P (b 1 . . . b n-1 )W an an-1 ) Z(a , 1) (4.3)
Moreover, for every ε ∈ {0, 1}, the following cross diagram is valid We now check that the element we are constructing is not the identity. Proof. Let n ≥ 0, and a = a 1 . . . a n ∈ T n . Assume that n = 0. Then, as σ C($) ((e, 0)) = (e, 1) and σ 2 C($) ((e, 0)) = (e, 0), the order of C($) is even or infinite in G. We hereafter assume that n ≥ 1.

($, ε) Q(P (b 1 . . . b n-1 )W an an-1 ) / / Q(C(b 1 . . . b n )) ($, ε) (4.4
By (3.6) and the definition of Q, we have δ ($,0) (Q(C(a))) = ¬ . . . ¬ ≡ ¬, since the number of ¬ symbols is odd. Then, the following cross diagram is valid

($, 0) (b, 0) ($, 1) (t(b, e, e), 1) (b, 0) Q(C(a)) / / ¬ / / (3.1) ¬ / / (3.1) ¬ / / (3.1) ¬ / / (3.1) ¬ ($ , 1) (b, 1) ($, 0) (t(b, e, e), 0) (b, 1)
C $ e / / (3.2)
C $ e / /

($, 0) (b, 0) ($, 1) (t(b, e, e) , 1) (b, 1)
Set x = ($, 0)(b, 0)($, 1)(t(b, e, e), 1)(b, 0). We find σ Q(C(a))C($) (x) = x and, moreover,

σ 2 Q(C(a))C($) (x) = x. Therefore, the order of Q(C(a))C($) is even or infinite in G.
We can now connect the orders of two elements corresponding to successive configurations of the cellular automaton.

Z(a$, 0) (Q(C(a))C($)) 2 / / Q(C(τ (a)))C($) Z(a$, 0) (4.5)
Moreover, if there is b ∈ T \F such that t(b, e, e) ∈ F , then the order of

Q(C(a))C($) is at least twice the order of Q(C(τ (a)))C($) in G. Proof. Let a = a 1 . . . a n ∈ (T \ F ) n . Set a 0 = a n+1 = a n+2 = e and b = b 1 . . . b n+1 = τ (a)
. Then, the following cross diagrams are valid

(a 1 , 0) . . . (a n , 0) ($, 0) Q(C(a 1 . . . a n )) / / (4.3) Q(P (b 1 . . . b n-1 )W an an-1 ) / / (4.4) Q(C(b 1 . . . b n-1 b n )) (a 1 , 1) . . . (a n , 1) ($, 0) C $ e / / (3.5) C $ an / / (3.4) C bn+1 e
(a 1 , 0) . . . (a n ,

Q(C(a 1 . . . a n )) / / 0) ($, 1)
Q(P (b 1 . . . b n-1 )W an an-1 ) / / (4.4) Q(C(b 1 . . . b n-1 b n )) (a 1 , 1) . . . (a n , 1) ($, 1) C $ e / / (3.5) C $ an / / (4.3)
C $ e (a 1 , 0) . . . (a n , 0) ($, 0)

Composing the above diagrams gives the one of (4.5). Lemma 4.4 implies that the order of Q(C(a))C($) is infinite or even. We can assume that the order of Q(C(a))C($) is 2k for some k ≥ 1. Let y ∈ Σ * . Then we find

Z(a$, 0)y = σ 2k Q(C(a))C($) (Z(a$, 0)y) as the order of Q(C(a))C($) is 2k, = σ k (Q(C(a))C($)) 2 (Z(a$, 0)y) by (2.3), = Z(a$, 0)σ k Q(C(b))C($) (y) by (4.5) applied k times. Therefore σ k Q(C(b))C($) (y) = y, hence the order of Q(C(b))C($) is at most k. Thus the order of Q(C(a))C($) is at least twice the order of Q(C(b))C($).
We conclude the section with a lower bound for the order of an element of our group, assuming that the cellular automaton does not stop in k steps. It follows from the proof of Lemma 4.6 and from Lemma 4.4 that, for every i < 2 k+2 , we have

σ i Q(C(a))C($) (x) = x.

An upper bound on the order

In this section, we give an upper bound on the order of Q(C(a))C($) in G. The main idea is that the word constructed in Remark 4.7 is, up to small variations, the worst possible one.

The first step is to establish that, if x is not the word of Remark 4.7, and if the first discrepancy between x and the word of Remark 4.7 occurs sufficiently close to the beginning, then the g-orbit of x is small. Also note that (1) or (2) below hold when a lies in F . Therefore, these conditions can be used as an halting condition. Lemma 5.1. Let a = a 1 . . . a n ∈ T * be of length n and x = x 1 . . . x N ∈ Σ * be of length N ≥ n. Then the following statement holds

(1) If there exists i ≤ n such that x i ∈ F × {0, 1}, then σ 2 Q(C(a))C $ e (x) = x. (2) If there exists i ≤ n such that x i = (a i , 0), then σ 2 Q(C(a))C $ e (x) = x. (3) If x n+1 = ($, 0) and x n+1 = ($, 1), then σ 4 Q(C(a))C $ e (x) = x.
Proof. We can assume that the last letter of x is ($, 0). Let us write x k = (c k , ε k ) with c k ∈ T ′ and ε k ∈ {0, 1}, for every k ≤ N . Proof. Set q = ρ (c1,0)(c2,0)...(c k-1 ,0) (C(a)) and r = ρ (c k ,ε k ) (q). Assume that c k ∈ F . Then the following cross diagram is valid

(c 1 , 0) . . . (c k-1 , 0) (c k , ε k ) Q(C(a 1 . . . a n )) / / (3.15) Q(q) / / (3.1) Q(¬ . . . ¬) (c 1 , 1) . . . (c k-1 , 1) (c k , 1 -ε k ) C $ e / / (3.5) C $ c k-1 / / (3.1) ¬ (c 1 , 0) . . . (c k-1 , 0) (c k , ε k ) As Q(¬ . . . ¬)¬ ≡ id, we deduce σ Q(C(a))C $ e (x) = x. Assume first c k = $.
From the definition of ρ, the last letter s of q is of the form s = δ y (C an e ) for some y ∈ Σ k-1 . Using an induction, we deduce from Remark 3.1(6) that s is not in {C} × T × {$}. Moreover, by (iii), the word q is regular with potential at least one. Hence, its last letter s is modifying, so, by Remark 3.1 [START_REF] Bondarenko | On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix[END_REF], we obtain δ ($,ε k ) (s) = δ ($,1-ε k ) (s) = ¬. Therefore the last letter of r = ρ ($,ε k ) (q) is ¬. Moreover, we obtain the following cross diagram

(c 1 , 0) . . . (c k-1 , 0) ($, ε k ) Q(C(a 1 . . . a n )) / / (3.15) Q(q) / / (3.13) Q(r) (c 1 , 1) . . . (c k-1 , 1) ($, 1 -ε k ) C $ e / / (3.5) C $ c k-1 / / δ ($,1-ε k ) (C $ c k-1 ) (c 1 , 0) . . . (c k-1 , 0) ($, ε k )
As the last letter of r is ¬, Lemmas 3.7 and 3.3 imply the equivalences

(Q(r)δ ($,1-ε k ) (C $ c k-1 )) 2 ≡ (¬δ ($,1-ε k ) (C $ c k-1 )) 2 ≡ id . So we have σ 2 Q(C(a))C $ e (x) = x.
Assume now c k = $ and ε k = 1. Then we find r = ρ (c k ,1) (q), whence

(c 1 , 0) . . . (c k-1 , 0) (c k , 1) Q(C(a 1 . . . a n )) / / (3.15) Q(q) / / (3.13) Q(r) (c 1 , 1) . . . (c k-1 , 1) (c k , 0) C $ e / / (3.5) C $ c k-1 / / (3.6) ¬ (c 1 , 0) . . . (c k-1 , 0) (c k , 1)
By Lemma 3.7, we have (Q(r)¬) 2 ≡ id, and we deduce σ We can now assume that k ≥ n + 1. Assume that there is 1 ≤ i ≤ n such that a i = c i . Then, by Corollary 4.2, the word ρ (c1,0)(c2,0)...(c k-1 ,0) (C(a)) is regular with potential ∞, so Condition (iii) holds. It follows from Claim 1 that (2) holds.

Finally, assume that c n+1 = $. Set q = ρ (a1,0)...(an,0) (C(a 1 . . . a n )). Lemma 4.1 implies q = P b1 . . . P bn-1 W an an-1 , thus there is no counting state in q. Hence, by Lemma 3.11(1), we have ρ (cn+1,0) (q) = ρ (cn+1,1) (q). Set r = ρ (cn+1,0) (q). We obtain the following cross diagram

(a 1 , 0) . . . (a n , 0) (c n+1 , ε n+1 ) Q(C(a 1 . . . a n )) / / (3.14) Q(q) / / (3.12) Q(r) (a 1 , 1) . . . (a n , 1) (c n+1 , ε n+1 ) C $ e / / (3.5) C $ an / / δ (cn+1,εn+1) (C $ an ) (a 1 , 0) . . . (a n , 0) (c n+1 , 1 -ε n+1 ) Q(C(a 1 . . . a n )) / / (3.14) Q(q) / / (3.12) Q(r) (a 1 , 1) . . . (a n , 1) (c n+1 , 1 -ε n+1 ) C $ e / / (3.5) C $ an / / δ (cn+1,1-εn+1) (C $ an ) (a 1 , 0) . . . (a n , 0) (c n+1 , ε n+1 ) If ε n+1 = 0, then δ (cn+1,εn+1) (C $ an ) = ¬ and δ (cn+1,1-εn+1) (C $ an ) = C $ cn+1 . Therefore, we find (Q(r)δ (cn+1,εn+1) (C $ an )Q(r)δ (cn+1,1-εn+1) (C $ an )) 2 = (Q(r)¬Q(r)C $ cn+1 ) 2 ≡ (¬C $ cn+1 ) 2 by Lemma 3.7, ≡ id by Lemma 3.3. Therefore σ 4 Q(C(a1...an))C $ e (x) = x. Similarly, if ε n+1 = 1, then δ (cn+1,εn+1) (C $ an ) = C $ cn+1 and δ (cn+1,1-εn+1) (C $ an ) = ¬. However, it follows from Lemmas 3.3 and 3.7 that Q(r)C $ bn+1 Q(r)¬ is of order 2, implying σ 4 Q(C(a1...an))C $ e (x) = x. Therefore, (3)
holds. This concludes the proof of Lemma 5.1.

We now show that, if a final state appears in configuration, then the order of the corresponding element is two. This is the halting condition for powers of elements in our group G. We now connect the orders of elements defined by two successive configurations. This corresponds to one step of computation of the automaton. We can assume that, for every k ≤ n, we have x k = (a k , 0). If x n+1 = ($, 1), then we set r = ρ ($,1) (q). Then, we obtain the following cross diagram

(a 1 , 0) . . . (a n , 0) ($, 1) Q(C(a 1 . . . a n )) / / (3.14) Q(q) / / (3.12) Q(r) (a 1 , 1) . . . (a n , 1) ($, 1)
C $ e / /

σ 2m Q(C(a))C $ e (x) = σ m (Q(C(a))C $ e ) 2 (x) = x 1 . . . x n x n+1 σ m Q(C(τ (a)))C $ e (x n+2 . . . x N ) = x .
Therefore, the order of Q(C(a))C $ e is at most 2m. Using Lemmas 5.2, 5.3, and 4.6, we inductively deduce a characterization of the order of Q(C(a))C $ e depending on the number of steps required for the cellular automaton to halt when it starts from a configuration a: Theorem 5.4. Let a ∈ T * , and let k ≥ 1. Assume that, in a, τ (a), . . . , τ k (a), there is no letter of F , and that, in τ k+1 (a), there is a letter of F . Then the order of Q(C(a))C $ e is 2 k+2 in G. We are now ready to prove that the element of the group G associated with a configuration a is of finite order if, and only if, the cellular automaton (T, t) halts when it starts from a: Corollary 5.5. For every a = a 1 . . . a n in (T \ F ) * , the following are equivalent:

(1) There is k such that σ Q(C a 1 e ...C an e )C $ e is of order 2 k+2 in G.

( Finally, the implication (3) =⇒ (1) follows from Theorem 5.4.

Simulation of a Turing Machine

It is known that one can simulate a Turing machine using a cellular automaton. There exists a very small example of a Turing-universal cellular automaton (rule 110, see Cook [START_REF] Cook | Universality in elementary cellular automata[END_REF][START_REF] Cook | A concrete view of Rule 110 computation[END_REF]), and even one of a universal cellular automaton with only four states (see Ollinger and Richard [START_REF] Ollinger | Four states are enough![END_REF]). However, a periodic tape is required, and, moreover, there is no halting state. Thus, we shall resort here to a more direct simulation of a universal Turing machine, based on the universal Turing machine constructed by Minsky in [START_REF] Minsky | Size and structure of universal Turing machines using tag systems[END_REF]. Rogozhin in [START_REF] Rogozhin | Small universal Turing machines[END_REF] and Neary and Woods in [START_REF] Neary | Four small universal Turing machines[END_REF] gave examples of smaller universal Turing machines, but the latter do not seem to provide a smaller cellular automaton.

Smith proves in [START_REF] Smith | Simple computation-universal cellular spaces[END_REF] that every m-state n-symbol Turing machine can be simulated by a one-dimensional cellular automaton with n+2m states and neighborhood {-1, 0, 1}. The states of the cellular automaton are the symbols of the Turing machine plus two copies of the state set of the Turing machine (in order to indicate the direction the head moves). However, as mentioned by Lindgren and Nordahl in [START_REF] Lindgren | Universal computation in simple one-dimensional cellular automata[END_REF], we only need to duplicate those states such that the head can, for an appropriate symbol, go to the left and to the right. In this way, starting from Minsky's universal Turing machine M with 7 states and 4 symbols (cf. [START_REF] Minsky | Size and structure of universal Turing machines using tag systems[END_REF]), one obtains a Turing-universal cellular automaton with 13 states. Moreover, we can add a symbol f , and complete the cellular automaton writing f whenever the transition is undefined (i.e. M halts).

This gives us a complete Turing-universal cellular automaton (T, t) with |T | = 14. Denote by e the blank symbol of M (observe that e ∈ T ). Set F = {f }. Minsky's Turing machine M only needs a one-way infinite tape to simulate Turing machines (through the simulation of tag systems). Therefore, the construction given in Notation 2.1 simulates one step of M when starting from a (finite) configuration corresponding to the simulation of a tag system.

Considering the Mealy automaton constructed in Section 3, the main result now directly follows from Corollary 5.5, and from the fact that the halting problem is undecidable (Turing [55]). Theorem 6.1. There is an automaton group G such that both the order problem and the Engel problem are undecidable in G. Remark 6.2. As |T | = 14, it follows from the definition of Σ and A that the number of symbols is |Σ| = 30, and the number of states is |A| = 421.

• P a else if p = W and x = (a, ε), • ¬ else if p = W and x = (s, ε). Then, the above proofs can be adapted to obtain the following result: Theorem 6.3. Let q = q 1 . . . q k sq k+1 . . . q n be a configuration of M . Assume that, starting from this configuration, M only visits a one-way infinite tape. Then C(eqe)C $ is of finite order if, and only if, M halts when starting from the configuration q.

In particular, if M is a universal Turing machine requiring only a one-way infinite tape, the corresponding automaton group has an undecidable order problem. When considering the universal Turing machine with six states and four symbols constructed by Neary and Woods in [START_REF] Neary | Four small universal Turing machines[END_REF], we obtain a Mealy automaton with 22 symbols and 81 states. However, the states C b r with r ∈ S and b ∈ Q can only appear if we have (s, a) ∈ E, and d ∈ Q such that ϕ(s, a) = (d, r, →). By looking at the transition table of the Neary and Woods Turing machine, we can see that one of the states is missing, so that we can remove the corresponding states from A, thus obtaining a Mealy automaton with 77 states.

Using similar ideas, and starting from the universal Turing machine with 9 states and 3 symbols of Neary and Woods, we can see on the transition table that three states cannot appear when the Turing Machine move to the right. Hence we obtain a Mealy automaton with 26 symbols and 72 states.

Funding

The author was supported by CONICYT, Proyectos Regulares FONDECYT no. 1150595, and by project number P27600 of the Austrian Science Fund (FWF).

e

  if p = C $ a and x = ($, 1). (3.2) ¬ if p = C b a and x = ($, 1), with b = $. (3.3) C t(a,e,e) e if p = C $ a and x = ($, 0). (3.4) C b d if p = C b a and x = (d, 1), with d = $. (3.5) ¬ if p = C b a and x = (d, 0), with b = d. (3.6) W b a if p = C b a and x = (b, 0), with b = $. (3.7) C t(a,b,e) e if p = W b a and x = ($, ε). (3.8) P t(a,b,d) if p = W b a and x = (d, ε), with d = $. (3.9) C a e if p = P a and x = ($, ε). (3.10) P a if p = P a and x = (d, ε), with d = $. (3.11)

Remark 3 . 1 .

 31 When reading the various cases in the definition of δ, we see that the following statements hold, for all p ∈ A and all x ∈ Σ.(1)If p is not counting, then δ x (p) = δ x ⊥ (p). See (3.1), (3.8), (3.9), (3.10), and (3.11). (2) If p is not counting and x ∈ T × {0, 1}, then δ x (p) = δ x ⊥ (p) is not counting. See (3.1), (3.9), and (3.11). (3) If x = (a, 0), with a = $, then δ x (p) is not counting. See (3.1), (3.6), (3.7), (3.9), and (3.11). (4) If p is a modifying state and x = (a, 1), then δ x (p) is a modifying state. See (3.1), (3.2), (3.3), and (3.5). (5) If x ∈ (T \ F ) × {0, 1} and p is non-modifying, then δ x (p) is non-modifying. See (3.8), (3.9), (3.10), and (3.11). (

  .3), (3.5), (3.6), (3.7), (3.8), (3.9), (3.10), and (3.11). (7) If x = ($, ε), p is a modifying state, and p is not in {C} × T × {$}, then δ x (p) = ¬. See (3.1), (3.3), and (3.6).

Lemma 3 . 13 .

 313 Let p ∈ A * be a regular word with potential at least one. Let x ∈ Σ. Then δ x (Q(p)) = Q(ρ x (p)). In particular we have the following cross diagram x Q(p) / / Q(ρ x (p))

Lemma 3 . 14 .

 314 Let a ∈ T * of length m. Let p ∈ A * regular with potential n ≥ m. Then we have the following cross diagram Z(a, 0)

Lemma 3 . 15 .

 315 Let a ∈ (T \ F ) * . Let p ∈ A * regular. Assume that the potential of ρ Z(a,0) (p) is at least one. Then we have the following cross diagram Z(a, 0) Q(p) / / Q(ρ Z(a,0) (p)) Denote by m the length of a and by n the potential of p. If n ≥ m, then (3.15) is a special case of (3.14). Assume n < m. Lemma 3.14 implies that the potential of ρ (a1,0)...(an,0) (p) is either 0 or ∞. However, if it is 0, then Lemma 3.9(3) implies that ρ Z(a,0) (p) = ρ (an+1,0)...(am,0) (ρ (a1,0)...(an,0) (p)) has potential 0, a contradiction. Therefore, ρ (a1,0)...(an,0) (p) has potential ∞. Hence, we have the following cross diagram (a 1 , 0) . . . (a n , 0) (a n+1 , 0) . . . (a m , 0) Q(p) / / (3.14) Q(ρ (a1,0)...(an,0) (p)) / / (3.14)

  1 . . . a n ∈ (T \ F ) * , and consider the word b = b 1 . . . b n b n+1 constructed by applying one step of the cellular automaton to a, and completed with the state e, namely the word b satisfying b

Lemma 4 . 1 .

 41 Let n ≥ 1 and a = a 1 . . . a n ∈ (T \ F ) n . Set a 0 = a n = a n+1 = e, and consider b 1 . . . b n+1 = τ (a). Then, for every 1 ≤ k ≤ n, we have ρ (a1,0)(a2,0)...(a k ,0) (C a1 e . . . C an e ) = P b1 . . . Pb k-1 W a k a k-1 C a k+1 a k . . . C an a k .Proof. Owing to the definition of ρ, (3.5) and (3.9) imply ρ (a1,0) (C a1 e . . . C an e ) = δ (a1,0) (C a1 e )δ (a1,1) (C a2 e ) . . . δ (a1,1) (C an e ) = W a1 a0 C a2 a1 . . . C an a1 . For an induction, assume that the formula is true for some k < n. Then the following equalities hold ρ (a1,0)(a2,0)...(a k+1 ,0) (C a1 e . . . C an e ) = ρ (a k+1 ,0) (ρ (a1,0)(a2,0)...(a k ,0) (C a1 e . . . C an e )) by definition ρ, = ρ (a k+1 ,0) (P b1 . . . P

1 )

 1 (C an a k ) by definition of ρ and (3.11), = P b1 . . . P b k-1 P b k W a k+1 a k C a k+2 a k+1 . . . C an a k+1 by (3.5) and (3.9).

Corollary 4 . 2 .

 42 Let a 1 . . . a n ∈ T * and c 1 . . . c N ∈ T * . If there is i ≤ min(n, N ) such that c i = a i or c i ∈ F , then ρ (c1,0)(c2,0)...(cN ,0) (C a1 e . . . C an e ) is regular with potential ∞. Proof. For c i ∈ F , (3.1) implies that, for every p = p 1 . . . p n ∈ A n , we have ρ (ci,0) (p 1 . . . p n ) = ¬ . . . ¬, and, therefore, ρ (c1,0)(c2,0)...(cN ,0) (C a1 e . . . C an e ) = ¬ . . . ¬ is regular with potential ∞. We can now assume that c 1 . . . c N ∈ (T \ F ) * . If c 1 = a 1 , we find ρ (c1,0) (C a1 e . . . C an e ) = δ (c1,0) (C a1 e )δ (c1,1) (C a2 e ) . . . δ (c1,1) (C an e ) by definition of ρ. = ¬C a2 c1 . . . C an c1 by (3.5) and (3.6) . Hence, ρ (c1,0) (C a1 e . . . C an e ) is regular with potential ∞. Then, Lemma 3.14 implies that ρ (c1,0)...(cN ,0) (C a1 e . . . C an e ) is regular with potential ∞. Assume c 1 = a 1 . Let b 1 , . . . b n be as in Lemma 4.1. Pick k minimal such that c k+1 = a k+1 . Then, for every j ≤ k, we have c j = a j . So Lemma 4.1 implies

  an a k ) by definition of ρ and (3.11), = P b1 . . . P b k-1 P t(a k-1 ,a k ,c k+1 ) ¬C a k+2 c k+1 . . . C an c k+1 by (3.5), (3.6), and (3.9). Therefore ρ (c1,0)...(c k ,0)(c k+1 ,0) (C a1 e . . . C an e ) is regular with potential ∞. Finally, Lemma 3.14 implies that ρ (c1,0)...(cN ,0) (C a1 e . . . C an e ) is regular with potential ∞.

Lemma 4 . 3 .

 43 Let n ≥ 1 and a = a 1 . . . a n ∈ (T \ F ) n . Set a 0 = a n+1 = a n+2 = e, and consider b 1 . . . b n+1 = τ (a). Then, the following cross diagram is valid

)

  Proof. Lemma 4.1 implies ρ Z(a,0) (C(a)) = P (b 1 . . . b n-1 )W an an-1 . As C(a) is regular with potential n, the cross diagram (4.3) follows from (3.14). Next, (3.10) implies δ ($,ε) (P b k ) = C b k e for every k ≤ n -1, and (3.8) implies δ ($,ε) (W an an-1 ) = C t(an-1,an,e) e = C bn e , whence ρ ($,ε) (P (b 1 . . . b n-1 )W an an-1 ) = C b1 e . . . C bn e . Hence, (4.4) follows from (3.12).

Lemma 4 . 4 .

 44 Let a ∈ T * . Assume that there is b ∈ T \ F satisfying t(b, e, e) ∈ F . Then the order of Q(C(a))C($) is even or infinite in G.

9 )

 9 P t(e,t(b,e,e),b)

Lemma 4 . 5 .

 45 Let a ∈ (T \ F ) * . Then the following cross diagram is valid

Lemma 4 . 6 .

 46 Let a ∈ T * , and k ≥ 1. Assume that a, τ (a), . . . , τ k (a) do not contain letters of F . Then the order of Q(C(a))C($) is at least 2 k+2 in G. Proof. Let a = a 1 . . . a n ∈ T * . The last letter of τ (a) is t(a n , e, e). So a n ∈ F and t(a n , e, e) ∈ F . Let b ∈ (T \ F ) * . By Lemma 4.5, the order of Q(C(b))C($) is at least twice the order of Q(C(τ (b)))C($). Moreover, by Lemma 4.4, the order of Q(C(τ (b)))C($) is at least two, therefore the order of Q(C(b))C($) is at least 4. Assume that k ≥ 0 is such that, for every b ∈ T * , if b, τ (b), . . . , τ k (b) do not contain letters of F , then the order of Q(C(b))C($) is at least 2 k+2 . Let b ∈ T * be such that b, τ (b), . . . , τ k+1 (b) do not contain letters of F . Then, τ (b), τ (τ (b)) . . . , τ k (τ (b)) do not contain letters of F , hence the order of Q(C(τ (b)))C($) is at least 2 k+2 . Therefore, it follows from Lemma 4.5 that the order of Q(C(b))C($) is at least 2 × 2 k+2 . The result follows by induction. Remark 4.7. We can explicitly construct an element witnessing the lower bound on the order of Q(C(τ k+1 (a)))C($) in G. Indeed, let b be as in Lemma 4.4, and set x = Z(a$τ (a)$ . . . $τ k (a), 0)($, 0)(b, 0)($, 1)(t(b, e, e), 1)(b, 0) .

Claim 1 .

 1 Suppose there exists 1 ≤ k ≤ N such that (i) For every i < k, we haveε i = 0, c i = $, and c i ∈ F . (ii) c k = $ or ε k = 1 or c k ∈ F . (iii) ρ (c1,0)(c2,0)...(c k-1 ,0) (C(a)) is regular with potential at least one. Then σ 2 Q(C(a))C $ e (x) = x.

2 Q

 2 (C(a))C $ e (x) = x. Thisestablishes Claim 1. Returning to the proof of Lemma 5.1, let k be minimal such that c k = $, ε k = 1, or c k ∈ F . Then Condition (ii) of the claim holds. Moreover, by minimality of k, Condition (i) holds as well. If k ≤ n, then, by Lemma 3.14, the word ρ (c1,0)(c2,0)...(c k-1 ,0) (C(a)) is regular with potential either n -(k -1) ≥ 1 or ∞, hence Condition (iii) holds. Then Claim 1 implies σ 2 Q(C(a))C $ e (x) = x. Thus (1) holds.

Lemma 5 . 2 . 2 Q

 522 Assume that there is b ∈ T such that t(b, e, e) ∈ F . Let a ∈ T * . Assume that one letter of a is in F . Then the order of Q(C(a))C $ e is two in G. Proof. Lemma 4.4 implies that the order of Q(C(a))C $ e is at least two. Consider a = a 1 . . . a n , and let i ≤ n be such that a i ∈ F . Let x in Σ * . Write x = (c 1 , ε 1 ) . . . (c N , ε N ). We can assume that N ≥ n. Note that either c i = a i or c i ∈ F . Hence, it follows from Lemma 5.1(1) and (2) that σ (C(a))C $ e (x) = x. Therefore the order of Q(C(a))C $ e is two.

Lemma 5 . 3 .

 53 Assume that there is b ∈ T such that t(b, e, e) ∈ F . Let a ∈ (T \ F ) * . If the order of Q(C(τ (a)))C $ e is finite in G, then the order of Q(C(a))C $ e is at most twice the order of Q(C(τ (a)))C $ e in G. Proof. Consider a = a 1 . . . a n ∈ (T \ F ) n . Denote by m the order of Q(C(τ (a)))C $ e . It follows from Lemma 4.4 that m is even. Let x ∈ Σ * of length N > n. Assume that there is k ≤ n such that x k = (a k , 0). It follows from Lemma 5.1(2) that σ 2 Q(C(a))C $ e (x) = x. Similarly, if x n+1 = ($, 0) and x n+1 = ($, 1), then, by Lemma 5.1(3), we have σ 4 Q(C(a))C $ e (x) = x. Therefore, in both cases, as m is even, we find σ 2m Q(C(a))C $ e (x) = x.

(a 1 ,

 1 0) . . . (a n , 0) ($, 0) Hence y = σ Q(C(a))C $ e (x) starts with (a 1 , 0) . . . (a n , 0)($, 0). Moreover, the size of the orbits of σ Q(C(a))C $ e on x and on y are the same. Thus we can assume x n+1 = ($, 0). Now, Lemma 4.5 implies

) σ Q(C a 1 e 3 ) 4 )

 134 ...C an e )C $ e is of finite order in G. (There is k such that τ k+1 (a) contains a symbol of F . (There is k such that [. . . [[σ Q(C a 1 e ...C an e )C $ e , σ ¬C $ e ], σ ¬C $ e ], . . . , σ ¬C $ e ], 2 k+2 commutators, is the identity. Proof. As the word Q(C a1 e . . . C an e ) and the one-letter word C $ e are palindromes, it follows from Corollary 3.5 that (1) and (4) are equivalent. The implication (1) =⇒ (2) is immediate. Assume that (3) fails, and let k ≥ 1. Then, no symbol of F appears in the words a, τ (a), . . . , τ k (a). It follows from Lemma 4.6 that the order of Q(C a1 e . . . C an e )C $ e is at least 2 k+2 . As this is true for each integer k, the order is infinite. So the implication (2) =⇒ (3) holds.

  and only if, the last letter of p is a modifying state.Proof. Write p = p 1 . . . p m . Note that Q(p) = Q(p 1 . . . p m-1 )p m Q(p 1 . . . p m-1). So the number of modifying states in Q(p) is odd if, and only if, p m is a modifying state. Hence, by Lemma 3.2, we have σ Q(p) (x) = x ⊥ if, and only if, p m is a modifying state.

We conclude the paper with an alternative construction that allows one to reduce the number of states and symbols. Fix a Turing machine M = (S, Q, s 0 , q 0 , ϕ), where S is the state set, Q is the alphabet, s 0 ∈ S is the initial state, q 0 ∈ Q is the blank symbol, and ϕ : E → S ×Q×{←, →} is the transition map, where E ⊆ S ×Q. The Turing machine halts if it reaches a configuration such that it cannot continue. That is, the state is s ∈ S and the head read a symbol q ∈ Q, such that (q, s) ∈ E. Assume in addition that the Turing machine operates on a tape indexed by N.

Set T = S ⊔ Q. A configuration of the Turing machine M can be represented by a word q 1 . . . q k sq k+1 . . . q n when the head points to the cell number k in state s.

A cellular automaton with neighborhood {-1, 0, 1} is not sufficient to simulate the Turing machine directly, but the Neighborhood {-2, -1, 0, 1} is. However, in order to optimize the size, we directly give the construction of a Mealy automaton, without going through the description of the cellular automaton.

As before we set T ′ = T ∪ {$} and Σ = T ′ × {0, 1}. We do not need to memorize much in order to compute one symbol of the next configuration. The set of states is defined in the following way

Set e = q 0 . We do not need final states as before, because the latter correspond to subwords of the form as where a ∈ Q, s ∈ S, and (s, a) ∈ E. The modifying states are the states in {¬,

As before, for all p ∈ A and x ∈ Σ, we set σ(p, x) = x ⊥ if, and only if, p is a modifying state, otherwise we set σ(p, x) = x.

The transition map is defined below. For all a, b, d ∈ Q, all r, s ∈ S, and all u, v, w ∈ Q ∪ S, we consider δ : A × Σ → A so that δ(p, x) is: