Martin Kutrib

Andreas Malcher

Cellular String Generators

In contrast to many investigations of cellular automata with regard to their ability to accept inputs under certain time constraints, we are studying here cellular automata towards their ability to generate strings in real time. Structural properties such as speed-up results and closure properties are investigated. On the one hand, constructions for the closure under intersection, reversal, and length-preserving homomorphism are presented, whereas on the other hand the non-closure under union, complementation, and arbitrary homomorphism is obtained. Finally, decidability questions such as emptiness, finiteness, equivalence, inclusion, regularity, and context-freeness are addressed.

Introduction

Cellular automata (CA) are a widely used model to describe, analyze, and understand parallel processes. They are in particular applied for massive parallel systems, since they are arrays of identical copies of deterministic finite automata where, in addition, the single nodes are homogeneously connected to both their immediate neighbors. Furthermore, they work synchronously at discrete time steps processing a parallel distributed input, where every cell is fed with an input symbol in a pre-initial step.

A standard approach to measure the computational power of some model is to study its ability to accept formal languages (see, for example, [START_REF] Smith | Cellular automata and formal languages[END_REF]). In general, the given input is accepted if there is a time step at which a designated cell, usually the leftmost one, enters an accepting state. Commonly studied models are two-way cellular automata with time restrictions such as real time or linear time, which means that the available time for accepting an input is restricted to the length of the input or to a multiple of the length of the input. An important restricted class are the real-time one-way cellular automata [START_REF] Dyer | One-way bounded cellular automata[END_REF], where every cell is connected with its right neighbor only. Hence, the flow of information is from right to left only. A survey on results concerning the computational capacity, closure properties, and decidability questions for these models and references to the literature may be found, for example, in [START_REF] Kutrib | Cellular automata -a computational point of view[END_REF][START_REF] Kutrib | Cellular automata and language theory[END_REF].

In the language accepting approach each computation can be considered as producing a yes or no answer for every possible input within a certain time. A much broader view on cellular automata computations is taken in [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF][START_REF] Kutrib | One-dimensional cellular automaton transducers[END_REF], where cellular automata computations are considered as transducing actions, that is, they produce an output of size n for every input of size n under time constraints such as real and linear time. Thus, the point of view changes from a parallel language accepting device to a parallel language transforming device. The paper [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF] discusses for cellular automata the time constraints of linear time and real time. Moreover, the inclusion relationships based on these constraints, closure properties, and relations to cellular automata considered as formal language acceptors are established. An important technical result is a speed-up theorem stating that every computation beyond real time can be sped up by a linear factor. The paper [START_REF] Kutrib | One-dimensional cellular automaton transducers[END_REF] considers also cellular automata with sequential input mode, called iterative arrays, as transducing devices. In particular, these devices are compared with the cellular automata counterpart with parallel input mode. In addition, the cellular transducing models are compared with classical sequential transducing devices such as finite state transducers and pushdown transducers.

In this paper, we will look on computations with cellular automata from yet another perspective. Rather than computing a yes or no answer or computing an output we are considering cellular automata as generating devices. This means in detail that the cellular automaton starts with an arbitrary number of cells being all in a quiescent state and, subsequently, works by applying its transition function synchronously to all cells. Finally, if the configuration reaches a fixpoint the sequence of cell states is considered as the string generated. From this point of view cellular automata compute a (partial) function mapping an initial length n to a string of length n over some alphabet. First investigations for this model have been made in [START_REF] Kutrib | One-dimensional pattern generation by cellular automata[END_REF]. In particular, the real-time generation of unary patterns is studied in depth and a characterization by time-constructible functions and their corresponding unary formal languages is given. In this paper, we will continue these investigations for real-time cellular automata and study, in particular, speed-up possibilities, closure properties, and decidability questions of the model.

It should be remarked that the notion of pattern generation is used for cellular automata also in other contexts. For example, in [START_REF] Wolfram | Random sequence generation by cellular automata[END_REF] the sequence of configurations produced by a cellular automaton starting with some input is considered as a two-dimensional pattern generated. Kari [START_REF] Kari | Universal pattern generation by cellular automata[END_REF] describes a cellular automaton as universal pattern generator in the sense that starting from a finite configuration all finite patterns over the state alphabet are generated which means here that these patterns occur as infixes in the sequence of configurations computed.

The paper is organized as follows. In Section 2, we formally define how cellular automata accept and generate formal languages and we present a detailed example generating prefixes of the Thue-Morse sequence. Section 3 is devoted to structural properties of cellular string generators. Two speed-up results are presented which are used in the subsequent constructions showing closure under intersection, reversal, and length-preserving homomorphism. In Section 4, we deal with the problems of deciding emptiness, finiteness, infiniteness, inclusion, equivalence, regularity, and context-freeness of real-time cellular string generators. By showing that suitably encoded computations of a Turing machine can be generated by cellular automata in real time, all decidability problems mentioned turn out to be not semidecidable.

Preliminaries

We denote the non-negative integers by N. Let Σ denote a finite set of letters. Then we write Σ * for the set of all finite strings consisting of letters from Σ. The empty string is denoted by λ, and we set Σ + = Σ * \ {λ}. A subset of Σ * is called a language over Σ. For the length of a string w we write |w|. In general, we use ⊆ for inclusions and ⊂ for strict inclusions. For convenience, we use S # to denote S ∪ {#}.

A two-way cellular automaton is a linear array of identical finite automata, called cells, numbered 1, 2, . . . , n. Except for border cells each one is connected to its both nearest neighbors. The state transition depends on the current state of a cell itself and the current states of its two neighbors, where the outermost cells receive a permanent boundary symbol on their free input lines. The cells work synchronously at discrete time steps.

Formally, a deterministic two-way cellular automaton (CA, for short) is a system M = S, Σ, F, s 0 , #, δ , where S is the finite, nonempty set of cell states, Σ ⊆ S is set of input symbols, F ⊆ S is the set of accepting states, s 0 ∈ S is the quiescent state, # / ∈ S is the permanent boundary symbol, and δ :

S # ×S ×S # → S is the local transition function satisfying δ(s 0 , s 0 , s 0 ) = s 0 .
A configuration c t of M at time t ≥ 0 is a mapping c t : {1, 2, . . . , n} → S, for n ≥ 1, occasionally represented as a word over S. Given a configuration c t , t ≥ 0, its successor configuration is computed according to the global transition function ∆, that is, c t+1 = ∆(c t ), as follows. For 2

≤ i ≤ n -1, c t+1 (i) = δ(c t (i -1)), c t (i), c t (i + 1)),
and for the outermost cells we set

