Augusto Modanese
email: augusto.modanese@student.kit.edu

Thomas Worsch
email: worsch@kit.edu

Shrinking and Expanding Cellular Automata

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Rosenfeld, Wu and Dubitzki [START_REF] Rosenfeld | Fast Language Acceptance by Shrinking Cellular Automata[END_REF] have introduced so-called shrinking cellular automata.

The idea is that the transition function allows a cell to "delete" itself. If one cell does that, then its both neighbors to the left and right become direct neighbors, and similarly if several cells are deleted (a precise definition will be given in Sect. 2). Rosenfeld and Wu observed that some formal languages can be recognized in less than real-time, using the shrinking process to mimic reductions according to the productions of a context free grammar.

It took more than 30 years before Kutrib et al. [START_REF] Kutrib | Shrinking One-Way Cellular Automata[END_REF] started a more thorough investigation of shrinking CA, explaining relations between shrinking and nonshrinking CA for small time bounds, i. e. real-time and linear time.

It seemed natural to also have a first look at cellular automata which can not only shrink, but also have the opposite ability expand by generating additional cells between already existing ones. As in the shrinking case, at least at first sight, it is only clear how to define this in the one-dimensional case. It turns out that shrinking and expanding CA are quite powerful.

The remainder of this paper is organized as follows. In Section 2 we define shrinking and expanding cellular automata and related notions like the set SX-CAP of problems decidable by SXCA in polynomial time. In Section 3 we relate time complexity of alternating Turing machines to that of SXCA, implying that PSPACE is included in SXCAP. In Section 4 we obtain results showing that in particular SXCAP in included in PSPACE. (Hence SXCA belong to the so-called second machine class [START_REF] Van Emde Boas | Machine Models and Simulations[END_REF].)

This paper is partially based on the bachelor thesis by the first author [START_REF] Modanese | Shrinking and Expanding Cellular Automata[END_REF].

Basics

The set of all integers is denoted Z, the set of all positive integers N + and N 0 = N + ∪ {0}. For two sets A and B the set of all total functions mapping from A to B is denoted B A .

Standard CA

In this paper we are looking at one-dimensional cellular automata with the standard neighborhood N = {-1, 0, 1} of radius 1. Let Q denote the set of states of a single cell.

Then a global configuration is a function c :

Z → Q. The local transition function δ : Q N → Q induces a global transition function ∆ : Q Z → Q Z in the usual way: ∆(c)(x) = δ( c,x ) where c,x : N → Q : n → c(x + n).
A (finite or infinite) computation is a sequence (c 0 , c 1 , . . . ) of configurations such that c t+1 = ∆(c t ) holds for all t.

We will always assume that there is a special state q such that the local transition functions satisfies two properties:

-As long as the cells in the neighborhood of a cell x are all in state q the next state of x is q again, i. e. q is a quiescent state. -A cell which is not in state q will never enter state q in the next step.

We will only look at decision problems. The input for a CA is always a nonempty word w ∈ A + over some finite alphabet A ⊂ Q. The initial configuration of a word w = a 0 • • • a n-1 of length |w| = n with a i ∈ A for all i ≤ |w| is defined as

c w : Z → Q : x → a i , iff 0 ≤ x = i < |w| q, otherwise . (1)
The requirements for q ensure that all configurations reachable from initial configurations c w as just defined all consist of a finite connected block of cells all of which are in a non-quiescent state, extended on both sides with infinitely many cells in state q. Of course the block of non-quiescent cells may grow during a computation.

For the acceptance and rejection of input words we assume that a special state a ("accept") and a special state r ("reject") are present in Q. A configuration c is final iff cell 0 is in the accepting or the rejecting state. The computation (c w = c 0 , c 1 , . . . , c t ) for an input w is halting if c t is final and if c t is the only final configuration in the computation. We call c t the result configuration for w. An input is accepted or rejected iff in the result configuration cell 0 is accepting or rejecting respectively.

The support of a configuration c is the set { x | c(x) = q }. Let C fin denote the set of all configurations c : Z → Q with finite support.

Shrinking and expanding CA

We now have a look at non-standard CA which can shrink by deleting cells "not needed" any longer [START_REF] Rosenfeld | Fast Language Acceptance by Shrinking Cellular Automata[END_REF][START_REF] Kutrib | Shrinking One-Way Cellular Automata[END_REF] and which can expand by generating new cells between already existing ones [START_REF] Modanese | Shrinking and Expanding Cellular Automata[END_REF].

In the present paper the focus is on CA which are allowed to do both during a computation. The following definition of shrinking and expanding CA (SXCA) is adapted to this case.

Besides the set Q of proper states there is a "pseudo state" ⊗. Formally we assume ⊗ / ∈ Q and write Q = Q ∪ {⊗}. In analogy to C fin let Cfin denote the set of all functions c :

Z → Q with having finite support { x | c(x) = q }.
The local transition function δ = (ε, σ) of an SXCA is given by two functions ε : Q N → Q and σ : Q N → Q. Given a configuration c ∈ C fin these induce a global transition of the SXCA defined in two substeps.

-To a given configuration c first ε and σ are applied to each local configuration c,x observed by cell x in c. This gives rise to a function X : C fin → Cfin in the following way. for all x ∈ Z:

X(c)(2x -1) = ε( c,x ) X(c)(2x) = σ( c,x ) (2)
One can imagine that the existing cells are pulled apart by doubling their indices entering the preliminary states σ( c,x ) respectively. To the left of each such cell a "new" cell is generated with preliminary state ε( c,x ). -Secondly, the cells which are in state ⊗ "are removed" and the "remaining cells are renumbered" in the following sense: Given any c ∈ Cfin , define a renumbering

r c : Z → Z 0 → min{ x ≥ 0 | c(x ) ∈ Q } x → min{ x > r c(x -1) | c(x ) ∈ Q }, if x > 0 x → max{ x < r c(x + 1) | c(x ) ∈ Q }, if x < 0 (3)
This induces a function S : Cfin → C fin by

S(c)(x) = c(r c(x)) (4)
Figure 1 shows an example.

The composition ∆ = S • X is the global transition function of the SXCA. CA in the classical definition are a special case, where existing cells are never deleted, i. e. all σ( ) = ⊗, and additional cells are never generated, i. e. all ε( ) = ⊗. Shrinking CA are recovered by again requiring all ε( ) = ⊗ and interpreting ⊗ as the "dissolve" value used in [START_REF] Kutrib | Shrinking One-Way Cellular Automata[END_REF].

The definitions for the notions computation, acceptance, etc., are defined in the same way as for standard CA. The cell in state x deletes itself (left gray cell, σ(b, x, y) = ⊗) and also doesn't generate an additional cell to its left (ε(b, x, y) = ⊗). The cell in state z enters z = σ(y, z, q) and generates a cell in state u = ε(y, z, q) to its left (second gray cell). Cells which are "not needed" are deleted and the remaining ones "renumbered" during the second substep.

c • • • q q q a b x y z q q • • • -5 -4 -3 -2 -1 0 1 2 3 4 X(c) • • • ⊗ a ⊗ b ⊗ ⊗ ⊗ y u z • • • -5 -4 -3 -2 -1 0 1 2 3 4 S(X(c)) • • • q q q a b y u z q q • • • -3 -2 -1 0 1 2 3
The time complexity of an SXCA is the function f : N + → N + where f (n) is the maximum number of steps needed for an input of length n until it is accepted or rejected. The set of problems which can be decided by SXCA with polynomial time complexity will be written SXCAP.

Relating ATM time to SXCA time

Fellah and Yu [START_REF] Fellah | Iterative tree automata, alternating Turing machines, and uniform Boolean circuits: relationships and characterization[END_REF] have shown an intricate close relation between tree-shaped cellular automata (with sequential input at the root) and alternating Turing machines (ATM) [START_REF] Chandra | Alternation[END_REF].

While the repeated generation of additional cells in an SXCA can yield an exponential growth of the number of cells -which superficially looks similar to the exponentially growing number of cells reachable from the root of a treethere is a difference: In a tree the root can quickly broadcast a value in t steps to 2 t cell. On the other hand, in a growing CA a cell (the "root") from which the generation of 2 t cells has been initiated, cannot in t steps broadcast a value to 2 t cells (once the generation process is complete). This seems to increase the complexity of some constructions. Still, we will prove in this section: Theorem 1. An alternating TM with time complexity bounded by some function t(n) can be simulated by an SXCA whose time complexity is O((t(n)) 2 ).

Since alternating time is polynomially related to sequential space [START_REF] Chandra | Alternation[END_REF], one immediately obtains: Corollary 2. PSPACE ⊆ SXCAP, i. e. the set of problems which can be decided by SXCA in polynomial time comprises PSPACE.

[ s ] [ a b c d e f ] Fig. 2. A block storing 6 tape symbols. The head of the ATM is visiting the third square and the ATM is in state s.

[ [ s ] ∃/∀ [ s ] ] [ [ a b c d e f ] [ a b c d e f ] ]
Fig. 3. Two copies of a block storing 6 tape symbols. The head of the ATM is visiting the third square and the ATM is in state s. Two "versions" of state s are used in order to the simulation of the ATM for its two possible continuations. The extra cell between the block remembers whether s is an existential or a universal state.

We now describe a construction proving Theorem 1. We assume the reader is familiar with ATMs.

Let T be an alternating Turing machine with one work tape on which also the input is provided at the beginning of a computation. Furthermore let S denote the set of states, B the set of tape symbols, and A ⊂ B the input alphabet of the ATM. One may assume that in each situation there are exactly two possible continuations for the ATM. We will construct an SXCA C which for each input w ∈ A + checks whether T would accept or reject w and then accepts or rejects w accordingly.

Without loss of generality T never writes blank symbols, and hence there is always one contiguous tape segment with non-blank symbols comprising all (input and) visited squares. The SXCA C uses k consecutive cells to store such segment of length k with symbols a 1 • • • a k , along with a representation of the ATM head being positioned on symbol a p , and the ATM being in state s ∈ S. Each cell stores one symbol, and cell p in addition the state s while the others store a value indicating that the head is not on the respective square. In addition the block is surrounded by two "bracket cells". See Fig. 2 for an example of such a block of the SXCA.

In its very first step, C changes the states storing the input symbols such that the cells represent the corresponding initial ATM configuration (as described above). Afterwards, C iterates the following procedure:

1. New cells are generated to the left of the block and the block contents are copied to it. For each state s of the ATM, the states in both blocks are distinguished by using an unprimed representation s in the left one, and a primed representation s in the right one. 2. Between the blocks an additional cell is used to remember whether the ATM state is an existential or a universal one. The pair of blocks is surrounded by an additional pair of brackets. See Fig. 3. 3. In the left block, the first alternative for the next step of the ATM is simulated, while the second alternative is simulated in the right one. The SXCA can distinguish between the two cases because different representations of the state are used in the two blocks.

4. In each block C checks whether the ATM state is a final one.

-If this is not the case, then C continues with step 1 above.