c t+1 (1) = δ(#, c t (1), c t (2)) and c t+1 (n) = δ(c t (n -1), c t (n), #).
Thus, the global transition function ∆ is induced by δ.

Here, a cellular automaton M can operate as decider or generator of strings.

A cellular automaton accepts a string (or word) a 1 a 2 • • • a n ∈ Σ + , if at some time step during the course of the computation starting in the initial configuration c 0 (i) = a i , 1 ≤ i ≤ n, the leftmost cell enters an accepting state, that is, the leftmost symbol of some reachable configuration is an accepting state. If the leftmost cell never enters an accepting state, the input is rejected. The language accepted by M is denoted by

L(M ) = { w ∈ Σ + | w is accepted by M }.
A cellular automaton generates a string a 1 a 2 • • • a n , if at some time step t during the computation on the initial configuration c 0 (i) = s 0 , 1 ≤ i ≤ n, (i) the string appears as configuration (that is, c t (i) = a i , 1 ≤ i ≤ n) and (ii) configuration c t is a fixpoint of the global transition function ∆ (that is, the configuration is stable from time t on). The pattern generated by M is

P (M ) = { w ∈ S + | w is generated by M }.
Since the set of input symbols and the set of accepting states are not used when a cellular automaton operates as generator, we may safely omit them from its definition.

Let t : N → N be a mapping. If all w ∈ L(M ) are accepted with at most t(|w|) time steps, or if all w ∈ P (M ) are generated with at most t(|w|) time steps, then M is said to be of time complexity t. If t(n) = n then M operates in real time. The family of all patterns generated by a cellular automaton in real time is denoted by P rt (M ).

We illustrate the definitions with an example.

Example 1. The Thue-Morse sequence is an infinite sequence over the alphabet {0, 1}. The well-known sequence has applications in numerous fields of mathematics and its properties are non-trivial. There a several ways of generating the Thue-Morse sequence one of which is given by a Lindenmayer system with axiom 0 and rewriting rules 0 → 01 and 1 → 10. The generation of strings can be described as follows: starting with the axiom every symbol 0 (symbol 1) is in parallel replaced by the string 01 [START_REF] Kutrib | Cellular automata and language theory[END_REF]. This procedure is iteratively applied to the resulting strings and yields the prefixes p 0 = 0, p 1 = 01, p 2 = 0110, p 3 = 01101001, p 4 = 0110100110010110, and so on. We remark that the length of the prefix p i is 2 i . The pattern P Thue = { p i | i ≥ 0 } derived therefrom can be generated by some cellular automaton in real time [START_REF] Kutrib | One-dimensional pattern generation by cellular automata[END_REF]. However, this means that nothing is generated whenever the length of the cellular automaton is not a power of two. Here, we are going to generalize this construction and extend the pattern generated in such a way that also prefixes p i of the Thue-Morse sequence are generated even when the length of the cellular automaton is not a power of two. The goal is to generate on initial length n the prefix p i with i = log 2 (n) . Since the length of the generated prefix is larger than the number of cells if n is not a power of two, we will group two adjacent symbols x, y ∈ {0, 1} of the sequence into states x|y where appropriate. Note that in the special case of an input length being a power of two the construction described here is the construction given in [START_REF] Kutrib | One-dimensional pattern generation by cellular automata[END_REF].

The basic idea is to work with a real-time version of the FSSP based on the time optimal solution of Waksman [START_REF] Waksman | An optimum solution to the firing squad synchronization problem[END_REF]. The latter solution starts with one general at the left end of the array and it takes n -1 time steps (n being the length of the array) to reach the right end. If we start instead with two generals at both ends, where the left general symmetrically behaves as the right general, we save n -1 time steps. Since we need one additional time step to initialize the generals at both ends, we can realize the FSSP within 2n -2 -(n -1) + 1 = n time steps, that is, within real time.

In the construction of the FSSP, the initial length is iteratively divided into halves, whereby dependent on the arity one or two middle points and thus one or two new generals are generated. In the first case, here the single middle cell is virtually split into two. These cells will represent two grouped adjacent symbols of the sequence. Next, we identify these cells. The following recursive formula f (n, m) gives 2, if the mth cell on initial length n contains a compressed symbol and, otherwise, gives 1.

f (n, m) =        1 n = 1 or m ≤ 1, 2 n > 1 odd and m = n+1 2 , f n+1 2 , m mod n+1 2 + m div n+1 2 , n > 1 odd and m = n+1 2 , f n 2 , m mod n 2 , n > 1 even.
For example, in Figure 1 we have

f (15, 4) = f (8, 4) = f (4, 0) = 1, f (15, 8) = 2, and f (15, 13) = f (8, 6) = f (4, 2) = f (2, 0) = 1.
The function f can be used to define the generated compressed Thue-Morse sequence. Let f n (m) = m j=1 f (n, j) and p i = w i,1 w i,2 • • • w i,2 i be an enumeration of the symbols of prefix p i . Then, the corresponding compressed prefix The general generation procedure is as follows (see Figure 1 for an example). Initially, at time n/2 + 1, the left new middle cell obtains the information 0 and the right new middle cell obtains the information 1, or the new single and grouped middle cell obtains the information 0|1. In the latter case, the cell simulates two cells from now on. The signals sent out from the new middle cells to the left and right, respectively, are attached with this information. If these signals meet some other signal so that another one or two new middle cell(s) is (are) generated, the left cell gets the information 0 and the right cell gets the information 1 if the signal carried the information 0. Otherwise, the left cell gets the information 1 and the right cell gets the information 0. This behavior is iterated up to the last but one time step in which all cells have become a general. In the last time step, in which all cells are synchronized, a left signal 0 (1) in cell i at time n -1 leads to 0 (1) in cell i -1 and 1 (0) in cell i at time n. Analogously, a right signal 0 (1) in cell i at time n -1 leads to 0 (1) in cell i and 1 (0) in cell i + 1 at time n. Note that here a split cell simulates two cells that are counted to determine the numbers i. Finally, after the synchronization, all states of the array represent the string generated and become permanent. Let Σ = {0, 1, 0|0, 0|1, 1|0, 1|1} be the alphabet and π be a projection to the original letters, that is, π(x) = x and π(x|y) = xy, for x, y ∈ {0, 1}. Then, the pattern generated by the constructed real-time cellular automaton M has the desired property w ∈ P (M ) =⇒ π(w) = p i with i = log 2 (|w|) .

p i (n) on initial length n with i = log 2 (n) is p i (n, 1)p i (n, 2) • • • p i (n, n), where we define p i (n, m) = w i,fn(m) , if f (n, m) = 1, and p i (n, m) = w i,fn(m)-1 w i,fn(m) , if f (n, m) = 2.

Structural Properties

For unary patterns of the form P ϕ = { a n | there is an m with n = ϕ(m) }, or even Pϕ = { x n | x = a if there is an m with n = ϕ(m), and x = b otherwise }, where ϕ : N → N is a time-constructible function, the three notions of language acceptance, time-constructibility, and string generation are characterizing each other, that is, they coincide. Here, we now turn to structural properties of the string generators as speed-up and closures of the set of generated strings under certain operations.

Speed-Up

Several types of cellular language acceptors can be sped-up as long as the remaining time complexity does not fall below real time. A proof in terms of trellis automata can be found in [START_REF] Choffrut | On real-time cellular automata and trellis automata[END_REF]. In [START_REF] Ibarra | Sequential machine characterizations of trellis and cellular automata and applications[END_REF][START_REF] Ibarra | Some results concerning linear iterative (systolic) arrays[END_REF] the speed-up results are shown for deterministic and nondeterministic cellular and iterative language acceptors. The proofs are based on sequential machine characterizations of the parallel devices. In particular, for all k ≥ 1, deterministic cellular automata can be sped-up from (n + t(n))-time to (n + t(n)/k )-time [START_REF] Bucher | On real time and linear time cellular automata[END_REF][START_REF] Ibarra | Sequential machine characterizations of trellis and cellular automata and applications[END_REF][START_REF] Ibarra | Some results concerning linear iterative (systolic) arrays[END_REF]. The question of whether every linear-time cellular language acceptor can be sped-up to real time is an open problem.

The situation for string generators is more involved. While for language acceptors usually only the states of one distinguished cell determine acceptance or rejection, the states of all cells are the result of a string generation. So, these known speed-up results do not apply here. However, in terms of transducers that given an input of size n compute an output of size n, a speed-up result is known [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF] that can be adapted to our notion.

As a preliminary lemma we prove that cellular string generators working in real time plus a constant amount of time can always be sped-up to real time.

Lemma 2. Let M be a cellular string generator with time complexity n + k,

where k ≥ 1 is a constant integer. Then an equivalent real-time string generator M can effectively be constructed.

Proof. The basic idea for the construction of M is to have in every cell k + 1 tracks such that at time t the tracks in M are filled with states from M at time t, t + 1, . . . , t + k. Hence, time step n + k in M is simulated at time n in M in the last track. The construction works in two phases. In the first phase, we start the simulation of M at both ends, but we simulate k + 1 time steps of M at once in every cell leaving the quiescent state s 0 . In the remaining time steps, each cell shifts the contents of its ith track to its (i -1)st track for 2 ≤ i ≤ k + 1 and updates the entry in the (k + 1)st track. Hence, every cell keeps track of the last k + 1 time steps.

We have a left part and a right part of the computation in this first phase. For the left part we may assume that all missing information from the right can be replaced by the information s 0 , since in the beginning all cells are in the quiescent state s 0 . In addition, we have to provide each cell in the left part with the necessary information from the left, namely, with the states of the k cells to the left. This can be realized by using k additional tracks. Analogously, we can assume for the right part of the computation that missing information from the left can be replaced by s 0 and we can provide information about the states of the k cells to the right by using k tracks.

At time n/2+1 if the initial length n is even and at time (n+1)/2 if n is odd, the left and right part of the computation meet in the middle cell(s), from where the second phase starts. In this phase, all information to update the entries in the (k + 1)st track is available taking into account both neighbors. Hence, the simulation of the last k + 1 time steps can be continued. At time step n in M we have eventually simulated the desired (n + k)th time step of M in the (k + 1)st track. To extract this information in the nth time step of M we start in the beginning in another track an instance of the FSSP. If the FSSP would fire at time step n, we just output the (k + 1)st track that would be calculated at time step n.

Next, we turn to show how to speed up the part of the time complexity beyond real time by a constant factor. As mentioned before, to this end we consider the involved and tricky construction shown for transductions in [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF]. Before we turn to the adaption to our notion, we sketch the underlying idea of [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF] to speed up the part of the time complexity beyond real time by a factor 2 (see Figure 2). The basic idea is to compress the input of length n into the n 2 cells 1 4 n + 1, 1 4 n + 2, . . . , 3 4 n, to simulate the given (n + t(n))-time cellular automaton with double speed on the compressed input, and to decompress the simulation result. The most involved part is the compression depicted in the red parts of the space-time diagram in Figure 2. Roughly speaking, in these areas the compression takes place in addition to as many as possible simulation steps. The cells in the green area of the space-time diagram are in the quiescent state. The simulation in the blue area is with double speed. Concerning the time,

Closure Properties

This subsection is devoted to investigating the closure properties of the family P rt (CA). We start with the Boolean operations. Finally, we investigate homomorphisms and obtain that the family P rt (CA) is not closed under arbitrary homomorphisms, whereas we can show that the family P rt (CA) is closed under length-preserving homomorphisms. Proposition 6. The family P rt (CA) is not closed under arbitrary homomorphism, but is closed under length-preserving homomorphism.

Proof. For the non-closure under arbitrary homomorphism we consider the language L = {a, bb}, that can be generated by a real-time CA, and the homomorphism h which maps a to aa and b to b. Then, h(L) = {aa, bb} which cannot be generated by any real-time CA. Now, let M = S, s 0 , #, δ be a real-time cellular automaton generating the pattern P ⊆ Σ * , where Σ ⊆ S. Moreover, let h : Σ * → Γ * be a length-preserving homomorphism. For the construction of a cellular automaton that generates h(P ) in real time, we consider a primed version S of the state set S, where the primed version of Σ is denoted by Σ , and we extend h to a length-preserving homomorphism h mapping from S * to (S ∪ Γ ) * such that h (a ) = h(a), if a ∈ Σ , and h (s ) = s , if s ∈ S \ Σ .

Next, we will sketch the construction of a cellular automaton M generating P (M ) = h (P (M )) = h (P ) = h(P ) in real time plus one that is subsequently sped up with Lemma 2 to work in real time. The basic idea is to work with three tracks and to start in the first track the simulation of M with state set S , and in the second track an instance of the FSSP. At time step n, when the FSSP fires, we generate in the third track the homomorphic image under h of the first track. At time step n + 1, we check in every cell whether its state in the first track, that is in the simulated configuration of M at time n, would remain the same also in the next time step, that is, in the simulated configuration of M at time n + 1. If so, each such cell enters the state from the third track, that is the homomorphic image under h of the state in the simulated configuration of M at time n. Otherwise, a new state p is entered that alternates with some other new state q. Furthermore, the transition function of M is suitably complemented so that configurations containing only symbols from Γ remain stable. If the configuration of M at time n is stable, a string from Σ * is generated by M From the undecidability of the emptiness problem the undecidability of the equivalence and inclusion problem follows immediately.

Corollary 9. Given two real-time cellular automata M 1 and M 2 , it is neither semidecidable whether P (M 1 ) = P (M 2 ) nor whether P (M 1 ) ⊆ P (M 2 ).

Theorem 10. Given a real-time cellular automaton M , it is neither semidecidable whether P (M ) is finite nor whether P (M ) is infinite.

Proof. Let M be an arbitrary Turing machine.

In order to show the assertion for finiteness, the pattern P M is extended to PM = { v M a n | n ≥ 0} \ { a n | n ≥ 0 }. Since PM is empty and, thus, finite if and only if M does not halt on empty input, the non-semidecidability of finiteness follows.

For infiniteness, the pattern P M is changed differently. We set PM = { $w 0 $w 1 $ • • • $w m $ | m ≥ 1, w 0 = (q 0 , ), and w i is successor of w i-1 }.

Since pattern PM is infinite if and only if M does not halt on empty input, the non-semidecidability of infiniteness follows.

Next we turn to two decidability problems that, to some extent, relate pattern generation with language acceptance. It is of natural interest if a given language is regular or context free. So, here we can ask whether the strings of a pattern form a regular or context-free language.

Theorem 11. Given a real-time cellular automaton M , it is neither semidecidable whether P (M ) forms a regular nor whether P (M ) forms a context-free language.

Proof. Let L be an arbitrary recursively enumerable language. Then there is a Turing machine M that enumerates the words of L, that is, it produces a list of not necessarily distinct words from L such that any word in L appears in the list. Modify M as follows. Whenever a new word w is to be put into the list, the new machine M first checks if w already appears in the list. If yes, it is not put into the list again and M continues to enumerate the next word. If not, the word w is put into the list and after that M enters a state from some set Q + that indicates that a new word has been enumerated.

Similar as in the proof of Theorem 10 we set

PM = { $w 0 $w 1 $ • • • $w m $ | m ≥ 1, w 0 = (q 0 , ), w i is successor of w i-1 ,
and the state in w m belongs to Q + }.

So, if L is finite, the pattern PM is finite and, thus, regular and context free. If L is infinite, the pattern PM is infinite and a simple application of the pumping lemma shows that it is not regular and not context free. In particular, pattern PM is regular and context-free if and only if L is finite. Since finiteness of recursively enumerable language is not semidecidable, the assertion follows.

  For example, if n = 15, we have f (15, 8) = 2 and f (15, j) = 1 if j = 8. Hence, f 15 (8) = 9 and f 15 (13) = 14 which gives p 4 (15, 8) = 11 and p 4 (15, 13) = 1, respectively.

Fig. 1 .

 1 Fig. 1. Generation of the prefix p4 = 0110100110010110 of the Thue-Morse sequence on initial length n = 15.

Proposition 4 .Proposition 5 .

 45 The family P rt (CA) is closed under intersection. It is neither closed under union nor under complementation.Next, we look at the reversal operation. By interchanging the left hand and right hand entries of the local transition function, we immediately obtain that also the reversal of a real-time pattern can be generated by a real-time string generator. The family P rt (CA) is closed under reversal.

Acknowledgements. The authors would like to thank the anonymous referees for their useful comments and remarks.

Principle of speeding up the part of the time complexity beyond real time by a factor 2 according to [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF].

once cell 1 2 n has left the quiescent state it has to perform further 1 2 n + t(n) steps. Since the simulation is with double speed, this takes 1 4 n + 1 2 t(n) time. The decompression of the computation result takes another 1 4 n time steps.

Theorem 3. Let M be a cellular string generator with time complexity n + t(n), where t : N → N is a function such that M is synchronizable at time step n+t(n).

Then, for all k ≥ 1, an equivalent string generator M with time complexity n + t(n)/k can effectively be constructed.

Proof. The principle of the construction is as shown in [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF] and has been described above. However, since a cellular string generator has to end a successful computation in a stable configuration there are differences with the transductions considered in [START_REF] Grandjean | Linear functional classes over cellular automata[END_REF]. So, basically, the simulation sketched in Figure 2 has to be stopped synchronously at time 3 4 n + 1 2 t(n), and the decompression has to be stopped synchronously at time n + 1 2 t(n). The first synchronization justifies the condition that M has to be synchronizable at time step n + t(n). So, some FSSP that synchronizes M at this time is implemented on an extra track of M . Therefore, its simulation is finished by firing the cells 1 4 n+1, 1 4 n+2, . . . , 3 4 n at time 3 4 n+ 1 2 t(n) as required. Additionally, the decompression phase is started synchronously.

The second synchronization is achieved by using two more extra tracks. On the first track an FSSP is implemented that synchronizes all cells at time step n. On the second track an FSSP is implemented that would synchronize all cells at time n+t(n). But now this second FSSP runs with speed one until the first FSSP fires, and continues with half speed. So, it fires at time n + 1 2 t(n) as required.

and we obtain that the homomorphic image under h , which is equivalent to h on Σ, of this string is generated by M . Otherwise, if M generates no string due to an instable configuration, then M enters an instable configuration as well. Therefore, it is ensured that M generates no string as well in such cases.

Decidability Problems

The first decidability problem we are dealing with is the question whether a given cellular automaton M generates a string at all, or whether the pattern P (M ) is empty. In order to show that the emptiness problem is not even semidecidable, even for cellular automata that generate patterns in real time, we reduce the problem to decide whether a Turing machine does not halt on empty input. It is well known that this problem is not semidecidable.

For the reduction, a technique from [START_REF] Hartmanis | On the succinctness of different representations of languages[END_REF] is utilized. Basically, the history of a Turing machine computation is encoded into a string. It suffices to consider deterministic Turing machines with one single tape and one single read-write head. Without loss of generality and for technical reasons, we assume that the Turing machines can either print a symbol on the current tape square or move the head one square to the right or left. Moreover, they neither can print blanks nor leave a square containing a blank. Finally, a Turing machine is assumed to perform at least one transition. So, let Q be the state set of some Turing machine M , where q 0 is the initial state and T ∩ Q = ∅ is the tape alphabet containing the blank symbol . Then a configuration of M can be written as a string of the form

to express that M is in state q, scanning tape symbol y, and

Dependent on M we define the string v M . Let $ / ∈ T ∪ Q, m ≥ 1, and w i ∈ T * (Q, T )T * , 0 ≤ i ≤ m, be configurations of M . If M does not halt on empty input then v M = λ. Otherwise we set v M = $w 0 $w 1 $w 2 $ • • • $w m $, where w 0 is the initial configuration (q 0 , ), w m is a halting configuration, and w i is the successor configuration of w i-1 , 1 ≤ i ≤ m. Now we define a pattern as P M = {v M } \ {λ}. Proposition 7. Let M be a Turing machine. Then the pattern P M is generated by some cellular automaton in real time.

Basically, Proposition 7 is already the reduction of the problem to decide whether a Turing machine does not halt on empty input to our emptiness problem.

Theorem 8. Given a real-time cellular automaton M , it is not semidecidable whether P (M ) is empty.

Proof. Given an arbitrary Turing machine M , by Proposition 7 we construct a real-time cellular automaton M that generates the pattern P M . Pattern P M is empty if and only if M does not halt on empty input. So, if the emptiness of P (M ) were semidecidable then the problem to decide whether a Turing machine does not halt on empty input would be semidecidable, a contradiction.


Keywords: torsion groups, finite-state automata, subshifts, recursion theory

We construct recursively-presented finitely-generated torsion groups which have bounded torsion and whose word problem is conjunctive equivalent (in particular positive and Turing equivalent) to a given recursively enumerable set. These groups can be interpreted as groups of finite state machines or as subgroups of topological full groups, on effective subshifts over other torsion groups. We define a recursion-theoretic property of a set of natural numbers, called impredictability. It roughly states that a Turing machine can enumerate numbers such that every Turing machine occasionally incorrectly guesses (by either halting or not) whether they are in the set, even given an oracle for a prefix of the set. We prove that impredictable recursively enumerable sets exist. Combining these constructions and slightly adapting a result of [Salo and Törmä, 2017], we obtain that four-headed group-walking finite-state automata can define strictly more subshifts than three-headed automata on a group containing a copy of the integers, confirming a conjecture of [Salo and Törmä, 2017]. These are the first examples of groups where four heads are better than three, and they show the maximal height of a finite head hierarchy is indeed four.

Introduction

In this paper, we combine construction techniques from group theory and recursion theory to verify a conjecture the author and Törmä made in [?] about group-walking automata. The a priori motivation was this conjecture, but the constructions and definitions we give may be of independent interest.

The results

Theorem 1. Let A be Σ 0 1 . Then there exists a recursively presented torsion group with bounded torsion, whose word problem is Turing equivalent to A.

The exact types of reduction are that A many-one reduces to the word problem, and the word problem conjunctively reduces to A.

⋆ Research supported by Academy of Finland grant 2608073211.

Our recursion-theoretic contributions are of a somewhat technical nature (though not particularly difficult). We define a possibly new notion called φimpredictability (Definition 1), which roughly states that a Turing machine can enumerate numbers such that every Turing machine occasionally incorrectly guesses (by either halting or not) whether they are in the set, even given an oracle for a prefix of the set.

Theorem 2. For every total recursive function φ, there exists a φ-impredictable Σ 0 1 set.

We now state our main "navigation-theoretic" contribution. In [?], for a f.g. (finitely-generated) group G and n ∈ N , the class of G-subshifts defined by group-walking finite-state machines with n heads is denoted by S(G, n). See [?] or Section 5 for the definitions. The following is a slight adaptation of a result of [?].

Lemma 1. If G has bounded torsion and has φ-impredictable word problem for fast-enough growing φ, then S(G × Z, 3) S(G × Z, 4).

For example φ = exp • exp • exp • exp • exp is fast enough. By putting the above results together, we obtain that four heads are better than three, as claimed in the title.

Theorem 3. There exists a finitely-generated recursively-presented group G containing a copy of the integers, such that S(G, 3) S(G, 4). See Section 1.3 for some context for this result, and a new conjecture.

Some relevant existing work

The main group-construction result (recursively presented groups with bounded torsion and with a word problem of a prescribed difficulty) uses the idea from [?,?] of groups of finite-state machines. It also uses existing torsion groups as a black-box, in particular it is an application of the deep theory that arose from the Burnside problem [?].

The idea of hiding information into the word problem is of course not a new idea in combinatorial group theory, but we are not aware of it appearing previously in the context of torsion groups. The Dehn monsters from [?], recursively presented groups where no infinite set of distinct elements can be enumerated, seem strongly related. (Our construction cannot be used to produce such groups due to using another group as a black box, but it is possible that their construction can be adapted to produce our result.)

Topological full groups (already on Z) are a well-known source of interesting examples of groups [?,?,?], and our groups can also be interpreted as subgroups of topological full groups of subshifts on torsion groups. In a symbolic dynamics context, [?] (independently) uses a similar construction to prove that the automorphism groups of multidimensional SFTs can have undecidable word problem.

Dan Turetsky showed in the MathOverflow answer [?] that the halting problem is not φ-impredictable for some total recursive φ, and that there exists a Σ 0 1 set which is simultaneously φ-impredictable for all total recursive φ. The latter result of course implies Theorem 2.

Head hierarchies

For context, we state what is now known about the head hierarchies, and state a bold conjecture. See Definition 3 for the definitions.

Theorem 4. For an infinite finitely-generated group G, denote by h(G)

∈ N >0 ∪ {∞} the supremum of n such that S(G, n -1) S(G, n). Then {3, 4, ∞} ⊂ H = {h(G) | G an infinite f.g. group} ⊂ {2, 3, 4, ∞}.
Our contribution is the 4 on the left, which is notable because the maximal finite height is now known.

Proof (Proof sketch). The fact 4 ∈ H follows from Theorem 3. The fact h ∈ H ∩ N =⇒ h ≤ 4 is proved in [?], and the facts 3 ∈ H and ∞ ∈ H are proved in [?] and [?] respectively. The fact 1 / ∈ H is seen as follows: In [?] it is shown that S(Z, 1) S(Z, 2) and the proof easily generalizes to virtually Z groups. On the other hand it is easy to see that the sunny-side-up X ≤1 separates one from four heads, i.e. X ≤1 ∈ S(G, 4) \ S(G, 1), for all f.g. infinite groups G which are not virtually Z, which can be proved using methods of [?] and [?].

We conjecture that four heads are needed if and only if the word problem is undecidable:

Conjecture 1. Let G be a finitely-generated infinite group which is not torsion. Then

-if Z ≤ G and G has decidable word problem, then h(G) = 3, -if Z ≤ G and G has undecidable word problem, then h(G) = 4.
The upper bounds are known, and h(G) = ∞ is known for torsion groups [?]. The first item is the join of conjectures in [?] and [?]. It is known that the sunny-side-up subshift X ≤1 does not prove h(Z) = h(Z 2 ) = 3, as on these groups two heads suffice for it. We do not know any other non-torsion groups where the sunny-side-up requires fewer heads than the above conjecture would suggest.

Settling this conjecture in the positive would not be the end of the story. A more refined invariant than h(G) would be to ask what the precise set of

n such that S(G × Z, n -1) S(G × Z, n) is.
In particular this is of interest when G is a torsion group; [?] only gives an affine function f

(n) ∼ 3n such that S(G × Z, n) S(G × Z, f (n)).
These results are of course about just one way to associate subshift classes to n-headed automata. We believe the results are relatively robust to changes in the definition, but some details are critical. It is in particular open what happens when G is a torsion group and the heads are allowed to communicate over distances, i.e. if they have a shared state.

Preliminaries

For two functions f, g write

f = O(g) (resp. f = Ω(g)) if for some choice of a > 0, f (n) ≤ ag(n) (resp. f (n) ≥ ag(n)) for large enough n. Write f = Θ(g) if f = O(g) and f = Ω(g). Write f ∼ g for f (n)/g(n) → 1. For a, b ∈ N write a | b for "a divides b".
We assume some familiarity with computability/recursion theory, but we state some (not necessarily standard) conventions. We identify partial computable functions with Turing machines, and also their Gödel numbers. Let T ⊂ N be the set of codings of Turing machines which halt on every input, and write P = N for all partial recursive functions. "Recursive" means the same as "computable" and refers to the existence of a Turing machine, which always halts unless the function is explicitly stated to be partial. If χ is a Turing machine, we write χ(p)↓ if χ halts on input p. A partial (not necessarily computable) function from A to B is denoted g : A B. Let us recall some basic definitions of reductions. A set A many-one reduces to a set B if there is φ ∈ T such that n ∈ A ⇐⇒ φ(n) ∈ B. For the following three reductions, we give quantitative versions, so we have a handle on the rate at which reduction happens. The definitions are stated in terms of characteristic sequences, but correspond to their usual meaning.

We say B weakly truth table reduces, or wtt-reduces, to A if there exists g ∈ P and nondecreasing β ∈ T with β(n) → ∞ such that when applied to words as g : {0, 1} * {0, 1} * , if x ∈ {0, 1} N is the characteristic function of A and y that of B, we have that g(w) is defined on prefixes of y, and

w ≺ y =⇒ (g(w) ≺ x ∧ |g(w)| ≥ β(|w|)).
We call β the rate of the reduction.

We say B positively reduces to A if it wtt-reduces to A, for some β ∈ T , with the following additional properties for g: g ∈ T , |g(w)| = β(|w|) for all w, and g is monotone in the sense that u ≤ v =⇒ g(u) ≤ g(v), where ≤ is letterwise comparison. If further g(u) i only depends on whether u ≥ w i,|u| for some w i,|u| computable from i, |u|, then B conjunctively reduces to A.

We say B Turing reduces to A if there is an A-oracle machine that can determine membership in B. Clearly many-one reducibility implies conjunctive reducibility implies positive reducibility implies weak truth table reducibility implies Turing reducibility.

We assume some familiarity with group theory, but state some conventions. Our groups are discrete and mostly finitely-generated. Finitely-generated groups come with a finite generating set, which we usually do not mention. The identity of a group G is denoted by e G (or just e). For words u, v ∈ S * where S is the generating set, write u ≈ G v (or just u ≈ v if G is clear from context) when u and v represent (evaluate to) the same element of G. For g, h ∈ G, write [g, h] = g -1 h -1 gh for the commutator of g and h.

The word problem of a group G is the following subset W ⊂ N: Let S be the fixed symmetric generating set, and order elements of S * (finite words over S) first by length and then lexicographically. Include n ∈ W if the nth word evaluates to the identity of G. Slight inconvenience is caused by linearizing the word problem this way, but on the other hand sticking to subsets of N slightly simplifies the discussion in Section 3. We denote the word problem of G as WP(G) ⊂ N.

If a countable group G acts on a compact zero-dimensional space X, the corresponding topological full group is the smallest group of homeomorphisms g : X → X which contains every homeomorphism g with the following property: there exists a clopen partition (P i ) k i=1 of X and g i ∈ G such that for ∀i ∈ {1, .., k} : ∀x ∈ P i : gx = g i x. It turns out that the group contains precisely such homeomorphisms, i.e. they are closed under composition. One may think of ((P i ) i , (g i ) i ) as a local rule for g.

A group is torsion if all elements have finite order, i.e. G does not contain a copy of the integers. The torsion function of a torsion group is

T G : N → N defined by T G (n) = sup{ord(g) | g ∈ G, |g| ≤ n}
where ord(g) = | g | and |g| is the word norm with respect to the implicit generating set. A group is of bounded torsion if T G (n) = O(1).

In [?] Ivanov shows that the free Burnside group

B(2, 2 48 ) = a, b | ∀w ∈ {a, b, a -1 , b -1 } * : w 2 48 ≈ e
is infinite and has decidable word problem ([?, Theorem A]), and we obtain Lemma 2. There exists a finitely-generated torsion group with bounded torsion and decidable word problem.

The decision algorithm is given in [?, Lemma 21.1]. For a survey on the Burnside problem see [?]. Theorem 3 could be proved using any torsion group with recursive torsion function (e.g. the Grigorchuk group), with minor modifications, as explained after the proof of Theorem 3. Our technical construction results (in particular Theorem 6) are stated and proved without assuming the existence of infinite f.g. groups of bounded torsion, though obviously to obtain Theorem 1 the existence of one is necessary (since it states the existence of one).

We assume some familiarity with symbolic dynamics on groups (see [?] for more information), but state some conventions. If G is a group, and Σ a finite set, Σ G with the product topology and the G-action gx h = x g -1 h is called the full shift, and the actions (g, x) → gx are called shifts. A subshift is a topologically closed subset X satisfying GX = X. A particularly important subshift is the sunny-side-up subshift

X ≤1 = {x ∈ {0, 1} G | g∈G x g ≤ 1}.
Equivalently a subshift is defined by a family of forbidden patterns, i.e. a (possibly infinite) family of clopen sets that the orbit Gx of x may not intersect. If G has decidable word problem then X ⊂ Σ G is effective if there exists a Turing machine that enumerates a family of forbidden patterns which defines the subshift. A cellular automaton on a subshift is a continuous shift-commuting self-map of it.

3 Impredictability

Definition 1. For a function φ, a set A ⊂ N is φ-impredictable if ∃ψ ∈ T : ∀χ ∈ P : ∃ ∞ p : ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p)) ↓ .
To unravel this definition a bit, we want to have a Turing machine ψ which always halts and gives us positions ψ(p) on the number line N so that, for any Turing machine χ, ψ(p) ∈ N is just the halting information about χ on input p, even if χ is allowed oracle access to the first φ(p) bits of A. Since χ is quantified universally, this definition is one way to formalize the idea that it is hard to predict whether ψ(p) ∈ A even given access to the first φ(p) bits of A.

Lemma 3. Let φ ′ , φ ∈ T and φ ′ (n) ≥ φ(n) for all large enough n. Then every φ ′ -impredictable set is φ-impredictable, with the same choice of ψ.

Proof. Let φ, φ ′ ∈ T and suppose A is φ ′ -impredictable. We need to show φimpredictability where φ(n) ≤ φ ′ (n) for all large enough n. Clearly changing finitely many initial values does not change φ-impredictability, so we may assume φ ≤ φ ′ . Let ψ ∈ T be given by φ ′ -impredictability, so

∀χ ∈ P : ∃ ∞ p : ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ ′ (p)) ↓
In particular, we can restrict to χ ∈ P which given (p, w) first cuts off all but at most the first φ(p) ≤ φ ′ (p) symbols of w, and then apply χ. This restriction is

∀ χ ∈ P : ∃ ∞ p : ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p)) ↓,
which is just the definition of φ-impredictability.

Theorem 5. For every φ ∈ T , there exists a φ-impredictable Σ 0 1 set.

Proof. We construct an increasing total computable function ψ, and A will be contained in its image. We want to have

ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p)) ↓
infinitely many times for all χ. The way we construct A is we go through n ∈ N and set either n / ∈ A, or set up the rule n ∈ A ⇐⇒ ξ n ↓ for some Turing machine ξ n whose behavior we describe (informally). We refer to those n ∈ N already considered as determined.