-If the state is final, C breaks out of the loop for the block and continues with step 5 below. 5. If the ATM state is a final one, then signals are sent in both directions to the nearest enclosing brackets deleting all cells which do not store the state or the brackets. Thus, the block is shrunk to a single cell storing state a or state r. 6. Eventually, an extra cell storing a quantifier will observe final states in both its neighboring cells. It then sends signals in both directions to the nearest enclosing brackets. This causes the deletion of the two cells which contain states, as well as of the ones containing the brackets. The cell itself enters state a or r according to the following rules:

-It enters a in case the quantifier is ∃ and at least one of the neighboring final states was a, or if the quantifier is ∀ and both neighboring final states were a. -Otherwise the cell enters state r.

As long as a configuration is not a final one, the block, inside the brackets, representing it will be replaced by two bracketed blocks and the ∃/∀ marker. The resulting nested hierarchy of brackets will be deleted from the inside out, once final configurations have been reached.

In the end, all non-quiescent cells are deleted except for a single cell, which is in state a or r if and only if the ATM would accept or reject the input, respectively.

It remains to estimate the time complexity of the SXCA. If the ATM is t(n) time-bounded, then, for an input of length n, it will never make more than t(n) steps during a possible computation and hence never visit more than t(n) squares. Therefore, the length of all blocks which have to be copied during step 1 is at most t(n). The simulation of one step of the ATM requires only constant time. Consequently after O((t(n)) 2 ) SXCA steps in every block a final state is reached.

Deleting the non-state cells within a block again only takes time t(n), and this also has to be done t(n) times. Therefore the result of the ATM is available after O((t(n)) 2 ) steps.

Relating SXCA time to TM space

At the beginning of the previous section it has already been pointed out that the (compared to tree CA) somewhat restricted possibilities of communication between cells may manifest themselves in somewhat less efficient simulations of other models by SXCA. On the other hand, the ability to delete a possibly large number of cells simultaneously, until now seems to impede particularly efficient "simulations" of SXCA by other models such as ATM. Instead of elaborating a somewhat arduous ATM, in this section we only exhibit a space efficient approach: Theorem 3. An SXCA whose time complexity is bounded by t(n) can be simulated by a deterministic TM with space complexity bounded by O((t(n)) 2 ).

Together with theorem 1 this implies: Corollary 4. SXCAP = PSPACE, i. e. the set of problems which can be decided by SXCA in polynomial time is exactly PSPACE.

Thus SXCA are a model in the so-called second class [START_REF] Van Emde Boas | Machine Models and Simulations[END_REF].

In order to prove Theorem 3 we first describe an algorithm and discuss its space complexity afterwards. For better readability at some points we have forced page breaks to make sure that pseudo code and corresponding explanations are on the same page.

We proceed "top down", starting with a very simple function, and proceed in three refining steps.

Assuming that there is a function State(cell x, time t) which computes the state of cell x ∈ Z at time t ∈ N 0 , it is trivial to determine whether the SXCA accepts a given input w. One just has to find the first time, when cell 0 enters a final state and check that. See algorithm 1.

finalState returns a or r if the SXCA accepts or rejects an input w, respectively. function final state ← finalState() is t ← 0 repeat t ← t + 1 s ← State(0, t) until s ∈ {a, r} return s end Algorithm 1: Finding the final result of an SXCA.

Next, we describe the process of determining the state of a cell x at time t. The case t = 0 is trivial. For t > 0, it is important to remember how the transition from a configuration c to S(X(c)) was defined in Sect. 2; in particular see Fig. 1. There are two possibilities how a cell z at time t -1, given its state and those of its both neighbors, can give rise to the state of cell x at time t: (i) by changing its own state using σ; or (ii) by generating a new cell using ε. Assume that z, along with a flag new which signals whether x was created using ε or not, can be computed by a function Predecessor(x, t). Then algorithm 2 shows a straightforward way to compute the state of cell x at time t.

Compute the state of cell x at time t:

function state s ← State(cell x, time t) is if t = 0 then Initial configuration for input w: if 0 ≤ x < |w| then return wx the x-th symbol of input w else return q end else (z, new) ← Predecessor(x, t) q-1 ← State(z -1, t -1) q0 ← State(z, t -1) q1 ← State(z + 1, t -1)
if new then cell was "generated" during transition to time t return ε(q-1, q0, q1) else cell already existed return σ(q-1, q0, q1) end end end Algorithm 2: Determining the state of a cell x at time t.

The renumbering of cells was defined earlier by distinguishing between two cell groups: the ones with indices x ≥ 0, and those with indices x < 0. Observe that the renumbering of cells never changes the index of a cell from one group to the other one. Now, consider the case x ≥ 0 first, and assume that there is function Successor(x, t) which, for a cell index x at time t, returns the index z at which the given cell will be located at time t + 1, or ∞ in case the cell is deleted. Then, determining Predecessor(x, t) is a simple matter of counting how many cells z get positioned to the left of x at time t. The case x < 0 is similar; the difference is that one has to count the cells to the right. Using the function sign : Z → Z with sign(0) = 0, and sign(x) = |x|/x otherwise, allows one to write down compact code working for both cases as shown in Algorithm 3.

Compute cell index z such that the states of cells (z -1, z, z + 1) at time t -1 determine the state of cell x at time t; additionally return a flag new indicating whether the cell now at position x is "a new one" or not, i. e. whether ε of σ should be used to compute its state.

function (cell z, bool new) ← Predecessor(cell x, time t) is z ← 0 while true do if Successor(z, t -1) = ∞ ∨ |Successor(z, t -1)| < |x| then z ← z + sign(x) end end if x = Successor(z, t -1) then return (z, false) else
this can only happen if cell x was generated from t -1 to t return (z, true) end end Algorithm 3: Counting how many cells existing at time t -1 get indices "closer to 0" than cell z.

Finally, the space complexity of the above algorithm has to be determined depending on the length n = |w| of the input. Let t(n) be the time complexity of the SXCA. First of all, one observes that, inside finalState, there will be calls to State for all t from 0 to t(n). This requires a counter which uses log t(n) space.

Secondly, the functions State, Predecessor and Successor all have a parameter time t, and they call themselves recursively in such a way that at least on every second recursion the time parameter is decreased by 1. Hence the number of recursion levels is bounded by 2t(n).

It remains to determine the space needed on each recursion level in any of the three functions. In all of them,q a constant number of cell indices have to be stored. Since the number of non-quiescent cells can only grow from k to 2(k + 2) in a single global step, from an initial configuration with n ≥ 2 cellscan, after t(n) steps, give rise to at most n • 4 t(n) non-quiescent cells. O(t(n)) bits suffice for storing the index of any cell in this resulting configuration.