List all partial functions χ in an infinite-to-one way, i.e. we consider functions χ successively, so that each χ appears infinitely many times. When considering χ, we want to determine new values in A so as to make sure that

ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p)) ↓
for at least one new p ∈ N. Suppose we have already determined the first m values of A, i.e. the word w ∈ {0, 1} m such that the characteristic sequence of A will begin with the word w is already determined, and that we have not determined whether n ∈ A for any n ≥ m. The idea is that while we do not know what the word w actually is, there are only 2 m possible choices, and we simply try all of them to get the equivalence above to hold for one new p. To achieve this we will determine whether n ∈ A for some interval of choices n ∈ [m, M ′ ].

Enumerate the words of {0, 1} m as w 0 , w 1 , ..., w 2 m -1 . Now, let p 0 < p 1 < ... < p 2 m -1 be minimal such that φ(p i ) ≥ m for all i. Let M = max j φ(p j ) Set n /

∈ A for all n ∈ [m, M ]. As ψ(p i ) for i ∈ [0, 2 m -1] pick any distinct values greater than M , and determine

ψ(p i ) ∈ A ⇐⇒ χ(p i , w i • 0 φ(pi)-m ) ↓. If w = w i , then for p = p i we have ψ(p) ∈ A ⇐⇒ χ(p i , w i • 0 φ(pi)-m )↓ ⇐⇒ χ(p, A ↾ φ(p))↓,
because the characteristic sequence of A indeed begins with the word w i •0 φ(pi)-m . Thus, we have obtained a new value p = p i at which the statement is satisfied for χ.