Therefore the total space complexity of the above algorithm is bounded by O((t(n) 2 ).

Conclusion and Outlook

We have proven that space complexity of Turing machines and time complexity of shrinking and expanding cellular automata are polynomially related. In the construction we made use of both shrinking and expanding, but only in a somewhat restricted way: During a first part of the computation the CA was only expanding, and during the second part only shrinking.

It is still an open problem to exactly characterize the set of problems which, for example, can be decided by polynomial time cellular automata which can only expand, but not shrink. The results may depend on the precise definition of acceptance for XCA.

Fig. 1 .

 1 Fig. 1. The two substeps of a global transition of an SXCA: The cells in states a, b and y should enter states a = σ(q, a, b), b = • • • and y = • • • respectively withoutgenerating an additional cell to their left (ε(q, a, b) = ⊗, . . . ). The cell in state x deletes itself (left gray cell, σ(b, x, y) = ⊗) and also doesn't generate an additional cell to its left (ε(b, x, y) = ⊗). The cell in state z enters z = σ(y, z, q) and generates a cell in state u = ε(y, z, q) to its left (second gray cell). Cells which are "not needed" are deleted and the remaining ones "renumbered" during the second substep.

Finally, Successor(x, t) has to be described; see algorithm 4 on the next page. Roughtly speaking, this is again a simple counting procedure: For every cell "between 0 and up to, but excluding x itself", one simply counts whether it gives rise to 0, 1 or 2 cells at time t + 1. After the trivial cases (cell x is deleted, or x = 0) have been handled, the consequences of the actions of cell 0 are taken into account. Before the while loop is started, i is the number of the first cell = 0 in the direction of cell x, and z is already the correct value to be returned in case none of the cells i, . . . , x -sign(x) lead to states = ⊗. Subsequently, z is increased/decreased (depending on which side of 0 is considered) when required.

Now, consider all cells from i up to, but excluding x, and count how many non-⊗ cells they amount to

Algorithm 4: Counting how many cells are generated from t to t + 1 which are "closer to 0" than cell x.


Kenichi Morita
email: km@hiroshima-u.ac.jp

An 8-State Simple Reversible Triangular Cellular Automaton That Exhibits Complex Behavior

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A three-neighbor triangular cellular automaton (TCA) is a one whose cell is regarded as being triangular-shaped, and communicates with its three neighbor cells. Here, we use the framework of triangular partitioned cellular automata (TPCAs) [START_REF] Imai | A computation-universal two-dimensional 8-state triangular reversible cellular automaton[END_REF], where each cell is divided into three parts, and each part has its own state set. TPCAs are a subclass of TCAs where the state set of a cell is the Cartesian product of the sets of the three parts. In a TPCA, the next state of a cell is determined depending only on the three adjacent parts of the neighbor cells (not depending on the states of the whole three neighbor cells). Such a framework is useful for designing reversible TCAs.

We define an elementary TPCA (ETPCA) as a TPCA such that each part of a cell has only two states (hence a cell has eight states), and its local transition function is isotropic (i.e., rotation-symmetric). There are 256 ETPCAs in total, and there are 36 reversible ETPCAs (RETPCAs). ETPCAs are extremely simple, since each of their local functions is described by only four local rules. But, they still show interesting behavior as in the case of one-dimensional elementary cellular automata (ECAs) [START_REF] Wolfram | Theory and Applications of Cellular Automata[END_REF][START_REF] Wolfram | A New Kind of Science[END_REF]. In [START_REF] Imai | A computation-universal two-dimensional 8-state triangular reversible cellular automaton[END_REF], it is shown that the RETPCA with the identification number 0157 (explained later) is computationally universal.

In this paper, we investigate a specific RETPCA T 0347 having the identification number 0347. It somewhat resembles Game-of-Life CA [START_REF] Gardner | Mathematical games: The fantastic combinations of John Conway's new solitaire game "life[END_REF][START_REF] Gardner | Mathematical games: On cellular automata, self-reproduction, the Garden of Eden and the game "life[END_REF][START_REF] Berlekamp | Winning Ways for Your Mathematical Plays[END_REF], and exhibits interesting behavior. In particular, there exist a glider and glider guns. The glider in T 0347 is a moving object with period 6. There are glider guns that generate gliders in three directions as well as in one direction. There is also a gun that generates gliders to the negative time direction. We can compose right-turn, Uturn, and left-turn modules out of stable blocks, which can change the moving direction of a glider. It is also possible to change the direction of a glider by colliding another glider appropriately. Based on these basic operations, we can implement gate modules that simulate reversible logic gates in the cellular space of T 0347 . By this, computational universality of T 0347 is concluded.

Elementary triangular partitioned cellular automata

In this section, we give definitions on elementary triangular partitioned cellular automata (ETPCAs), their reversibility, and some related notions.

A partitioned cellular automaton (PCA) is a subclass of a standard CA, where a cell is divided into several parts, and each part has its own state set. The next state of a cell is determined by the states of the adjacent parts of the neighboring cells. Figure 1 shows the case of a two-dimensional three-neighbor triangular PCA (TPCA). A local function of a TPCA is specified by a set of local rules of the form shown in Fig. 1 (b). Applying it to all the cells in parallel, a global function, which gives a transition relation among configurations, is obtained. Hereafter, we consider only deterministic PCAs.

We say a PCA is locally reversible if its local function is injective, and globally reversible if its global function is injective. It is known that global reversibility and local reversibility are equivalent (Lemma 1). Thus, such a PCA is simply called a reversible PCA (RPCA). Note that, in [START_REF] Morita | Computation universality of one-dimensional reversible (injective) cellular automata[END_REF], the lemma is given for one-dimensional PCAs, but it is easy to extend it for two-dimensional PCAs.

Lemma 1. [11]

A PCA A is globally reversible iff it is locally reversible.

By this lemma, to obtain a reversible CA, it is sufficient to give a locally reversible PCA. Thus, the framework of PCA makes it easy to design reversible CAs. A TPCA is called isotropic (or rotation-symmetric), if, for each local rule, the rules obtained by rotating the both sides of it by a multiple of 60 • exist. Note that, if a TPCA is isotropic, then all three parts of a cell must have the same state set. In the following, we study only isotropic TPCAs. An 8-state isotropic TPCA is called an elementary TPCA (ETPCA). Thus, each part of a cell has the state set {0, 1}. ETPCAs are the simplest ones among two-dimensional PCAs. But, this class still contains many interesting PCAs as in the case of one-dimensional elementary CAs (ECAs) [START_REF] Wolfram | Theory and Applications of Cellular Automata[END_REF][START_REF] Wolfram | A New Kind of Science[END_REF].

r 3 r 2 r 1 - s 3 s 2 s 1 (a) (b)
Since ETPCA is isotropic, and each part of a cell has only two states, its local function is defined by only four local rules. Hence, an ETPCA can be specified by a four-digit number wxyz such that w, z ∈ {0, 7} and x, y ∈ {0, 1, . . . , 7} as shown in Fig. 2. Thus, there are 256 ETPCAs. Note that w and z must be 0 or 7 because ETPCAs are isotropic and deterministic. The ETPCA with the identification number wxyz is denoted by T wxyz .

w : A reversible ETPCA is denoted by RETPCA. It is easy to see the following.

- 0 | • • • 7 x : • - 0 | • 1 | • 2 | • • 3 | • 4 | • • 5 | • • 6 | • • • 7 y : • • - 0 | • 1 | • 2 | • • 3 | • 4 | • • 5 | • • 6 | • • • 7 z : • • • - 0 | • • • 7
An ETPCA T wxyz is reversible iff (w, z) ∈ {(0, 7), (7, 0)} ∧ (x, y) ∈ {1, 2, 4}×{3, 5, 6} ∪ {3, 5, 6}×{1, 2, 4} Let T wxyz be an ETPCA. We say T wxyz is conservative (or bit-conserving), if the total number of particles (i.e., •'s) is conserved in each rule. Thus, the following holds. Note that, if an ETPCA is conservative, then it is reversible.

An ETPCA T wxyz is conservative iff w = 0 ∧ x ∈ {1, 2, 4} ∧ y ∈ {3, 5, 6} ∧ z = 7

RETPCA T 0347 and its properties

Here, we focus on a specific RETPCA T 0347 , and investigate its properties. Its local function is given in Fig. 3. It is a non-conservative RETPCA. We shall see that there are many patterns (i.e., segments of configurations) that show interesting behavior as in the case of Game-of-Life CA [START_REF] Berlekamp | Winning Ways for Your Mathematical Plays[END_REF][START_REF] Gardner | Mathematical games: The fantastic combinations of John Conway's new solitaire game "life[END_REF][START_REF] Gardner | Mathematical games: On cellular automata, self-reproduction, the Garden of Eden and the game "life[END_REF]. In Section 4, some of them will be used to construct reversible logic gates in T 0347 . In [START_REF] Morita | A reversible elementary triangular partitioned cellular automaton that exhibits complex behavior (slides with simulation movies[END_REF], evolving processes of various configurations of T 0347 can be seen by movies.

-0 ,

• - • • 3 , • • - • 4 , • • • - • • • 7 Fig. 3.
Local function of the non-conservative RETPCA T0347

Glider, block, fin, and rotator in T 0347

The most useful object in T 0347 is a glider (Fig. 4). It swims in the cellular space like a fish (or an eel). It travels a unit distance, the side-length of a triangle, in 6 steps. By rotating it appropriately, it can move in any of the six directions.

t = 0 • • • • •• t = 1 • • •• • • t = 2 • • • •• • t = 3 •• • • • • t = 4 • • • • • • t = 5 • • • • • • t = 6 • • • • •• Fig. 4.
Movement of a glider. The glider patterns at time t = 0, . . . , 5, and 6 are said to be of phase 0, . . . , 5, and 0, respectively.

A block is an object shown in Fig. 5 (a) or (b). It does not change its pattern if no other object touches it. In this sense, it is a stable pattern. There are two kinds of blocks, i.e., type I (Fig. 5 (a)) and type II (Fig. 5 (b)). As explained in Subsect. 3.2, an appropriate type of a block must be used when colliding a glider with it. Combining several blocks, right-turn, U-turn, and left-turn of a glider will be implemented. A fin is an object that simply rotates as in Fig. 6 with period 6. It can also travel around a block (Fig. 7), or a sequence of blocks (Fig. 8) clockwise.

• •• • • • • • • • • • • • • •• • (a) (b)
A rotator is an object shown in Fig. 9. Like a fin, it rotates around some point, and its period is 42.

t = 0 • • • t = 1 • • • t = 2 • •• t = 3 • • • t = 4 • • • t = 5 •• • t = 6 • • •
Fig. 6. A fin that rotates around the point indicated by

• t = 0 • • • • •• • • • • • • t = 1 • • •• • • • • • • • • t = 2 • • •• • • • • • • • • t = 3 • • • • • • • • • t = 4 • • •• • • • • • • • • t = 5 • • • •• • • • • t = 6 • • •• • • • • • • • •• • • t = 7 • • • • • • • • • t = 8 • • •• • • • • • •• • • •• t = 9 • • • • • • • • • t = 10 • • •• • • • •• • • • t = 11 • •• • • • • • • t = 12 • •• • • • •• • • • • t = 13 • •• • • • • • • • • • t = 14 • •• • • • • • • • •• Fig. 7.
A fin can travel around a block clockwise. It takes 42 steps to return to the initial position. Note that the block changes its pattern transiently, but it becomes the initial pattern again at t = 14.

t = 0 • • • • • • •• • • •• • • • • • • • • • •• • • • • • • • t = 25 •• • • • • • • • •• • • •• • • • • • • • •• • • • • • • t = 50 • • • • • • • • • •• • • •• • • • • • • • •• • • • • • • Fig. 8.
A fin travelling along a sequence of blocks

t = 0 •• • • • • t = 1 • • • • • • t = 2 •• • • • • t = 3 • • • • •• t = 4 • • • t = 5 • •• t = 6 • •• t = 7 • • •• • • Fig. 9.
A rotator that moves around the point indicated by •. Its period is 42.

Changing the move direction of a glider by blocks

We now make several experiments of colliding a glider with blocks. First, we collide a glider with a single block. We put a glider that moves eastward, and a block of type I as shown in Fig. 10 (t = 0). At t = 12 they collide. Then, the glider is split into a body (i.e., a rotator) and a fin, and the body begins to rotate around the point indicated by • (t = 16). The fin travels around the block (t = 38). When it comes back to the original position, it interacts with the body (t = 50). By this, the rotation center of the body is shifted upward by two cells, and the fin travels around the block once more (t = 61). At t = 94, the body and the fin meet again to reconstruct a glider. Finally, the glider goes westward (t = 97). By above, backward-turn of the glider is realized.

In the above process, if we use a type II block instead of a type I block, then the glider goes to the north-east direction, but the block cannot be re-used, since some garbage remains (Fig. 11). Therefore, an appropriate type of block should be used depending on the coming direction of the glider. Figure 12 shows the allowed input positions of a glider in each type of a block.

t = 0 • • • • ••• • •• • •• • • t = 12 • • • • ••• • •• • •• • • t = 16 • • • • • • • •••• • • • •••• • •• t = 38 ••• • • • • • •• • • • • • • • • t = 50 • • • • • • ••• • • • • • •• • • t = 61 •• • • •• • • • • • • • • • t = 94 • • • • ••• • •• • •• • • t = 97 •• ••• • • • • • • •• • •
t = 0 • • • • • • •• • •• • ••• t = 12 • • • •• • •• • ••• t = 20 • • • • • • •• • • • • • •• t = 28 • • • • • • • • • • • • • • • • •• Fig. 11.
If we collide a glider moving eastward with a type II block, garbage remains Next, we collide a glider with two blocks (Fig. 13). As in the case of one block (Fig. 10), the glider is split into a rotator and a fin (t = 56). The fin travels around the blocks three times without interacting with the rotator. At the end of the fourth round, they meet to form a glider, which goes to the south-west direction (t = 334). Hence, two blocks act as a right-turn module.

• •• • • • • • • • • • • • • •• • (a) (b)
Figures 14 and15 show that three blocks and five blocks also act as rightturn modules. They have shorter delays than the case of two blocks. Note that, as in Fig. 15, blocks need not be placed in a straight line. Namely, the sequence of blocks can be bent slightly. But, if we do so, an appropriate type of a block must be used at each position. Otherwise, blocks will be destroyed.

If we collide a glider with a sequence of four, six, or seven blocks, then they will be destroyed. On the other hand, a sequence of eight blocks acts as a backward-turn module like one block, and that of nine blocks acts as a right-turn module like two blocks. Generally, a sequence of n + 7 blocks (n > 0) shows a similar behavior as that of n blocks though the total delay is longer. The reason is as follows. The period that the fin goes around the n+7 blocks is 36(n+7)+6. Thus, when the fin comes back, the phase of the rotator becomes the same as in the case of n blocks, since the period of a rotator is 42, and 36 × 7 is a multiple of 42. A U-turn module is given in Fig. 16. Also in this case, the glider is first split into a rotator and a fin (t = 36). But, slightly before the fin comes back to the start position, it meets the rotator, and a glider is reconstructed, which moves westward (t = 113). Note that, here the output path is different from the input path, while in the backward-turn module they are the same (Fig. 10).

t = 0 • • • • ••• • ••• • •• • •• • • • •• • • t = 56 • • • •••• • ••• • •• • • • •••• • • •• • • • •• t = 334 ••• • ••• • • •• • • • •• • • • • • • •• Fig. 13. 120 • -right-turn module composed of two blocks t = 0 • • • • ••• • ••• • ••• • •• • •• • • • •• • • • •• • • t = 250 ••• • ••• • ••• • • •• • • • •• • • • •• • • • • • • •• Fig. 14. Right-turn module composed of three blocks t = 0 • • • • ••• • • • •• • •• • •• • • • ••• • • •• • ••• • ••• • • ••• • •• • • • •• • • t = 208 ••• • • • •• • • •• • • • ••• • • • • • •• • ••• • ••• • • • ••• • •• • • • •• • • ••
Figure 17 shows a left-turn module. It is more sophisticated than the rightturn and U-turn modules. The glider is split into a rotator and a fin as before. The fin first travels outside of the module, and then inside. But, around the middle of the module it meets the rotator. A glider is reconstructed from them, and it moves to the north-west direction (t = 366).

It is also possible to make a 60 • -right-turn module as in Fig. 18. First, the input glider makes 120 • -right-turn by the three blocks (t = 250). Next, the glider is reflected by the left-side block. Finally, it makes 120 • -right-turn again by the three blocks (t = 585). This mechanism is also used as an interface between a bidirectional signal path and unidirectional signal paths as shown in Fig. 19. 19. Interface between a bidirectional signal path, and unidirectional signal paths Table 1 shows the net delay d (i.e., the additional delay caused by the module) and the phase shift s of each turn module. Here, the relation s = (-d) mod 6 holds. In the case of Fig. 13, we can regard the travelling distance of the glider from t = 0 to 334 is 5. Since the speed of a glider is 1/6, d = 334-5/(1/6) = 304. Combining these turn modules, we can control the moving direction of a glider freely. It is also possible to shift the phase of a glider. For example, by making right-turn (120 • ) and then left-turn (120 • ), its phase is shifted by 2.

t = 0 ••• • • • • • ••• • • •• • • •• • •• • • • • •• • ••• • • ••• • •• • • ••• • • •• • • t = 36 • • • ••• • ••• • • •• • • • • • •• • • • • •• • • • ••• • • ••• •• • •• • • ••• • • •• • • t = 113 ••• • ••• • • •• • • • •• • • • • •• • •• ••• • • ••• • • • • • •• • • ••• • • •• • • Fig. 16. U-turn module t = 0 • • • • ••• • •• • •• • • • • •• • • • •• • ••• • • ••• • ••• • •• • • ••• • • • •• • ••• • • • •• • • •• • • • ••• • •• • • • ••• • • •• • ••• • • • •• • ••• • • ••• • •• • • • ••• • •• • • t = 366 • • • • • • • •• • • •• • • • • •• • • • •• • ••• • • ••• • ••• • •• • • ••• • • • •• • ••• • • • •• • • •• • • • ••• • •• • • • ••• • • •• • ••• • • • •• • ••• • • ••• • •• • • • ••• • •• • • Fig. 17. 120 • -left-turn module t = 0 • • • • • • • • •• • ••• • ••• • ••• • • ••• • •• • • • •• • • • •• • • t = 250 • • •• • •• ••• • ••• • ••• • • ••• • • • • • •• • • • •• • • • •• • • t = 585 • • •• • ••• • ••• • ••• • • ••• • •• • • • •• • • • •• • • • • • • ••
••• • ••• • ••• • • •• • • • •• • • • •• • • Fig.

Glider guns in T 0347

A glider gun is a pattern that generates gliders periodically as the one in Gameof-Life [START_REF] Gardner | Mathematical games: On cellular automata, self-reproduction, the Garden of Eden and the game "life[END_REF]. In the RETPCA T 0347 , it is very easy to create a three-way glider gun. As shown in Fig. 20, it is obtained by colliding a glider with a fin. Interestingly, there is a glider absorber in T 0347 (Fig. 21). It absorbs three gliders every 24 steps, and finally produces a fin and a glider. It is considered as a "backward glider gun" that generates gliders to the negative time direction.

t = 0 • • • • •• • • • t = 96 • • • • •• • • • • •• • • • • • • • • • • • • • • • • • • •• • • • • • •• •• •• • • • • • • • • • • • • • • • • •
= -96 • • • • • • • • • • • • • • • • • • • • • •• • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • t = 0 • • • • • • • • • Fig. 21.
Glider absorber. It is considered as a glider gun to the negative time direction.

There is another way of composing a glider gun. Figure 22 shows that three gliders are generated by the head-on collision of two gliders. Based on this mechanism, we can design a one-way glider gun as shown in Fig. 23, where two of the three generated gliders are re-used to generate the next three.

t = 0 •• •• • • • • • • • • t = 30 •• • • • • • • • • • • • • • • • •
• • •• • • • •• • • ••• • ••• • • •• • • • •• • • ••• • ••• ••• • • • •• • • • •• • ••• • • •• • • • ••• • ••• • •• • • ••• • • • •• • • • •• • ••• • ••• • • •• • • • ••• • ••• • •• • • • •• • • ••• • • • •• • • • •• • ••• • • • •• • • •• • • • ••• • ••• • •• • • • ••• ••• • • •• • • • • •• • ••• • • • •• • • ••• • •• • • • ••• • • •• • ••• • • • •• • • ••• • •• • • • ••• • • •• • • • •• • •• •• ••• • • ••• • ••• • • • • • • • • • •• • • • • •• • • • •• • ••• • • • •• • • ••• • ••• • •• • • • ••• • • •• • ••• • • • •• • ••• • ••• • • • •• • • ••• • •• • • • ••• • •• • • ••• • • •• • • ••• • • ••• • • •• • • • •• • ••• • • •• • • • •• • • • • •• • • ••• • ••• • •• • • • • •• • ••• • • ••• • ••• • •• • • • • •• • ••• • • ••• • •• • • ••• • • •• • •

Making switch gate and inverse switch gate modules in T 0347

We show a switch gate and an inverse switch gate can be implemented in T 0347 using gliders as signals. The operation of a switch gate is realized by colliding two gliders as shown in Fig. 25. It is important that, in this collision, the glider from the input port c travels to the south-east direction with no delay even though it interacts with the glider from x (hence its phase is not shifted also).

t = 0 c x • • • • • • • • •• • • t = 24 c x • • • • • • • • •• • • t = 48 c x cx cx c • • • • • • • • • • • •

Fig. 25. Switch gate operation realized by collision of two gliders

Here, we implement a switch gate as a "gate module" in the standard form. Otherwise, adjustment of signal timing, in particular, adjustment of the phase of a glider becomes very cumbersome when designing a larger circuit. A gate module is a pattern embedded in a rectangular-like region in the cellular space that satisfies the following (Fig. 26): (1) It realizes a reversible logic gate. [START_REF] Berlekamp | Winning Ways for Your Mathematical Plays[END_REF] Input ports are at the left end. (3) Output ports are at the right end. (4) Delay between input and output is constant and a multiple of 6. Figure 27 shows a switch gate module. The delay in this module is 2232 steps. An inverse switch gate module is implemented in a similar manner as shown in Fig. 28. It is a "quasi-mirror-image" of the switch gate module. The positions of the blocks are just the mirror images of those in the switch gate. But, each block is replaced by the other type of the corresponding block (not by the mirror image of the block). The delay between input and output is also 2232 steps.

Gate module Input

If we use only 120 • -right-turn modules (Table 1) to connect gate modules, then there is no need of adjusting the phases of gliders. This is because the phase shift becomes 0, if we make 120 • -right-turns three times. In this way, we can construct a larger circuit easily. Thus, we have the following theorem.

Theorem 1. The RETPCA T 0347 with infinite (but ultimately periodic) configurations is Turing universal.

Concluding remarks

Among 256 ETPCAs, we studied a specific reversible ETPCA T 0347 . In spite of its extreme simplicity of the local function and the constraint of reversibility, T 0347 shows interesting behavior. Here, a glider plays the key role in T 0347 . By placing blocks appropriately, trajectory and the phase of a glider can be completely controlled. Logical operation is also performed by interacting gliders. In this way, Turing universality of T 0347 with infinite configurations was proved.

On the other hand, it is an open problem whether there is a universal constructor in T 0347 , which can build any pattern in some specified class of patterns (e.g., the class of all patterns consisting of blocks). It is also not known whether universal systems (such as reversible Turing machines, reversible counter machines, or some others) are simulated in the finite configurations of T 0347 .

Besides T 0347 , it has already been shown that the conservative RETPCA T 0157 with infinite configurations is Turing universal [START_REF] Imai | A computation-universal two-dimensional 8-state triangular reversible cellular automaton[END_REF], where a single particle rather than a glider is used to represent a signal. It is left for the future study to find other ETPCAs that are universal.

Fig. 1 .

 1 Fig. 1. A three-neighbor triangular PCA. (a) Its cellular space, and (b) a local rule.

Fig. 2 .

 2 Fig. 2. Representing an ETPCA by a four-digit number wxyz, where w, z ∈ {0, 7} and x, y ∈ {0, 1, . . . , 7}. The states 0 and 1 are represented by a blank and •, respectively. Vertical bars indicate alternatives of a right-hand side of a rule.

Fig. 5 .

 5 Fig. 5. Blocks of (a) type I and (b) type II. They are stable patterns.

Fig. 10 .

 10 Fig. 10. Colliding a glider with a type I block. It works as a backward-turn module.

Fig. 12 .

 12 Fig. 12. Allowed input positions for (a) the type I block, and (b) the type II block

Fig. 15 .

 15 Fig. 15. Right-turn module composed of five blocks, which are not linearly placed

Fig. 18 .

 18 Fig. 18. 60 • -right-turn module composed of four blocks

Fig. 20 .

 20 Fig. 20. Three-way glider gun. It generates three gliders every 24 steps.

  t

Fig. 22 .

 22 Fig. 22. Generating three gliders by the head-on collision of two gliders

Fig. 23 .

 23 Fig. 23. One-way glider gun. It generates a glider every 1422 steps.

Fig. 26 .

 26 Fig. 26. Gate module in the standard form

Table 1 .

 1 Net delay and phase shift of the seven turn modules

	Module	Net delay d Phase shift s
	Backward-turn	73	+5
	Right-turn (120 • ) by 2 blocks	304	+2
	Right-turn (120 • ) by 3 blocks	220	+2
	Right-turn (120 • ) by 5 blocks	178	+2
	U-turn	77	+1
	Left-turn (120 • )	342	0
	Right-turn (60 • ) by 4 blocks	513	+3

Acknowledgement. This work was supported by JSPS KAKENHI Grant Number 15K00019.

T 0347 is computationally universal

In this section, we show Turing universality of T 0347 , i.e., any Turing machine can be simulated in it.

Showing Turing universality of reversible CA

To prove Turing universality of a reversible CA, it is sufficient to show that any reversible logic circuit composed of switch gates (Fig. 24 (a)), inverse switch gates (Fig. 24 (b)), and delay elements can be simulated in it (Lemma 6). Lemma 6 can be derived, e.g., in the following way. First, a Fredkin gate (Fig. 24 (c)) can be constructed out of switch gates and inverse switch gates (Lemma 2). Second, any reversible sequential machine (RSM), in particular, a rotary element (RE), which is a 2-state 4-symbol RSM, is composed only of Fredkin gates and delay elements (Lemma 3). Third, any reversible Turing machine is constructed out of REs (Lemma 4). Finally, any (irreversible) Turing machine is simulated by a reversible one (Lemma 5). Thus, Lemma 6 follows. Note that the circuit that realizes a reversible Turing machine constructed by this method becomes an infinite (but ultimately periodic) circuit.

Lemma 2. [3]

A Fredkin gate can be simulated by a circuit composed of switch gates and inverse switch gates, which produces no garbage signals.

Lemma 3. [8] Any RSM (in particular RE) can be simulated by a circuit composed of Fredkin gates and delay elements, which produces no garbage signals.

Lemma 4. [START_REF] Morita | A simple reversible logic element and cellular automata for reversible computing[END_REF] Any reversible Turing machine can be simulated by a garbage-less circuit composed only of REs.

Lemma 5. [1] Any (irreversible) Turing machine can be simulated by a garbageless reversible Turing machine.

Lemma 6. A reversible CA is Turing universal, if any circuit composed of switch gates, inverse switch gates, and delay elements is simulated in it.

So far, Turing universality of several reversible two-dimensional CAs has been shown in this way. They are the 2-state reversible block CA model by Margolus [START_REF] Margolus | Physics-like model of computation[END_REF], the two models of 16-state reversible PCAs on square grid by Morita and Ueno [START_REF] Morita | Computation-universal models of two-dimensional 16-state reversible cellular automata[END_REF], and the conservative RETPCA T 0157 by Imai and Morita [START_REF] Imai | A computation-universal two-dimensional 8-state triangular reversible cellular automaton[END_REF].


Andrew Winslow
email: awinslow@ulb.ac.be

A Brief Tour of Theoretical Tile Self-Assembly

The author gives a brief historical tour of theoretical tile self-assembly via chronological sequence of reports on selected topics in the field. The result is to provide context and motivation for the these results and the field more broadly.

Introduction. This tour covers only a subset of the research topics in theoretical tile self-assembly. It is intended for readers who are familiar with the basics of the field and wish to obtain a better understanding of how the multitude of models, problems, and results relate. As such, it is neither a survey nor an introduction; for these, the reader is referred to the excellent works of Doty [START_REF] Doty | Theory of algorithmic self-assembly[END_REF], Patitz [START_REF] Patitz | An introduction to tile-based self-assembly[END_REF], Woods [START_REF] Woods | Intrinsic universality and the computational power of self-assembly[END_REF], and Winfree [START_REF] Winfree | Algorithmic Self-Assembly of DNA[END_REF]. Moreover, it does not cover work in experimental DNA tile self-assembly.

The aTAM of Winfree (1990s). It is common for work on theoretical tile self-assembly (hereafter tile assembly), to begin "In his Ph.D. thesis, Winfree [START_REF] Winfree | Algorithmic Self-Assembly of DNA[END_REF] introduced the abstract tile assembly model (aTAM) . . . ". The ubiquity of this opener matches the importance this work plays in the field: it is the point of conception, and nearly 20 years later, its reading connotes initiation to the area. Moreover, the sustained popularity of tile assembly is due in large part to the elegance and hidden intricacy of this original model. Such intricacy is perhaps most crystallized in a simple yet devious question: is universal computation possible in the aTAM at temperature 1?

As with any research, the concept of the aTAM and its experimental implementations were not in isolation. Several other models of (linear) DNA-based computation also introduced around this time, including the filtering-based models of Adleman [START_REF] Adleman | Molecular computation of solutions to combinatorial problems[END_REF] and Beaver [START_REF] Beaver | A universal molecular computer[END_REF] and the splicing systems of Pâun, Kari, Yokomori, and others [START_REF] Freund | Dna computing based on splicing: the existence of universal computers[END_REF][START_REF] Pâun | On the power of the splicing operation[END_REF][START_REF] Yokomori | Dna-ec: a model of dna computing based on equality checking[END_REF].

Benchmark Problems (2000)(2001)(2002)(2003)(2004). Beyond defining the aTAM, the Winfree thesis also contains a proof of the computational universality of the aTAM at temperature 2. This result established algorithmic universality, but not the ability to assemble shapes efficiently, i.e., using systems of few tile types. Rothemund and Winfree [START_REF] Rothemund | The program-size complexity of selfassembled squares[END_REF] soon established this, achieving n × n square assembly with O(log n) tile types. Following this work, the twin capabilities of universal computation and efficient square assembly became the de facto benchmarks for powerful models of tile assembly. 1Followup work by Adleman et al. [START_REF] Adleman | Running time and program size for self-assembled squares[END_REF][START_REF] Cheng | Optimal self-assembly of counters at temperature two[END_REF] closed the small gaps in optimality left by the construction Rothemund and Winfree and introduced a new metric of efficiency: (expected) assembly time. This metric was ported from simultaneous work on the dynamics of linear assemblies by Adleman et al. [START_REF] Adleman | Toward a mathematical theory of self-assembly[END_REF][START_REF] Adleman | Linear self-assemblies: Equilibria, entropy and convergence rates[END_REF] and considered in other models later [START_REF] Chen | Parallelism and time in hierarchical self-assembly[END_REF]. Shortly after, efficient assembly of general (non-square) shapes was proved NP-complete by Adleman et al. [START_REF] Adleman | Combinatorial optimization problems in self-assembly[END_REF], while Soloveichik and Winfree [START_REF] Soloveichik | Complexity of self-assembled shapes (extended abstract)[END_REF] established the geometric universality [START_REF] Summers | Universality in algorithm self-assembly[END_REF] of the aTAM: the construction of all shapes efficiently (if scaling is permitted).

Even beyond techniques for information encoding and construction analysis introduced in [START_REF] Adleman | Running time and program size for self-assembled squares[END_REF][START_REF] Soloveichik | Complexity of self-assembled shapes (extended abstract)[END_REF], perhaps the most persistent single contribution of work in this era was implicit conjecture in [START_REF] Rothemund | The program-size complexity of selfassembled squares[END_REF] that the aTAM at temperature 1 is not capable of (universal) computation, based on related conjectured lower bound of 2n -1 tiles to assemble n × n squares.

Error-Prone Models (2002)(2003)(2004)(2005)(2006)(2007)(2008)(2009)(2010)(2011). Some of the earliest variations on the aTAM were those concerned with the design of systems robust to various errors in the assembly process. Such errors included incorrect tile attachments [START_REF] Chen | Invadable self-assembly: combining robustness with efficiency[END_REF][START_REF] Chen | Error free self-assembly using error prone tiles[END_REF][START_REF] Sahu | Capabilities and limits of compact error resilience methods for algorithmic self-assembly in two and three dimensions[END_REF][START_REF] Soloveichik | Combining self-healing and proofreading in self-assembly[END_REF][START_REF] Winfree | Proofreading tile sets: Error correction for algorithmic self-assembly[END_REF], assembly "damage" via partial deletion [START_REF] Soloveichik | Combining self-healing and proofreading in self-assembly[END_REF][START_REF] Winfree | Self-healing tile sets[END_REF], temperature fluctuations [START_REF] Doty | Strong fault-tolerance for self-assembly with fuzzy temperature[END_REF], and unseeded growth [START_REF] Schulman | Programmable control of nucleation for algorithmic self-assembly[END_REF]. In an ironic turn, the adversarial "seedless" growth addressed by Schulman et al. [START_REF] Schulman | Programmable control of nucleation for algorithmic self-assembly[END_REF] was later used to achieve efficient constructions impossible with seeded growth [START_REF] Cannon | Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM[END_REF]. The collection of errorprone models and results demonstrated that even small changes to aTAM yield rich new ideas. New model variations remain the largest catalyst of new work in tile assembly.

The Temperature 1 Problem (2005-ongoing). The Temperature-1 Problem is the most notorious open problem in tile assembly: is the temperature-1 aTAM computationally universal? The widely conjectured answer is a resounding "Obviously not!" 2 , but the problem has resisted nearly all progress, permitting only negative results that use either stronger conjectures [START_REF] Meunier | The self-assembly of paths and squares at temperature 1[END_REF][START_REF] Meunier | Intrinsic universality in tile self-assembly requires cooperation[END_REF], weaker models [START_REF] Maňuch | Journal of computational biology[END_REF][START_REF] Reif | The computation complexity of temperature-1 tilings[END_REF], or the assumption of other plausible conjectures [START_REF] Doty | Limitations of self-assembly at temperature one[END_REF].

One primary difficulty is even obtaining a precise formal statement of what constitutes "computation" in tile assembly. The second is developing a proof approach that passes the "3D test": the proof must break in 3D, implied by the result of Cook, Fu, and Schweller [START_REF] Cook | Temperature 1 self-assembly: determinstic assembly in 3d and probabilistic assembly in 2d[END_REF].

Computational Universality via Weak Cooperation (2007-2012). The computationally universality of the aTAM at temperature 2 and the temperature 1 problem beg the question of whether computational universality can be achieved by adding other features to the temperature-1 aTAM. Several variations of the temperature-1 aTAM were considered for which the answer proved to be "Yes". These included models using the third dimension [START_REF] Cook | Temperature 1 self-assembly: determinstic assembly in 3d and probabilistic assembly in 2d[END_REF], negativestrength glues [START_REF] Doty | Negative interactions in irreversible self-assembly[END_REF][START_REF] Patitz | Exact shapes and turing universality at temperature 1 with a single negative glue[END_REF], non-square tiles [START_REF] Fekete | Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly[END_REF][START_REF] Hendricks | The simulation powers and limitations of higher temperature hierarchical self-assembly systems[END_REF], and tiles with triggerable "signals" [START_REF] Jonoska | Active tile self-assembly, part 1: universality at temperature 1[END_REF][START_REF] Padilla | Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes[END_REF]. These models commonly exploit either "weak cooperation" in the form of repelling forces or the ability to "jump over walls".

Handedness (2008)(2009)(2010)(2011)(2012)(2013)(2014) In addition to models adding features to the temperature-1 aTAM, other modifications to the aTAM were under consider-ation. In particular, the elimination of the seed was considered in the hierarchical or two-handed (2HAM) tile assembly models, hinted at in several settings [START_REF] Aggarwal | Complexities for generalized models of self-assembly[END_REF][START_REF] Demaine | Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues[END_REF][START_REF] Luhrs | Polyomino-safe DNA self-assembly via block replacement[END_REF] before reaching the formulation used currently [START_REF] Abel | Shape replication through self-assembly and RNase enzymes[END_REF][START_REF] Doty | Strong fault-tolerance for self-assembly with fuzzy temperature[END_REF]. Surprisingly, the removal of the seed causes numerous unexpected effects, including increased power [START_REF] Cannon | Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM[END_REF], runaway growth [START_REF] Doty | Producibility in hierarchical self-assembly[END_REF][START_REF] Doty | Pattern overlap implies runaway growth in hierarchical tile systems[END_REF], and no improvement in assembly time [START_REF] Chen | Parallelism and time in hierarchical self-assembly[END_REF].

Intrinsic Universality (2010-present). By 2010, the introduction of new tile assembly models was occurring regularly. As previously described, many of these models obtained computational universality, but through alternative "weakly cooperative" means. With a few exceptions where direct simulation was possible (e.g., 2HAM simulation of aTAM [START_REF] Cannon | Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM[END_REF]), the understanding of the relative power of these models was unsatisfyingly coarse: models are either computationally universal or not.

Adapting definitions of a geometric notion of simulation from cellular automata (see [START_REF] Goles | Communication complexity and intrinsic universality in cellular automata[END_REF][START_REF] Ollinger | Universalities in cellular automata[END_REF]), Doty et al. [START_REF] Doty | The tile assembly model is intrinsically universal[END_REF][START_REF] Doty | Intrinsic universality in self-assembly[END_REF] established that the temperature-2 aTAM is intrinsic universal for all aTAM systems: there exists a single temperature-2 tile set that simulates the behavior of any aTAM system (when provided with a seed assembly encoding the system). Subsequent work used this new comparative metric to prove positive and negative intrinsic universality results for variations of the 2HAM, aTAM, and polygonal tile model [START_REF] Demaine | One tile to rule them all: Simulating any tile assembly system with a single universal tile[END_REF][START_REF] Demaine | The twohanded tile assembly model is not intrinsically universal[END_REF][START_REF] Hendricks | The simulation powers and limitations of higher temperature hierarchical self-assembly systems[END_REF][START_REF] Meunier | Intrinsic universality in tile self-assembly requires cooperation[END_REF]. In progress towards the Temperature 1 Problem, the temperature-1 aTAM was proved not intrinsically universal for the higher temperature aTAM [START_REF] Meunier | Intrinsic universality in tile self-assembly requires cooperation[END_REF], failing to match temperature 2.

As discussed later, these simple challenges ultimately proved insufficient detailed for distinguishing between some powerful but unequal models.


Sebastián Barbieri
email: sebastian.barbieri@ens-lyon.fr

Jarkko Kari
email: jkari@utu.fi

Ville Salo
email: vosalo@utu.fi

The group of reversible Turing machines

We consider Turing machines as actions over configurations in Σ Z d which only change them locally around a marked position that can move and carry a particular state. In this setting we study the monoid of Turing machines and the group of reversible Turing machines. We also study two natural subgroups, namely the group of finite-state automata, which generalizes the topological full groups studied in the theory of orbitequivalence, and the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates. Our main results are that the group of Turing machines in one dimension is neither amenable nor residually finite, but is locally embeddable in finite groups, and that the torsion problem is decidable for finite-state automata in dimension one, but not in dimension two.

Introduction

Turing machines and their generalization

Turing machines have been studied since the 30s as the standard formalization of the abstract concept of computation. However, more recently, Turing machines have also been studied in the context of dynamical systems. In [START_REF] Kůrka | On topological dynamics of Turing machines[END_REF], two dynamical systems were associated to a Turing machine, one with a 'moving tape' and one with a 'moving head'. After that, there has been a lot of study of dynamics of Turing machines, see for example [START_REF] Kůrka | Decidability and universality in symbolic dynamical systems[END_REF][START_REF] Umeo | On the presence of periodic configurations in Turing machines and in counter machines[END_REF][START_REF] Kari | Periodicity and immortality in reversible computing[END_REF][START_REF] Gajardo | One head machines from a symbolic approach[END_REF][START_REF] Gajardo | Zigzags in Turing machines[END_REF][START_REF] Jeandel | Computability of the entropy of one-tape Turing machines[END_REF][START_REF] Ollinger | The transitivity problem of Turing machines[END_REF]. Another connection between Turing machines and dynamics is that they can be used to define subshifts. Subshifts whose forbidden patterns are given by a Turing machine are called effectively closed, computable, or Π 0 1 subshifts, and especially in multiple dimensions, they are central to the topic due to the strong links known between SFTs, sofic shifts and Π 0 1 -subshifts, see for example [START_REF] Durand | Effective closed subshifts in 1d can be implemented in 2d[END_REF][START_REF] Aubrun | Simulation of effective subshifts by two-dimensional subshifts of finite type[END_REF]. An intrinsic notion of Turing machine computation for these subshifts on general groups was proposed in [START_REF] Aubrun | A notion of effectiveness for subshifts on finitely generated groups[END_REF], and a similar study was performed with finite state machines in [START_REF] Salo | Plane-walking automata[END_REF][START_REF] Salo | Group-walking automata[END_REF].

In all these papers, the definition of a Turing machine is (up to notational differences and switching between the moving tape and moving head model) the following: A Turing machine is a function T :

Σ Z × Q → Σ Z × Q defined by a local rule f T : Σ × Q → Σ × Q × {-1,
0, 1} by the formula T (x, q) = (σ -d (x), q ) if f T (x 0 , q) = (a, q , d), where σ : Σ Z → Σ Z is the shift action given by σ d (x) z = x z-d , x0 = a and x| Z\{0} = x| Z\{0} . In this paper, such Turing machines are called classical Turing machines. This definition (as far as we know) certainly suffices to capture all computational and dynamical properties of interest, but it also has some undesirable properties: The composition of two classical Turing machines -and even the square of a classical Turing machine -is typically not a classical Turing machine, and the reverse of a reversible classical Turing machine is not always a classical Turing machine.

In this paper, we give a more general definition of a Turing machine, by allowing it to move the head and modify cells at an arbitrary (but bounded) distance on each timestep. With the new definition, we get rid of both issues: With our definition, -Turing machines are closed under composition, forming a monoid, and reversible Turing machines are closed under inversion, forming a group.

We also characterize reversibility of classical Turing machines in combinatorial terms, and show what their inverses look like. Our definition of a Turing machine originated in the yet unpublished work [START_REF] Salo | [END_REF], where the group of such machines was studied on general Z-subshifts (with somewhat different objectives).

These benefits of the definition should be compared to the benefits of allowing arbitrary radii in the definition of a cellular automaton: If we define cellular automata as having a fixed radius of, say, 3, then the inverse map of a reversible cellular automaton is not always a cellular automaton, as the inverse of a cellular automaton may have a much larger radius [START_REF] Czeizler | A tight linear bound on the synchronization delay of bijective automata[END_REF]. Similarly, with a fixed radius, the composition of two cellular automata is not necessarily a cellular automaton.

We give our Turing machine definitions in two ways, with a moving tape and with a moving head, as done in [START_REF] Kůrka | On topological dynamics of Turing machines[END_REF]. The moving tape point of view is often the more useful one when studying one-step behavior and invariant measures, whereas we find the moving head point of view easier for constructing examples, and when we need to track the movement of multiple heads. The moving head Turing machines are in fact a subset of cellular automata on a particular kind of subshift. The moving tape machine on the other hand is a generalization of the topological full group of a subshift, which is an important concept in particular in the theory of orbit equivalence. For topological full groups of minimal subshifts, see for example [START_REF] Giordano | Full groups of Cantor minimal systems[END_REF][START_REF] Grigorchuk | On algebraic properties of topological full groups[END_REF][START_REF] Juschenko | Cantor systems, piecewise translations and simple amenable groups[END_REF]. The (one-sided) SFT case is studied in [START_REF] Matui | Topological full groups of one-sided shifts of finite type[END_REF].

Our results and comparisons with other groups

In Section 2, we define our basic models and prove basic results about them. In Section 2.3, we define the uniform measure and show as a simple application of it that injectivity and surjectivity are both equal to reversibility.

Our results have interesting counterparts in the theory of cellular automata: One of the main theorems in the theory of cellular automata is that injectivity implies surjectivity, and (global) bijectivity is equivalent to having a cellular automaton inverse map. Furthermore, one can attach to a reversible one-or two-dimensional cellular automaton its 'average drift', that is, the speed at which information moves when the map is applied, and this is a homomorphism from the group of cellular automata to a sublattice of Q d (where d is the corresponding dimension), see [START_REF] Kari | Representation of reversible cellular automata with block permutations[END_REF]. In Section 3 we use the uniform measure to define an analog, the 'average movement' homomorphism for Turing machines.

In Section 3, we define some interesting subgroups of the group of Turing machines. First, we define the local permutations -Turing machines that never move the head at all -, and their generalization to oblivious Turing machines where movement is allowed, but is independent of the tape contents. The group of oblivious Turing machines can be seen as a kind of generalization of lamplighter groups. It is easy to show that these groups are amenable but not residually finite. What makes them interesting is that the group of oblivious Turing machines is finitely generated, due to the existence of universal reversible logical gates. It turns out that strong enough universality for reversible gates was proved only recently [START_REF] Aaronson | The classification of reversible bit operations[END_REF].

We also define the group of (reversible) finite-state machines -Turing machines that never modify the tape. Here, we show how to embed a free group with a similar technique as used in [START_REF] Elek | On the topological full group of a minimal Cantor Zˆ2system[END_REF], proving that this group is non-amenable. By considering the action of Turing machines on periodic points, 4 we show that the group of finite-state automata is residually finite, and the group of Turing machines is locally embeddable in finite groups (in particular sofic).

Our definition of a Turing machine can be seen as a generalization of the topological full group, and in particular finite-state machines with a single state exactly correspond to this group. Thus, it is interesting to compare the results of Section 3 to known results about topological full groups. In [START_REF] Grigorchuk | On algebraic properties of topological full groups[END_REF][START_REF] Juschenko | Cantor systems, piecewise translations and simple amenable groups[END_REF] it is shown that the topological full group of a minimal subshift is locally embeddable in finite groups and amenable, while we show that on full shifts, this group is non-amenable, but the whole group of Turing machines is LEF. 5Our original motivation for defining these subgroups -finite-state machines and local permutations -was to study the question of whether they generate all reversible Turing machines. Namely, a reversible Turing machine changes the tape contents at the position of the head and then moves, in a globally reversible way. Thus, it is a natural question whether every reversible Turing machine can actually be split into reversible tape changes (actions by local permutations) and reversible moves (finite-state automata). We show that this is not the case, by showing that Turing machines can have arbitrarily small average movement, but that elementary ones have only a discrete sublattice of possible average movements. We do not know whether this is the only restriction.

In Section 4, we show that the group of Turing machines is recursively presented and has a decidable word problem, but that its torsion problem (the problem of deciding if a given element has finite order) is undecidable in all dimensions. For finite-state machines, we show that the torsion problem is decidable in dimension one, but is undecidable in higher dimensions, even when we restrict to a finitely generated subgroup. We note a similar situation with Thompson's group V : its torsion problem is decidable in one-dimension, but undecidable in higher dimensions. [START_REF] Belk | Conjugacy and dynamics in Thompson's groups[END_REF][START_REF] Belk | Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V[END_REF]

Preliminaries

In this section we present general definitions and settle the notation which is used throughout the article. The review of these concepts will be brief and focused on the dynamical aspects. For a more complete introduction the reader may refer to [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] or [START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF] for the group theoretic aspects. Let A be a finite alphabet. The set

A Z d = {x : Z d → A} equipped with the left group action σ : Z d × A Z d → A Z d defined by (σ v (x)) u = x u-v is a full shift.
The elements a ∈ A and x ∈ A Z d are called symbols and configurations respectively. With the discrete topology on A the set of configurations A Z d is compact and given by the metric d(x, y) = 2 -inf({|v|∈N| xv =yv}) where |v| is a norm on Z d (we settle here for the || • || ∞ norm). This topology has the cylinders

[a] v = {x ∈ A Z d |x v = a ∈ A} as a subbasis. A support is a finite subset F ⊂ Z d . Given a support F , a pattern with support F is an element p of A F . We also denote the cylinder generated by p in position v as [p] v = u∈F [p u ] v+u , and [p] = [p] 0 . Definition 1. A subset X of A Z d is a subshift if it is σ-invariant -σ(X) ⊂ X
-and closed for the cylinder topology. Equivalently, X is a subshift if and only if there exists a set of forbidden patterns F that defines it.

X = p∈F ,v∈Z d A Z d \ [p] v .
Let X, Y be subshifts over alphabets A and B respectively. A continuous Z d -equivariant map φ : X → Y between subshifts is called a morphism. A well-known Theorem of Curtis, Lyndon and Hedlund which can be found in full generality in [START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF] asserts that morphisms are equivalent to maps defined by local rules as follows: There exists a finite F ⊂ Z d and Φ :

A F → B such that ∀x ∈ X : φ(x) v = Φ(σ -v (x)| F ).
If φ is an endomorphism then we refer to it as a cellular automaton. A cellular automaton is said to be reversible if there exists a cellular automaton

φ -1 such that φ • φ -1 = φ -1 • φ = id. It is well known that reversibility is equivalent to bijectivity.
Throughout this article we use the following notation inspired by Turing machines. We denote by Σ = {0, . . . , n -1} the set of tape symbols and Q = {1, . . . , k} the set of states. We also use exclusively the symbols n = |Σ| for the size of the alphabet and k = |Q| for the number of states. Given a function f : Ω → i∈I A i we denote by f i the projection of f to the i-th coordinate.

In this section we define our generalized Turing machine model, and the group of Turing machines. In fact, we give two definitions for this group, one with a moving head and one with a moving tape as in [START_REF] Kůrka | On topological dynamics of Turing machines[END_REF]. We show that -except in the case of a trivial alphabet -these groups are isomorphic. 6 Furthermore, both can be defined both by local rules and 'dynamically', that is, in terms of continuity and the shift. In the moving tape model we characterize reversibility as preservation of the uniform measure. Finally we conclude this section by characterizing reversibility for classical Turing machines in our setting.

The moving head model

Consider Q = {1, . . . , k} and let X k be the subshift with alphabet Q ∪ {0} such that in each configuration the number of non-zero symbols is at most one.

X k = {x ∈ {0, 1, . . . , k} Z d | 0 / ∈ {x u , x v } =⇒ u = v}.
In particular

X 0 = {0 Z d } and i < j =⇒ X i X j . Let also Σ = {0, . . . , n -1} and X n,k = Σ Z d × X k .
For the case d = 1, configurations in X n,k represent a bi-infinite tape filled with symbols in Σ possibly containing a head that has a state in Q. Note that there might be no head in a configuration.

Definition 2. Given a function

f : Σ F × Q → Σ F × Q × Z d ,
where F, F are finite subsets of Z d , we can define a map T f : X n,k → X n,k as follows: Let (x, y) ∈ X n,k . If there is no v ∈ Z d such that y v = 0 then T (x, y) = (x, y). Otherwise let p = σ -v (x)| F , q = y v = 0 and f (p, q) = (p , q , d).

Then T (x, y) = (x, ỹ) where:

xt = x t if t -v / ∈ F p t-v if t -v ∈ F , ỹt = q if t = v + d 0 otherwise Such T = T f is called a (moving head) (d, n, k)-Turing machine, and f is its local rule. If there exists a (d, n, k)-Turing machine T -1 such that T • T -1 = T -1 • T = id, we say T is reversible.
Note that σ -v (x)| F is the F -shaped pattern 'at' v, but we do not write x| F +v because we want the pattern we read from x to have F as its domain.

This definition corresponds to classical Turing machines with the moving head model when d = 1, F = F = {0} and f (x, q) 3 ∈ {-1, 0, 1} for all x, q. By possibly changing the local rule f , we can always choose F = [-r i , r i ] d and F = [-r o , r o ] d for some r i , r o ∈ N, without changing the Turing machine T f it defines. The minimal such r i is called the in-radius of T , and the minimal r o is called the out-radius of T . We say the in-radius of a Turing machine is -1 if there is no dependence on input, that is, the neighborhood [-r i , r i ] can be replaced by the empty set. Since Σ F × Q is finite, the third component of f (p, q) takes only finitely many values v ∈ Z d . The maximum of |v| for such v is called the move-radius of T . Finally, the maximum of all these three radii is called the radius of T . In this terminology, classical Turing machines are those with in-and out-radius 0, and move-radius 1. In some parts of this article we just consider d = 1. In this case we simplify the notation and just write RTM(n, k) := RTM(Z, n, k).

Of course, we want TM(Z d , n, k) to be a monoid and RTM(Z d , n, k) a group under function composition. This is indeed the case, and one can prove this directly by constructing local rules for the inverse of a reversible Turing machine and composition of two Turing machines. However, it is much easier to extract this from the following characterization of Turing machines as a particular kind of cellular automaton.

For a subshift X, we denote by End(X) the monoid of endomorphisms of X and Aut(X) the group of automorphisms of X.

Proposition 1. Let n, k be positive integers and Y = X n,0 . Then: Clearly, the conditions of Proposition 1 are preserved under function composition and inversion. Thus:

TM(Z d , n, k) = {φ ∈ End(X n,k ) | φ| Y = id, φ -1 (Y ) = Y } RTM(Z d , n, k) = {φ ∈ Aut(X n,k ) | φ| Y = id}
Corollary 2. Under function composition, (TM(Z d , n, k), •) is a submonoid of End(X n,k ) and (RTM(Z d , n, k), •) is a group.
We usually omit the function composition symbol, and use the notations TM(Z d , n, k) and RTM(Z d , n, k) to refer to the corresponding monoids and groups.

The moving tape model

It's also possible to consider the position of the Turing machine as fixed at 0, and move the tape instead, to obtain the moving tape Turing machine model. In [START_REF] Kůrka | On topological dynamics of Turing machines[END_REF], where Turing machines are studied as dynamical systems, the moving head model and moving tape model give non-conjugate dynamical systems. However, the abstract monoids defined by the two points of view turn out to be equal, and we obtain an equivalent definition of the group of Turing machines.

As in the previous section, we begin with a definition using local rules.

Definition 4. Given a function f :

Σ F × Q → Σ F × Q × Z d
, where F, F are finite subsets of Z d , we can define a map T f :

Σ Z d × Q → Σ Z d × Q as follows: If f (x| F , q) = (p, q , d), then T f (x, q) = (σ d (y), q ) where y u = x u , if u / ∈ F p u , if u ∈ F ,
is called the moving tape Turing machine defined by f . These machines also have the following characterization with a slightly more dynamical feel to it. Say that x and y are asymptotic, and write x ∼ y, if d(σ v (x), σ v (y)) → 0 as |v| → ∞. We write x ∼ m y if x v = y v for all |v| ≥ m, and clearly x ∼ y ⇐⇒ ∃m : x ∼ m y.

Lemma 1. Let T : Σ Z d × Q → Σ Z d × Q be a function.
Then T is a moving tape Turing machine if and only if it is continuous, and for a continuous function s :

Σ Z d × Q → Z d and a ∈ N we have T (x, q) 1 ∼ a σ s(x,q) (x) for all (x, q) ∈ Σ Z d × Q.
Note that in place of a we could allow a continuous N-valued function of (x, q) -the definition obtained would be equivalent, as the a of the present definition can be taken as the maximum of such a function.

We call the function s in the definition of these machines the shift indicator of T , as it indicates how much the tape is shifted depending on the local configuration around 0. In the theory of orbit equivalence and topological full groups, the analogs of s are usually called cocycles. We also define in-, out-and move-radii of moving tape Turing machines similarly as in the moving head case.

We note that it is not enough that T (x, q) 1 ∼ σ s(x,q) (x) for all (x, q) ∈ Σ Z d × Q: Let Q = {1} and consider the function T :

Σ Z × Q → Σ Z × Q defined by (T (x, 1) 1 ) i = x -i if x [-|i|+1,|i|-1] = 0 2i-1
and {x i , x -i } = {0}, and (T (x, 1) 1 ) i = x i otherwise. Clearly this map is continuous, and the constant-0 map s(x, q) = 0 gives a shift-indicator for it. However, T is not defined by any local rule since it can modify the tape arbitrarily far from the origin.

As for moving head machines, it is easy to see (either by constructing local rules or by applying the dynamical definition) that the composition of two moving tape Turing machines is again a moving tape Turing machine. This allows us to proceed as before and define their monoid and group. Definition 5. We denote by TM fix (Z d , n, k) and RTM fix (Z d , n, k) the monoid of moving tape (d, n, k)-Turing machines and the group of reversible moving tape (d, n, k)-Turing machines respectively. Now, let us show that the moving head and moving tape models are equivalent. First, there is a natural epimorphism Ψ : TM(Z d , n, k) → TM fix (Z d , n, k). Namely, let T ∈ TM(Z d , n, k). We define Ψ (T ) as follows: Let (x, q) ∈ Σ Z d × Q. Letting y be the configuration such that y 0 = q and 0 everywhere else and T (x, y) = (x , y ) such that y v = q we define Ψ (T )(x, q) = (σ -v (x ), q ). This is clearly an epimorphism but it's not necessarily injective if n = 1. Indeed, we have that RTM fix (Z d , 1, k) ∼ = S k and TM fix (Z d , 1, k) is isomorphic to the monoid of all functions from {1, . . . , k} to itself while

Z d ≤ RTM(Z d , 1, k) ≤ TM(Z d , 1, k). Nevertheless, if n ≥ 2 this mapping is an isomorphism. Lemma 2. If n ≥ 2 then: TM fix (Z d , n, k) ∼ = TM(Z d , n, k) RTM fix (Z d , n, k) ∼ = RTM(Z d , n, k).
The previous result means that besides the trivial case n = 1 where the tape plays no role, we can study the properties of these groups using any model.

The uniform measure and reversibility.

Consider the space Σ Z d ×Q. We define a measure µ on B(Σ Z d ×Q) as the product measure of the uniform Bernoulli measure and the uniform discrete measure. That is, if F is a finite subset of Z d and p ∈ Σ F , then:

µ([p] × {q}) = 1 kn |F | .
With this measure in hand we can prove the following: Theorem 1. Let T ∈ TM fix (Z d , n, k). Then the following are equivalent:

1. T is injective. 2. T is surjective. 3. T ∈ RTM fix (Z d , n, k). 4.
T preserves the uniform measure (µ(T -1 (A)) = µ(A) for all Borel sets A).

µ(T (A)) = µ(A) for all Borel sets A.

Remark 1. The proof is based on showing that every Turing machine is a local homeomorphism and preserves the measure of all large-radius cylinders in the forward sense. Note that preserving the measure of large-radius cylinders in the forward sense does not imply preserving the measure of all Borel sets, in general. For example, the machine which turns the symbol in F = {0} to 0 without moving the head satisfies µ(

[p]) = µ(T [p]) for any p ∈ Σ S with S ⊃ F . But µ([]) = 1 and µ(T ([])) = µ([0]) = 1/2,
where [] = {0, . . . , n} Z is the cylinder defined by the empty word.

Using the measure, one can define the average movement of a Turing machine.

Definition 6. Let T ∈ TM fix (Z d , n, k) with shift indicator function s : Σ Z d × Q → Z d . We define the average movement α(T ) ∈ Q d as α(T ) := E µ (s) = Σ Z d ×Q s(x, q)dµ,
where µ is the uniform measure defined in Subsection 2.3. For T in TM(Z d , n, k) we define α as the application to its image under the canonical epimorphism Ψ , that is, α(T ) := α(Ψ (T )).

We remark that this integral is actually a finite sum over the cylinders p ∈ Σ F . Nonetheless, its expression as an expected value allows us to show the following:

If T 1 , T 2 ∈ RTM(Z d , n, k) then α(T 1 •T 2 ) = α(T 1 )+α(T 2 )
. Indeed, as reversibility implies measure-preservation, we have that

E µ (s T1•T2 ) = E µ (s T1 • T 2 + s T2 ) = E µ (s T1 ) + E µ (s T2 ).
This means that α defines an homomorphism from RTM(Z d , n, k) to Q d .

Classical Turing machines

As discussed in the introduction, we say a one-dimensional Turing machine is classical if its in-and out-radii are 0, and its move-radius is 1. In this section, we characterize reversibility in classical Turing machines. If T 0 has in-, outand move-radius 0, that is, T 0 only performs a permutation of the set of pairs (s, q) ∈ Σ × Q at the position of the head, then we say T 0 is a state-symbol permutation. If T 1 has in-radius -1, never modifies the tape, and only makes movements by vectors in {-1, 0, 1}, then T 1 is called a state-dependent shift. 7Theorem 2. A classical Turing machine T is reversible if and only if it is of the form T 1 • T 0 where T 0 is a state-symbol permutation and T 1 is a state-dependent shift.

It follows that the inverse of a reversible classical Turing machine is always of the form T 0 • T 1 where T 0 is a state-symbol permutation and T 1 is a statedependent shift. In the terminology of Section 3, the theorem implies that all reversible classical Turing machines are elementary.

Properties of RTM and interesting subgroups

In this section we study some properties of RTM by studying the subgroups it contains. We introduce LP, the group of local permutations where the head does not move and RFA, the group of (reversible) finite-state automata which do not change the tape. These groups separately capture the dynamics of changing the tape and moving the head. We also define the group of oblivious Turing machines OB as an extension of LP where arbitrary tape-independent moves are allowed, and EL as the group of elementary Turing machines, which are compositions of finite-state automata and oblivious Turing machines.

First, we observe that α(RTM(Z d , n, k)) is not finitely generated, and thus:

Theorem 3. For n ≥ 2, the group RTM(Z d , n, k) is not finitely generated.

Although α is not a homomorphism on TM(Z d , n, k), using Theorem 1, we obtain that TM(Z d , n, k) cannot be finitely generated either.

Local permutations and oblivious Turing machines

For v ∈ Z d , define the machine T v which does not modifies the state or the tape, and moves the head by the vector v on each step. Denote the group of such machines by Shift(Z d , n, k). Clearly α : Shift(Z d , n, k) → Z d is a group isomorphism. Define also SP(Z d , n, k) as the state-permutations: Turing machines that never move and only permute their state as a function of the tape. In other words, LP(Z d , n, k) is the group of reversible machines that do not move the head, and OB(Z d , n, k) is the group of reversible Turing machines whose head movement is independent of the tape contents. Note that in the definition of both groups, we allow changing the state as a function of the tape, and vice versa. Clearly Shift(Z d , n, k) ≤ OB(Z d , n, k) and SP(Z d , n, k) ≤ LP(Z d , n, k). Proposition 2. Let S ∞ be the group of permutations of N of finite support. Then for n ≥ 2, S ∞ → LP(Z d , n, k).

In particular, RTM(Z d , n, k) is not residually finite. By Cayley's theorem, Proposition 2 also implies that RTM(Z d , n, k) contains all finite groups. Proposition 3. The group OB(Z d , n, k) is amenable.

Write H G for the restricted wreath product. The groups G Z d are sometimes called generalized lamplighter groups. In fact, OB(Z d , n, k) can in some sense be seen as a generalized generalized lamplighter group, since the subgroup of OB(Z d , n, k) generated by the local permutations LP(Z d , n, 1) with radius 0 and Shift(Z d , n, 1) is isomorphic to

A ∼ = S n Z d .
Interestingly, just like the generalized lamplighter groups, we can show that the whole group OB(Z d , n, k) is finitely generated.

Finite-state automata

Definition 8. We define the reversible finite-state automata RFA(Z d , n, k) as the group of reversible (d, n, k)-Turing machines that do not change the tape. That is, the local rules are of the form f (p, q) = (p, q , z) for all entries p ∈ Σ F , q ∈ Q.

This group is orthogonal to OB(Z d , n, k) in the following sense:

Proposition 5. RFA(Z d , n, k) ∩ LP(Z d , n, k) = SP(Z d , n, k) RFA(Z d , n, k) ∩ OB(Z d , n, k) = SP(Z d , n, k), Shift(Z d , n, k)
As usual, the case n = 1 is not particularly interesting, and we have that RFA(Z d , 1, k) ∼ = RTM(Z d , 1, k). In the general case the group is more complex.

We now prove that the RFA(Z d , n, k)-groups are non-amenable. In [START_REF] Elek | On the topological full group of a minimal Cantor Zˆ2system[END_REF], a similar idea is used to prove that there exists a minimal Z 2 -subshift whose topological full group is not amenable. Proposition 6. Let n ≥ 2. For all m ∈ N we have that:

Z/2Z * • • • * Z/2Z m times → RFA(Z d , n, k) Corollary 3.
For n ≥ 2, RFA(Z d , n, k) and RTM(Z d , n, k) contain the free group on two elements. In particular, they are not amenable.

By standard marker constructions, one can also embed all finite groups and finitely generated abelian groups in RFA(Z d , n, k) -however, this group is residually finite, and thus does not contain S ∞ or (Q, +). The proof of this theorem is based on studying the action of the group on finite subshifts where heads are occur periodically. Non-finitely generatedness is obtained by looking at signs of permutations of the finitely many orbits, to obtain the sign homomorphism to an infinitely generated abelian group.

8. Let Q p = 1 p Z. Then α(RFA(Z d , n, k)) = α(EL(Z d , n, k)) = Q d k . In particular, EL(Z d , n, k) RTM(Z d , n, k).
We do not know whether α(T ) ∈ Z d implies T ∈ EL(Z d , n, 1), nor whether EL(Z d , n, k) is finitely generated -the sign homomorphism we use in the proof of finitely-generatedness of the group of finite-state automata does not extend to it.

By the results of this section, the group RTM(Z d , n, k) is neither amenable nor residually finite. By adapting the proof of Theorem 5, one can show that it is locally embeddable in finite groups. See [START_REF] Vershik | Groups that are locally embeddable in the class of finite groups[END_REF][START_REF] Ziman | On finite approximations of groups and algebras[END_REF][START_REF] Weiss | Sofic groups and dynamical systems[END_REF] for the definitions. Theorem 6. The group RTM(Z d , n, k) is LEF, and thus sofic, for all n, k, d.

Computability aspects

Basic decidability results

First, we observe that basic management of local rules is decidable. Note that these results hold, and are easy to prove, even in higher dimensions. Lemma 3. Given two local rules f, g :

Σ F × Q → Σ F × Q × Z d ,
it is decidable whether T f = T g , we can effectively compute a local rule for T f • T g , it is decidable whether T f is reversible, and we can effectively compute a local rule for T -1 f when T f is reversible.

A group is called recursively presented if one can algorithmically enumerate its elements, and all identities that hold between them. If one can furthermore decide whether a given identity holds in the group (equivalently, whether a given element is equal to the identity element), we say the group has a decidable word problem. The above lemma is the algorithmic content of the following proposition: Proposition 9. The groups TM(Z d , n, k) and RTM(Z d , n, k) are recursively presented and have decidable word problems in the standard presentations.

The torsion problem

The torsion problem of a recursively presented group G is the set of presentations of elements g ∈ G such that g n = 1 G for some n ≥ 1. Torsion elements are recursively enumerable when the group G is recursively presented, but the torsion problem need not be decidable even when G has decidable word problem.

In the case of RTM(Z d , n, k) the torsion problem is undecidable for n ≥ 2. This result was shown by Kari and Ollinger in [START_REF] Kari | Periodicity and immortality in reversible computing[END_REF] using a reduction from the mortality problem which they also prove to be undecidable.

The question becomes quite interesting if we consider the subgroup RFA(Z d , n, k) for n ≥ 2, as then the decidability of the torsion problem is dimension-sensitive.

Definition 3 .

 3 Define TM(Z d , n, k) as the set of (d, n, k)-Turing machines and RTM(Z d , n, k) the set of reversible (d, n, k)-Turing machines.

Corollary 1 .

 1 We have φ ∈ RTM(Z d , n, k) if and only if φ ∈ TM(Z d , n, k) and φ is bijective.

Definition 7 .

 7 We define the group LP(Z d , n, k) of local permutations as the subgroup of reversible (d, n, k)-Turing machines whose shift-indicator is the constant-0 function. Define also OB(Z d , n, k) = Shift(Z d , n, k), LP(Z d , n, k) , the group of oblivious Turing machines.

Proposition 4 .

 4 If G is a finite group and n ≥ 2, then G Z d → OB(Z d , n, k).

Theorem 4 .

 4 OB(Z d , n, k) is finitely generated.

Proposition 7 .

 7 Let n ≥ 2 and G be any finite group or a finitely generated abelian group. Then G ≤ RFA(Z d , n, k).Theorem 5. Let n ≥ 2, k ≥ 1, d ≥ 1.Then the group RFA(Z d , n, k) is residually finite and is not finitely generated.

3. 3

 3 Elementary Turing machines and the LEF property of RTM Definition 9. We define the group of elementary Turing machines EL(Z d , n, k) := RFA(Z d , n, k), LP(Z d , n, k) . That is, the group generated by machines which only change the tape or move the head.

Proposition

Theorem 7 .Theorem 8 .

 78 The torsion problem of RFA(Z, n, k) is decidable. For all n ≥ 2, k ≥ 1, d ≥ 2, there is a finitely generated subgroup of RFA(Z d , n, k) whose torsion problem is undecidable.

The idea is similar as that in[START_REF] Boyle | The automorphism group of a shift of finite type[END_REF] for showing that automorphism groups of mixing SFTs are residually finite, but we do not actually look at subsystems, but the periodic points of an enlarged system, where we allow infinitely many heads to occur.

In[START_REF] Salo | [END_REF] it is shown that on minimal subshifts, the group of Turing machines coincides with the group of finite-state automata.

Note that the dynamics obtained from these two definitions are in fact quite different, as shown in[START_REF] Kůrka | On topological dynamics of Turing machines[END_REF][START_REF] Kůrka | Erratum to: Entropy of Turing machines with moving head[END_REF].

Note that these machines are slightly different than the groups SP(Z, n, k) and Shift(Z, n, k) introduced in Section 3, as the permutations in SP(Z, n, k) do not modify the tape, and moves in Shift(Z; n, k) cannot depend on the state.

Acknowledgements

The third author was supported by FONDECYT grant 3150552.