For all n that are yet undetermined, but some larger number is determined, we determine n / ∈ A, so that we determine the values in some new interval [m, M ′ ]. We can then inductively continue to the next value of χ. This process determines all values of A, and by construction A is a recursively enumerable set which is φ-impredictable.

Lemma 4. Let A, B ⊂ N and suppose A many-one reduces to B, and B wttreduces to A with rate β.

If A is φ-impredictable, then B is (β • φ)-impredictable.
Proof. Let φ ′ = β • φ. Let f : N → N be the many-one reduction from A to B, and g : {0, 1} * → {0, 1} * the wtt-reduction from B to A with rate β. Since A is φ-impredictable there exists ψ : N → N such that ∀χ ∈ P : ∃ ∞ p : ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p))↓.

Setting ψ ′ = f • ψ, we have, by the definition of f , that

∀χ ∈ P : ∃ ∞ p : ψ ′ (p) ∈ B ⇐⇒ χ(p, A ↾ φ(p))↓.
For χ ∈ P define χ ∈ P as follows: Given (p, w), compute g(w) = u and then evaluate χ(p, u ↾ φ ′ (p)), so that

χ(p, A ↾ φ(p))↓ ⇐⇒ χ(p, g(A ↾ φ(p)) ↾ φ ′ (p))↓,
where we observe that g(A ↾ φ(p)) ↾ φ ′ (p) = B ↾ φ ′ (p) (in particular g indeed halts with an output so the formula makes sense).

Specializing the first quantifier, we have

∀ χ ∈ P : ∃ ∞ p : ψ ′ (p) ∈ B ⇐⇒ χ(p, A ↾ φ(p))↓, equivalently ∀χ ∈ P : ∃ ∞ p : ψ ′ (p) ∈ B ⇐⇒ χ(p, B ↾ φ ′ (p)), so ψ ′ proves that B is φ ′ -impredictable, as desired.
We show that impredictability implies uncomputability.

Proposition 1. If A is Π 0 1 , then A is not φ-impredictable for any φ ∈ T . Proof. Suppose for a contradiction that A is Π 0 1 and is φ-impredictable with φ ∈ T . Let ψ ∈ P be such that

∀χ ∈ P : ∃ ∞ p : ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p)) ↓ .
In particular, this applies to the following χ: given (p, w), we ignore w and if ψ(p) / ∈ A, then χ(p, w) ↓, and otherwise χ(p, w) ↑. This well-defines χ ∈ P since A is Π 0 1 , and for all p ∈ N we have

ψ(p) ∈ A ⇐⇒ χ(p, A ↾ φ(p)) ↑, a contradiction.

Impredictable torsion groups

Definition 2. We define a group K(G, A, H) which depends on a choice of a finitely-generated groups G, H (and choices of generating sets for them, kept implicit), and a set A ⊂ N. First define a subshift on G by

X A = {x ∈ {0, 1} G | g∈G x g ≤ 2,
and k∈{g,h}

x k = 2 =⇒ d(g, h) / ∈ A}
where d : G×G → N is the (left-invariant) word metric. To each g ∈ G associate the bijection

ĝ(x, h ′ ) = (g • x, h ′ ), ĝ : X A × H → X A × H
i.e. the usual shift action in the first component, and to each b ∈ {0, 1} and h ∈ H associate the bijection

h b (x, h ′ ) = (x, h 1-|xe G -b| • h ′ ), h b : X A × H → X A × H
where h 1-|xe G -b| evaluates to e H if x eG = b, and to h otherwise. Define A,H) is finitely-generated, and the implicit generators we use for K are the ones from the definition, with ĝ taken only for g in the generating set of G, and h b only for h in the generating set of H.

K(G, A, H) = {ĝ, h b | g ∈ G, h ∈ H, b ∈ {0, 1}} ≤ Sym(X A × H) Obviously K = K(G,
Remark 1. This group can be interpreted as a group of finite-state machines in the sense of [?] (with obvious nonabelian generalization) when H is finite, by simulating the actions of ĝ by translations of the head, having |H| states, and changing the state by the left-regular action of H (if in the correct clopen set) when h b is applied. Again if H is finite, K can also be interpreted as a subgroup of the topological full group of the G × H-subshift X A × H under the action (g, h) • (x, h ′ ) = (gx, hh ′ ), by having ĝ act by (g, e H ) and having h B act by either (e G , h) or (e G , e H ) depending on x eG .

(where dom(gP ) = gdom(P ) and gP k = P g -1 k ), and for b ∈ {0, 1} and h ∈ H we map

h b (P, h ′ ) = (P, h 1-|Pe G -b| h ′ ),
when e G ∈ dom(P ), and h b (P, h ′ ) = (P, h ′ ) otherwise.

If |w| ≤ n and γ(w) = e G , clearly w ≈ e K if and only if the action of w fixes all P × h where P ∈ L n (X A ), h ∈ H. Naturally, if P ⊃ L n (X A ) and the action fixes (P, h) for all P ∈ P, h ∈ H, then a fortiori w ≈ e K . We can verify this for a particular (P, h) by using the fact H is recursively presented. By the previous lemma, X A is effective, so we can enumerate upper approximations to L n (X A ) which eventually converge. In other words, we eventually obtain the set L n (X A ), and it w ≈ e K , then at this point (at the latest) we can conclude that w indeed acts trivially and halts.

The proof of the first item is similar. To see that there is a wtt-reduction with exponential rate, observe that if we know the first n values of A, then we can determine the legal contents of all G-patterns with domain B n (G) in X A , and using this, and the decidable word problem of H, we can determine whether w ≈ e K for any word with |w| ≤ n. Since we list elements of groups in lexicographic order, the resulting rate β is exponential, as there are exponentially many words w with |w| ≤ n.

To see that this is a conjunctive reduction, we observe that the reduction function g : {0, 1} * → {0, 1} * (computing initial segments of the word problem from initial segments of A) of the previous paragraph can be written uniformly for all sets A so it is total computable, and that we should set g(u) i = 1 if and only if the ith group element acts trivially on the set of patterns not containing elements of A. It can be checked by a terminating computation whether the group element acts nontrivially on some pattern containing only one 1. Our query on A should check that whenever the element acts nontrivially on a pattern with two 1s, then A contains the distance between the 1s of the pattern. This corresponds to checking u ≥ w |u|,i where w |u|,i lists these finitely many bad distances.

Lemma 9. Suppose G has decidable word problem and H is not abelian. Then A many-one reduces to the word problem of K(G, A, H).

Proof. For n ≥ 1, let g n be any effective list of elements of G satisfying |g n | = n (using the fact G has decidable word problem), and consider

g ′ n = [h ′ 1 , h gn 1 ]
where [h ′ , h] = e H (using that H is not abelian) and the action of

h gn 1 = g n h 1 g -1 n is h gn 1 (x, h ′ ) = (x, h 1-|xg n -b| • h ′ )
We have g ′ n ≈ e K if and only if n ∈ A. Namely, if n / ∈ A then g ′ n acts nontrivially on (x, e H ) where x ∈ X A is the unique configuration satisfying x eG = x gn = 1, while if n ∈ A then for all x ∈ X A either x eG = 0 or x gn = 0, and in either case a direct computation shows g ′ n (x, h) = (x, h) for all h ∈ H.

Lemma 10. For any torsion groups G, H, we have

T K(G,A,H) = O(T G T H ). Proof. Let K = K(G, A, H). If w ∈ K with |w| ≤ n, then γ(w) ∈ G with |γ(w)| = m ≤ n. Let k = T G (m) (note that k | T G (n)), so γ(w k ) = γ(w) k = e G .
If w k has order ℓ for all w, then w ℓk = (w k ) ℓ = e K , and thus T K (n) ≤ ℓT G (m), and we have shown

T K = O(T G T H ) as claimed.
So suppose that γ(w) = e G , and consider the action on (x, h) ∈ X A × H. The action of w shifts x around, and based on its contents multiplies h from the right by elements of H. For any fixed x ∈ X A , γ(w) = e G implies that there exists

h x ∈ H with |h x | ≤ |w|, such that w • (x, h) = (x, h x h) for all h ∈ H. Since h x has order at most T H (|h ′ |), and T H (|h ′ |) | T H (|w|), we have w TH (|w|) • (x, h) = (x, h TH (|w|) x h) = (x, h), concluding the proof.
Theorem 6. Let A ⊂ N be Σ 0 1 . For any f.g. torsion group G with decidable word problem there exists a recursively presented torsion group K with T K = Θ(T G ), such that the word problem of K conjunctively reduces to A with exponential rate and A many-one reduces to the word problem of K.

Proof. By the previous lemmas, if K = K(G, A, H) for finitely-generated groups G and H which have decidable word problems, and H is nonabelian with bounded torsion, then -K is recursively presented (Lemma 8), -T K ≥ T G because G ≤ K and by the choice of generators (Lemma 6), -T K ≤ T G T H = O(T G ) (Lemma 10), -WP(K) conjunctively reduces to A with exponential rate (Lemma 8), -A many-one reduces to WP(K) (Lemma 9).

In the previous theorem, the implicit constants for Θ can be taken to be 1 (for the lower bound) and 6 (for the upper bound, by setting H = S 3 ). Of course, if G has bounded torsion, so does K.

Theorem 7. Let φ be a total recursive function. Then there exists a recursively presented torsion group with bounded torsion, whose word problem is φimpredictable.

Proof. Let A be a φ-impredictable Σ 0 1 set (Theorem 5) and apply the previous theorem to obtain a recursively presented torsion group K with bounded torsion, such that the word problem of K conjunctively reduces to A with exponential rate β and A many-one reduces to the word problem of K. Then in particular the word problem of K wtt-reduces to A with exponential rate β. By Lemma 4, the word problem of K is (β • φ)-impredictable. In particular, it is φ-impredictable by Lemma 3.

5 Application: Four heads are better than three

We first define group-walking automata and the subshifts they recognize. By π i we mean the projection to the ith coordinate of a finite Cartesian product. For Q i ∋ 0 a finite set write X 1

Qi for the subshift on a group G clear from context containing those

x ∈ (Q i ∪ {0}) G satisfying |{g ∈ G | x g = 0}| ≤ 1.
Definition 3. Let Σ be a finite alphabet. A k-headed group-walking automaton on the full shift Σ G is a tuple A = ( k i=1 Q i , f, I, F, S), where Q 1 , Q 2 , . . . , Q k are state sets not containing the symbol 0, I and F are finite clopen subsets of the product subshift Y = k i=1 X 1

Qi , and f :

Σ G × Y → Σ G × Y is a cellular automaton satisfying π 1 • f = π 1 and π i (π 2 (f (x, y))) = 0 G ⇐⇒ π i (y) = 0 G for all x ∈ Σ G , y ∈ Y and i ∈ {1, . . . , k}.
For a k-headed automaton A as above, we denote by

S(A) ⊂ Σ G the subshift {x ∈ Σ G | ∀g, h ∈ G, y ∈ I, n ∈ N : h • π 2 (f n (g • x, y)) / ∈ F }.
For k ≥ 1, we denote by S(G, k) the class of all subshifts S(A) for k-headed automata A, and S(G, 0) is the class of all G-SFTs. We also write S(G) = k∈N S(G, k).

This definition may seem cryptic on a first reading. Its details are unraveled in [?] (see [?] for a discussion of possible variants). Our interpretation of X ∈ S(G, k) is that a k-headed group-walking automaton can define X, for a particular (in our opinion natural) way of defining subshifts by such automata.

Key points are that interpreting the ith track of Y as giving the position or a head and its current state, f is a local rule that tells how the heads move on configurations, and the assumptions imply that all heads are always present, are initialized in (roughly) the same position (described by I), have to join together to reject a configuration (described by F ), and cannot communicate over distances (because f is a cellular automaton).

The following observation is essentially Proposition 2 in [?], though here we "complement" the separating subshift, because the result of [?] cannot be used with recursively presented groups.

Lemma 11. Let G be a finitely-generated torsion group, let T (n) = max(n, T G (n)), and suppose that there exists a superexponential function

ζ : N → N such that the word problem of G is (ζ • ζ • T • ζ • T • ζ)-impredictable. Then S(G × Z, 3) S(G × Z, 4).
We sketch the proof from [?], for our complemented definitions.

Proof (Proof sketch). Let ζ be superexponential and recursive, let G be such that the word problem of The crucial observation in [?] was that for any fixed three-headed automaton A, the function (ζ •T •ζ •T •ζ)(p) eventually bounds how far the G-projections of the heads can be from each other during valid runs on a configuration x p , which means that we can construct a Turing machine that, given access to an oracle for the initial segment G ↾ φ(p) of the word problem (we add an extra ζ since we linearize the word problem), we can simulate all runs of A on the configurations x p (observe that there are essentially only p different starting positions that need to be halting if and only if one of them halts (i.e. the finite clopen set F is entered and the configuration is forbidden).

G is φ-impredictable for φ = ζ • ζ • T • ζ • T • ζ,
Suppose for a contradiction that A is a three-headed automaton that defines Y B . Letting χ be the Turing machine described above which simulates A, we have for all large enough p that Remark 2. For maximal "automaticity",1 or to avoid using f.g. bounded torsion groups (whose infiniteness is rather difficult to verify for mortals), one can replace the use of bounded torsion groups by any torsion group with recursive torsion function. For example using the Grigorchuk group as G in the construction of K (then T K (n) ≤ O(n 3 ) by [?, Theorem VIII.70]), and using Theorem 6 directly, the previous proof goes through with the same exponential tower. Automata groups in the sense of [?] cannot have bounded torsion by Zelmanov's theorem [?,?,?].

  and let ψ be the corresponding function, so∀χ ∈ P : ∃ ∞ p : ψ(p) ∼ e G ⇐⇒ χ(p, G ↾ φ(p)) ↓ .For each p ∈ N, let x p ∈ {0, 1} G×Z be the configuration wherex p (g,n) = 1 if and only if n ≡ 0 mod p. Define B = {p ∈ N | ψ(p) ∼ e G },and let Y B ⊂ {0, 1} G×Z be the smallest subshift containing the configurations x p with p ∈ B, i.e. the forbidden patterns are (encodings of) the complement of the word problem of G (together with the recursive set of patterns ensuring Y B ⊂ Y ∅ ). We clearly have x p ∈ Y B ⇐⇒ p ∈ B ⇐⇒ ψ(p) ∼ e G .

  χ(p, G ↾ φ(p))↓ ⇐⇒ x p / ∈ Y Bbut by the definition of ψ there exist arbitrarily large p such thatψ(p) ∼ e G ⇐⇒ χ(p, G ↾ φ(p)) ↓ ⇐⇒ x p / ∈ Y B ⇐⇒ ψ(p) ∼ e G ,a contradiction.On the other hand Y B ∈ S(G × Z, 4) since it is intrinsically Π 0 1 in the sense of [?], by a similar proof as in [?], observing that using an oracle for the word problem of G we can easily forbid all x p with p / ∈ B.Four heads are now seen to be better than three:Proof (Proof of Theorem 3). By Theorem 7, there exists a group G which has bounded torsion and has exp• exp • exp • exp • exp-impredictable word problem. Such a group is (ζ • ζ • T • ζ • T • ζ)-impredictable for some superexponential function ζ, where T (n) = n, and thus the previous lemma implies S(G × Z, 3) S(G × Z, 4).

Using the Grigorchuk group or another torsion automata group, the statement of our main result is somewhat amusing, in that it states that a group of finite-state automata acting on a subshift on an automata group admits subshifts definable by group-walking automata with four heads but not three.

We now prove some important technical properties of these groups, leading up to the proof that they give examples of bounded torsion groups with impredictable word problem.

Lemma 5. If A ′ ⊂ A, the defining action of K(G, A, H) can be seen as a restriction of the action of K(G, A ′ , H) in a natural way, thus K(G, A, H) is a quotient group of K(G, A ′ , H).

Proof. Map generators to generators in the obvious way. The group K(G, A ′ , H) acts on X A ′ × H ⊃ X A × H and the restriction of the action to X A × H is precisely that of K(G, A, H). Thus, all identities of K(G, A ′ , H) are identities also in K(G, A, H).

In particular, the defining action of K(G, A, H) is always a restriction of K(G, ∅, H). Lemma 6. For any G, A, H, there exists a split epimorphism K(G, A, H) → G.

Proof. We have X ≤1 = X N ⊂ X A , so the ĝ-translations act nontrivially on the X A component as the action on X ≤1 is the one-point compactification of the left-regular action of G on itself. Observe also that the X A -component is not modified by any of the maps h b , so the action of K A on this component factors is just the shift action G X A . This gives a homomorphism γ : K(G, A, H) → G, and the map g → ĝ is a section for it.

We refer to γ as the natural epimorphism.

Lemma 7. If WP(G) is decidable and A is Σ 0 1 , then X A is an effective subshift. Proof. Since we can list elements of A, and can compute the distance between given group elements, we can forbid all finite patterns where two 1s appear at g, h with d(g, h) ∈ A.

Lemma 8. If G has decidable word problem and H is recursively presented, then the following statements hold.

-If H has decidable word problem, then the word problem of K(G, A, H) conjunctively reduces to A with exponential rate. ,A,H) and let S be the finite generating set of K. We begin with the proof of the latter item. We need to find a semi-algorithm that, given w ∈ S * , halts if and only if w represents the identity. For this, first consider the natural epimorphism image γ(w) ∈ G. Because G is in particular recursively presented, we can first verify that γ(w) = e G (if not, then also w = e K , and the computation diverges as desired).

Assuming γ(w) = e G , we next check that w acts trivially on all elements of X A × H. We define an action of the free group on generators S on pairs (P, h) ∈ L(X ∅ ) × H by ĝ(P, h ′ ) = (g • P, h ′ ),