Rodrigo Torres
email: rtorres@ing-mat.udec.cl

Nicolas Ollinger
email: nicolas.ollinger@univ-orleans.fr

Anahí Gajardo

Undecidability of the surjectivity of the subshift associated to a Turing machine

Keywords: Turing machines, discrete-time dynamical systems, subshifts, formal languages

We consider Turing machines (TM) from a dynamical system point of view, and in this context, we associate a subshift by taking the sequence of symbols and states that the head has at each instant. Taking a subshift that select only a part of the state of a system is a classical technic in dynamical systems that plays a central role in their analysis. Surjectivity of Turing machines is equivalent to their reversibility and it can be simply identified from the machine rule. Nevertheless, the associated subshift can be surjective even if the machine is not, and the property results to be undecidable in the symbolic system.

consists in taking the linear sequence of states and symbols that the machine reads during its evolution over a given initial configuration, and to consider afterwards the set of infinite sequences produced by all the possible initial configurations. Subshifts are key tools in the study of general dynamical systems, they give crucial information about the system (see for example [START_REF] Kůrka | Topological and Symbolic Dynamics[END_REF]). In this approach, the complexity of the subshift has been related with the complexity of the machine.

In this paper, we study the surjectivity of the t-shift. A function T is surjective if for every y, there exists an x such that T (x) = y. If T is the function that defines the evolution of a Turing machine, it results to be equivalent to the reversibility of the machine and it can be characterized in a very simple way from the machine's transition rule. If the machine is surjective, so it is its associated t-shift, but the converse is not true. Thus we look for a characterization of the surjectivity of the t-shift in terms of some property of the machine.

When a subshift is surjective, every sequence can be extended by the left, in such a way that the subshift itself can be considered as a set of bi-infinite sequences, i.e., sequences running over Z. In this case, the shift action is reversible, and other properties can be considered.

Another reason to study this property is that surjectivity is a necessary condition for transitivity, which is a relevant property in the area of dynamical systems.

The following section provides definitions and concepts about symbolic dynamics and Turing machines. Section 2 gives a characterization of the t-shift surjectivity. In section 3, we establish the undecidability of some preliminary problems, to conclude with the undecidability of the property in the last section.

Definitions

Turing Machine

Turing machine written in quadruples. Following Morita [START_REF] Morita | A 1-tape 2-symbol reversible Turing machine[END_REF], a Turing machine (TM) M is a tuple (Q, Σ, δ), where Q is a finite set of states, Σ is a finite set of symbols and

δ ⊆ Q × Σ × Σ × Q ∪ Q × {/} × {-1, 0, +1} × Q is the
writing/moving relation of the machine. The machine works on a tape, usually bi-infinite, full of symbols from Σ. A configuration is an element (w, i, q) of Σ Z × Z × Q. A writing instruction is a quadruple (q, s, s ′ , q ′ ); it can be applied to a configuration (w, i, q ′′ ) if w i = s and q = q ′′ , leading to the configuration (w ′ , i, q ′ ), where w ′ i = s ′ and w ′ k = w k for all k = i. A moving instruction is a quadruple (q, /, d, q ′ ); it can be applied to a configuration (w, i, q ′′ ) if q = q ′′ , leading to the configuration (w, i + d, q ′ ).

Turing machine written in quintuples.

A Turing machine M can also be written in quintuples by having the writing/moving relation δ considered as δ ⊆ Q × Σ × Q × Σ × {-1, 0, +1}. A quintuple instruction (q, s, q ′ , s ′ , d) can be applied to a configuration (w, i, q ′′ ) if w i = s and q = q ′′ , leading to the configuration (w ′ , i + d, q ′ ), where w ′ i = s ′ and w ′ k = w k for all k = i. Turing machines, when viewed as computing model, have a particular starting state q 0 , and a particular symbol called blank symbol; the computation is intended to start over a configuration (w, 0, q 0 ), where w represents the input, a word with a finite number of non-blank symbols. The computation process stops when the machine reaches another particular state: the halting state q F . In this paper, we are omitting these three parameters, since we do not want the machine to halt and we will study its dynamics for arbitrary initial configurations. In any case, the halting problem can be translated to the present context as the problem of deciding whether the machine reaches a particular state when starting in another particular state with an homogeneous configuration except for a finite number of cells.

We also remark that the quintuples model is the traditional one, while the quadruples model is used for reversible Turing machines. One can translate any machine written in quadruples into a machine written in quintuples in a simple way because writing instructions are just quintuples instructions that do not cause any movement, and moving instructions are those that do not modify the tape. The converse transformation is also possible but a quintuple instruction will need to be replaced by a writing instruction followed by a moving instruction, thus the set of states needs to be duplicated and the time is also multiplied by two. Therefore, both models are equivalent as computing system, but not as dynamical system.

Deterministic Turing machine.

A Turing machine M is deterministic if, for any configuration (w, i, q) ∈ X, at most one instruction can be applied (regardless the machine is written in quadruples or quintuples). In terms of quintuples, this is equivalent to give δ as a (possibly partial) function δ :

Q × Σ → Q × Σ × {-1, 0, +1}. This function δ can be projected into three components δ Q : Q × Σ → Q, δ S : Q × Σ → Σ and δ D : Q × Σ → {-1, 0, +1}.
Complete Turing machine. In any of the two models, if no instruction can be applied, the machine halts. A Turing machine M is complete if for each configuration (w, i, q), at least one instruction can be applied, i.e., it never halts.

Analogous notions can be defined when going backward in time.

Backward deterministic Turing machine. A Turing machine M is backward deterministic if each configuration comes from at most one previous configuration. A Turing machine written in quadruples is backward deterministic (as seen in [START_REF] Morita | A 1-tape 2-symbol reversible Turing machine[END_REF]) if and only if for any two different quadruples (q, s, s ′ , q ′ ) and (q ′′ , s ′′ , s ′′′ , q ′ ) in δ, it holds:

s = / ∧ s ′′ = / ∧ s ′ = s ′′′
Backward complete Turing machine. A Turing machine M is backward complete if each configuration comes from at least one preimage.

Reversible Turing machine. A Turing machine is reversible if it is deterministic forward and backward. For a machine written in quadruples, reversing the quadruples gives the reverse machine. The reverse instruction of a writing instruction (q, s, s ′ , q ′ ) is (q ′ , s ′ , s, q). The reverse instruction of a movement instruction (q, /, d, q ′ ) is (q ′ , /, -d, q). It is not difficult to see that a reversible Turing machine is complete if and only if its reverse is complete.

All of these last properties are local, and they can be checked in a finite number of steps.

Dynamical System

A dynamical system is a pair (X, T ), where X is called phase space and T : X → X is called global transition function. In this paper, we consider

X = Σ Z × Z × Q. Σ Z is
called the two-sided full shift and its elements are called bi-infinite words, the symbol ′ will be used to mark the position 0; for example, . . . 2333 ′ 233124 . . . indicates that 2 is set in the position 0. Σ N is the one-sided full shif t and its elements are called infinite words.

Subshifts. The shift function σ, is defined both in Σ Z and Σ N either by σ(. . . w -2 w ′ -1 w 0 w 1 w 2 . . .) = . . . w -1 w ′ 0 w 1 w 2 w 3 . . . or σ(w 1 w 2 w 3 . . .) = w 2 w 3 .
. .; it is a bijective function in the first case. Σ * denotes the set of finite sequences of elements of Σ, called finite words. Two words z = z 0 ...z n and y = y 0 ...y m can be concatenated by just putting them one after the other: zy = z 0 ...z n y 0 ...y m . A word x can also be concatenated with a semi-infinite word w = w 0 w 1 w 2 ...: xw = x 0 ...x n w 0 w 1 . . . A finite word z is said to be a subword of another (finite or infinite) word v, if there exists two indices i and j, such that z = v i v i+1 ...v j . In this case we write: z ⊑ v. Subsets of Σ * are called formal languages. Given a subset of the full shift S, a formal language is defined:

L(S) = {z ∈ Σ * | (∃w ∈ S) z ⊑ w} .
Reciprocally, given a formal language L, a set of infinite sequences can be defined:

S L = {w ∈ Σ M | (∀z ⊑ w) z ∈ L} . When S satisfies S L(S) = S, it is called a subshift.
The t-shift. A complete and deterministic Turing machine M = (Q, Σ, δ) can be associated with a dynamical system (X, T ), where X is the set of configurations Σ Z × Z × Q, and the global transition function T : X → X consists into apply one transition of the Turing machine. We define π : [START_REF] Gajardo | One head machines from a symbolic approach[END_REF].

X → Q × Σ by π(w, i, q) = (q, w i ). The t-shift associated to T , denoted by S T ⊆ (Q × Σ) N , is the set of orbits τ (x) = (π(T n (x))) n∈N , for x ∈ X. It is not difficult to see that S T is in fact a subshift

Surjectivity

As we have said, when M is deterministic and complete, T is a function. In this context, backward determinism is equivalent to injectivity of T and backward completeness corresponds to surjectivity. Through a cardinality argument, it is possible to show that, when the machine is deterministic and complete, surjectivity is equivalent to injectivity and both are easy to check from the machine's transition rule. From now on, we will work only with deterministic and complete Turing machines.

Remark 1. A Turing machine M = (Q, Σ, δ) written in quintuples is surjective if and only if, for every q ′ ∈ Q and s ′ , r ′ , t ′ ∈ Σ, there is at least one q ∈ Q and s ∈ Σ such that δ(q, s) = (q ′ , s ′ , +1) or δ(q, s) = (q ′ , r ′ , -1) or δ(q, s) = (q ′ , t ′ , 0).

If for some q ′ , the condition of TM surjectivity is not satisfied, we say that q ′ is defective. Thus a machine is surjective if and only if it has no defective state.

Definition 1. A state q ′ ∈ Q of a Turing machine M = (Q, Σ, δ) is said to be defective if:
1. (Quintuple model) There exist symbols s ′ , r ′ , t ′ ∈ Σ such that no instruction gives: (q ′ , s ′ , +1), (q ′ , r ′ , -1) or (q ′ , t ′ , 0).

(Quadruple model)

There exist s ′ ∈ Σ such that there exist no instruction (q, /, d, q ′ ) nor (q, s, s ′ , q ′ ), for no q ∈ Q, s ∈ Σ, and d ∈ {-1, 0, +1}.

Notice that an unreachable state is indeed defective, but we will assume that every state is reachable. If not, the subshift S T will not be surjective in any case.

Surjectivity of T is inherited by the subshift S T , however, if T is not surjective, the subshift can still be surjective. For example, let M be the Turing machine that simply moves to the right by always writing a 0. This machine is not surjective, but the associated subshift does.

Remark 2. A t-shift is surjective if and only if: (∀u

∈ S T )(∃a ∈ Q × Σ) au ∈ S T
If u = ( q1 q2 ... s1 s2 ... ) ∈ S T and a = (q, s), condition au ∈ S T says that δ Q (q, s) = q 1 and that the configuration that produces u has the symbol s at position -δ D (q, s). If the machine does not visit position -δ D (q, s), s can be any symbol, otherwise it is restricted to the constraint δ S (q, s) = s i+1 , where

i = min{j | j k=1 δ D (u k ) = -δ D (q, s)}.
In the example, the unique state of the machine is defective, it does not admit the symbol '1' at the left of the head, but position -1 is never revisited, that is why any symbol can be appended at the beginnig of u. If the state q 1 is defective and it does not admits the symbol s i+1 at position -δ(q, s), then au ∈ S T . Surjectivity will be possible when defective states avoid the head from going in to the "conflictive" positions, we develop this in the next section.

It is important to note that in the quadruples model, the surjectivity of T is held by the subshift S T and vice versa. If we have a defective state q 1 , then there exist no moving instruction leading to q 1 . From the previous assertion, if q 1 is defective, then S T is not surjective. We are interested in surjectivity only within the quintuples model.

Blocking States

We say that a state q is a blocking state to the left (right) if:

(∀u ∈ S T )(∀s ∈ Σ) u 1 = (s, q) ⇒ (∀j ∈ N) j k=1 δ D (u k ) = -1(+1) .
We also say that q is an s-blocking state to the left (right) for a given s ∈ Σ, if:

(∀u ∈ S T ) u 1 = (s, q) ⇒ (∀j ∈ N) j k=1 δ D (u k ) = -1(+1) .
Finally we say that q is just a blocking state, if for every s ∈ Σ, q is an s-blocking state either to the left or right.

A state q is said to be reachable from the left (right) if there exists a state q ′ and symbols s, s ′ such that δ(s ′ , q ′ ) = (s, q, +1) (resp. -1).

The surjectivity on S T can be characterized through these notions, in fact, S T is surjective if and only if for each q ′ ∈ Q at least one of the following holds:

1. q ′ is not defective: If q ′ is not defective, then, independently on the context, it can be reached from some configuration. 2. q ′ is blocking to the left (right) and it is reachable from the left (right):

If q ′ happens to be a blocking state to the left (right), no configuration producing u ∈ S T , with u 1 = (q ′ , s 1 ), is able to revisit the position -1 (+1) (with respect to the initial head position), so any (q, s) ∈ Q × Σ, such that δ Q (q, s) = q ′ and δ D (q, s) = +1(-1), can be appended at the beginning of u. 3. q ′ is blocking and it is reachable from the left and from the right: If q ′ happens to be a blocking state, u ∈ S T starts with u 1 = (q ′ , s 1 ) and q ′ is s 1 -blocking to the left (right), then no configuration producing u is able to revisit the position -1 (+1) (with respect to the initial head position), so any (q, s) ∈ Q × Σ, satisfying δ Q (q, s) = q ′ and δ D (q, s) = +1(-1) can be appended at the beginning of u.

If we could decide when a state is blocking, we could decide surjectivity. In the next section, however, we see that checking the blocking property is not possible.

Undecidability of preliminary problems

In this section, we show the undecidability of several problems related with the blocking property of a state, that will serve as intermediate to finally prove the undecidability of the surjectivity on S T in section 4.

Let us remark that the following proofs are equivalent in quadruples and quintuples model, one only has to use the usual transformation described in the section 1. The last is possible because the following problems are related to movement abilities of the head.

Undecidability of the blocking state problem

Let us consider the next three problems.

(BSl) Given a Turing machine M and a state q, decide whether q is a blocking state to the left. (BSr) Given a Turing machine M and a state q, decide whether q is a blocking state to the right. (BS) Given a Turing machine M and a state q, decide whether q is a blocking state.

Let us remark that (BSl) and (BSr) are Turing equivalent, i.e., (BSl) reduces to (BSr) and vice versa. To see this it is enough to see that switching the movement direction on every instruction of a given machine M produces a machine M ′ whose states are blocking to the left if and only if the respective states of M are blocking to the right.

We prove the undecidability of these three problems by reduction from the emptiness problem, which is known to be undecidable for machines written either in quadruples or quintulples and also for machines restricted to work on a semi infinite tape. The definition of the emptiness problem is adapted to the present context as follows.

(E) Given a Turing machine M , and two states q 0 and q F , decide whether there is an input configuration (w, 0, q 0 ) that makes the machine to reach the state q F in finite time.

Lemma 1. (BSl) is undecidable.

Proof. We prove undecidability by reduction from the emptiness problem. Let M = (Q, Σ, δ) be a Turing machine, and let q 0 , q F ∈ Q be two states. We will assume, without loss of generality, that M is written in quintuples, and that starting with q 0 the head never goes to the left of position 0 (this is equivalent to say that the machine works only on the right side of the tape). Let us define M ′ just like M but with an additional state q aux , and some small differences in its transition function δ: δ(q F , s) = (q aux , s, -1), and δ(q aux , s) = (q aux , s, -1), for every s ∈ Σ .

Thus, M reaches q F for some input (w, 0, q 0 ) if and only if the state q 0 is not a blocking state to the left for M ′ .

Theorem 1. (BS) is undecidable.

Proof. Let M = (Q, Σ, δ) be a Turing machine, and let q 0 , q F ∈ Q be two states. Let M ′ be a machine defined as in the last proof. Since M works only on the right side, we have that δ D (q 0 , s) = +1 for every s, thus q 0 is not s-blocking to the right for any symbol s. Therefore, q 0 is blocking to the left for M ′ if and only if q 0 is a blocking state for M ′ .

It results that the emptiness problem is satisfied for (M, q 0 , q F ) if and only if the blocking problem is satisfied for (M ′ , q 0 ).

Undecidability of the blocking state problem in complete RTMs

With the results of the last section, we discard the possibility of solving the problem of surjectivity via blocking states. However, knowing about the surjectivity of S T for a given machine M does not help to solve the blocking problem for a particular state q of M . Thus surjectivity can still be decidable. We want to reduce the blocking state problem to the surjectivity problem, but to do so we need to produce a machine whose surjectivity depends only on the blocking property of one of its states. This can be achieved by working with reversible machines, which are modified to make one of its states defective. That is why we introduce a new problem.

(BSLrtm) Given a complete and reversible Turing machine M and a state q that is reachable from the left, decide whether q is a blocking state to the left.

We prove the undecidability of this problem by reduction from the halting problem of reversible two counter machines, which is proved undecidable in [START_REF] Morita | Universality of a reversible two-counter machine[END_REF].

Definition 2. A k-counter machine (k-CM) is a triple (S, k, R),
where S is a finite set, k ∈ N is the number of counters, and R ⊆ S × {0, +} k × {1, .., k} × {-1, 0, +1}×S is the transition relation. A configuration of the machine is a pair (s, ν), where s is the current state and ν ∈ N k is the content of the k counters. By considering the function sign: N k → {0, +} k defined by sign(ν) j = 0 if ν j = 0 and + otherwise, an instruction (s, u, i, d, t) ∈ R can be applied to a configuration (s, ν) if sign(ν) = u, and the new configuration is (t, ν ′ ) where ν ′ j = ν j for every j = i and ν ′ i = ν i + d. R cannot contain the instruction (s, u, i, -1, t) if u i = 0. Just like Turing machines, a k-counter machine is said to be deterministic (k-DCM) if at most one instruction can be applied to each configuration. In addition, a k-CM C is said to be reversible (k-RCM) if it is forward and backward deterministic.

The halting problem consists in determining, given an initial configuration (s, ν), whether the machine reaches a given halting state t. It is undecidable for k = 2, even if the initial configuration is fixed to (s 0 , (0, 0)).

Theorem 2. (BSLrtm) is undecidable.

Proof. We prove undecidability by reduction from the halting problem of 2-RCM.

Let C = (S, 2, R) be a 2-RCM, with initial configuration (s 0 , (0, 0)) and final state t ∈ S. For this proof we need a Turing machine M and a state q = q 0 meeting the following:

1. it simulates C on the right side of the tape, 2. it is reversible, 3. it reaches the position -1 starting at 0 from q 0 if and only if C halts (reaches t) starting from (s 0 , (0, 0)), 4. it is complete, and 5. q 0 is reachable from the left.

If the machine meets the above objectives, q 0 will not be blocking to the left if and only if, starting from (s 0 , (0, 0)), C halts.

The first 3 objectives can be viewed in detail in the appendix; however, here we sketch them briefly. For simplicity, we define M in the quadruple form. For the first objective, we make a traditional simulation. Let M = (Q, Σ, δ) be a Turing machine. Starting with q 0 , the machine writes "< | >" into the tape, and goes to state s 0 (as seen in appendix, Part 1). This corresponds to the initial configuration (s 0 , (0, 0)) of the counter machine. The simulation will correctly work if the tape initially contains only 1s. In general, each configuration (s, (n, m)) of the counter machine will be represented in the Turing machine by the configuration (... ′ < 1 n |1 m > ..., 0, s). This will be achieved by simulating each instructions of C, as seen in the appendix, Part 2. In this way, M simulates C. It is noteworthy that, throughout the simulation, the machine does not reach the left side of the tape.

Providing simple safeguards, each counter machine instruction can be simulated by M in a reversible way. However, when reaching a state s ∈ S, while the counter machine knows whether each of its register is empty or not, the Turing machine does not, thus it may not be reversible in such situations. In order to solve this, the symbols of the form (d, d ′ ) are added to Σ, for each d, d ′ ∈ {0, +}; and we better represent C configurations by (...

′ (d, d ′ )1 n |1 m > ..., 0, s).
Now, for the third goal, when M reaches the halting state t of C, we add an extra transition to move to the left: (t, /, -1, t aux ). Thus M is able to reach the -1 starting from q 0 if and only if C halts when it starts from (s, (0, 0)).

Next, for the fourth objective, we use an idea from [START_REF] Kari | Periodicity and immortality in reversible computing[END_REF]. Create a new machine M ′ = (Q ′ , Σ, δ ′ ), with Q ′ = Q ∪ {+, -}. States of the form (q, +) act in the same way that in the M machine, and states of the form (q, -) makes the reverse transitions. Each transition not defined for M , switch + by -; analogously, transitions not defined in the reverse makes -to become +. This makes M ′ complete.

The fifth goal is attained by modifying M ′ in only one instruction: ((q 0 , -), /, 0, (q 0 , +)) is switched by ((q 0 , -), /, +1, (q 0 , +)). Thus, q 0 is a blocking state to the left, reachable from the left, for the complete reversible TM M ′ , if and only if C does not halt (reaches the t state) from (s 0 , (0, 0)).

Remark 3. The same machine can be used to proof that the emptiness problem for reversible and complete TM is undecidable, We simply make q = q 0 and q ′ = t.:

(E RCT M ) Given a reversible and complete TM M = (Q, Σ, δ) and two states q, q ′ ∈ Q, decide if there exists a configuration (w, 0, q) such that the state q ′ is attained in finite time. associated to a Turing machine (Surj) Given a deterministic and complete Turing machine written in quintuples, decide whether its t-shift is surjective.

Theorem 3. (Surj) is undecidable.

Proof. We prove the undecidability by reduction from (BSLrtm). Let M = (Q, Σ, δ) be a complete and reversible Turing machine. Let q ′ be a state that is reachable from the left, and let q, s and s ′ be such that δ(q, s) = (q ′ , s ′ , +1). We know that this machine is surjective. We assume that δ is written as a function. Now let us define M ′ as M , but with an additional state q aux and the following new instructions:

(∀t ∈ Q) δ(q aux , t) = (q ′ , t, 0) . and changing δ(q, s) = (q ′ , s ′ , +1) by δ(q, s) = (q aux , s ′ , +1). M ′ is not surjective, because the configuration (w, i, q aux ) has not preimage if w i-1 = s ′ . So q aux is the unique defective state of M ′ . In this way, if q ′ is a blocking state to the left for M , then so is q aux and since it is also reachable from the left, the t-shift of M ′ is surjective. On the other hand, if this t-shift is surjective, q aux must be blocking. As q aux is only reachable from the left, it must be blocking to the left. This is possible only if q ′ is blocking to the left.

Conclusions

Surjectivity of the t-shift of a Turing machine resulted to be not equivalent to the surjectivity of the machine it self. The last property was characterized in terms of another property of the Turing machine, the blocking property of its states: in the absence of the surjectivity of the Turing machine, some of its states must be blocking.

But the blocking property resulted to be undecidable as well as the surjectivity of the t-shift. A rather simple problem in Turing machines can not be decided in t-shift, so we think that others more complicated problems (for example, transitivity) can not be decided too, but this will require a more deep investigation.

⋆ This work has been supported by CONICYT FONDECYT #1090568 and BASAL project CMM, Universidad de Chile, and CI 2 MA, Universidad de Concepción.

Appendix

Construction of the Turing machine shown in the proof or Theorem 2. We will construct a reversible Turing machine M = (Q, Σ, δ) to simulate a 2-reversible counter machine C = (S, 2, R). Q = S ∪ Q 0 ∪ S 1 ∪ ... ∪ S |R| , where Q 0 is the set of states required for writing "< | >" on the tape, including q 0 , and S i the set of states needed to simulate the instruction i of R. Σ = {<, |, >, 1} ∪ {0, +} 2 . The first set recreates the counters on the machine and the second contains auxiliary symbols indicating the status of the counters when reaching a new state.

The transition function is given by a graph, the notation is described in figure 1. It is noteworthy that this machine simulates arbitrary counter machine, so we will describe only generic instructions.

In general, each configuration (s, (n, m)) of the counting machine will be represented in the Turing machine by the configuration (< 1 n |1 m >, 0, s). The machine simulates C from configuration (s 0 , (0, 0)), by writing "< | >" on the tape. Subsequently, the machine adds and removes 1's from the tape, accordingly to the instructions of C. The machine will work as long as the background is full of 1's (the new visited cells), if it encounter any other symbol, it stops. It is important to note that, before reaching any state of C, the machine replaces the symbol "<" by the pair (d, d ′ ) ∈ {0, +} 2 , in order to indicate the sign of each counter at the end of each instruction. In this way, the machine knows which of the instructions of the counter machine is the next to be applied. And this makes the reversibility of the counter machine to be inherited by the Turing machine.

Fig. 2: The routine that writes the sequence "< | >" in the tape.

Part 2: Executing instructions. Let us suppose that the following instructions are in R: (s, (0, 0), i, d, t), (s, (0, +), i ′ , d ′ , t ′ ), (s, (+, 0), i ′′ , d ′′ , t ′′ ) y (s, (+, +), i ′′′ , d ′′′ , t ′′′ ). They are simulated with the routine depicted in figure 3.

(s, (0, 0), i, d, t) (s, (0, +), i ′ , d ′ , t ′ ) (s, (+, 0), i ′′ , d ′′ , t ′′ ) (s, (+, +), i ′′′ , d ′′′ , t ′′′ ) (0, 0)/ < (0, +)/ < (+, 0)/ < (+, +)/ < 0 0 0 0 Fig. 3: Depending on the sign of the counters, the machine performs the instruction (s, (0, 0), i, d, t), (s, (0, +), i ′ , d ′ , t ′ ), (s, (+, 0), i ′′ , d ′′ , t ′′ ) or (s, (+, +), i ′′′ , d ′′′ , t ′′′ ).

Part 3: Addition/Subtraction. Each sub-routine uses an exclusive set of states. There are several cases, depending on the sign of each counter, but they are all similar, thus we present only two examples in figures 4 and 5.

Fig. 4: Sub-routine corresponding to instruction (s, (+, +), 1, +, t ′′′ ), it adds one unit to counter 1, assuming counter 2 non empty.

Fig. 5: Sub-routine corresponding to instruction (s, (0, +), 2, -, t ′ ), it subtracts from counter 2, assuming counter 1 empty.


Two teaching approaches in geotechnical engineering S. Perlo, Assist. Prof., Univ. Paris-Est, IRC-ESTP

Teaching to future engineers raises many questionsthatmay be divided into three categories.

The first one seems to be often forgotten compared to the theoretical knowledge: "what should an engineer know or rather what he should know to do?"Naturally follows the second category of questions, after "what to teach?", is "how to teach?". The third one appears automatically "how do our students learn?" We will see that the way the students learn depends more on the choice of the assessment process. Obviously all these questions are connected together and lead to many others questions. It will be sure that, as teachers, we have much more questions than answers or solutions.

Trying to consider all these aspects, I propose two approaches of geotechnical lessons to my studentsat ESTP ("EcoleSpéciale des Travaux Publics, du Bâtiment et de l"Industrie") depending on the notions to pass on. ESTP is one of the French "GrandesEcoles" which will be furtherpresented on this communication.

In the first category a preliminary question could be:"what is an engineer?" Different definitions can be found. The CTI (Commission des Titresd"Ingénieur -Engineering Degree Commission) has adopted the following global definition of engineering(CTI Web site): "Engineering can be defined as the posing and answering of complex questions in an effective and innovative way, in the fields of creation, design, production and implementation, within a competitive environment and with a focus on products, systems or services, and possibly their financing and sale. As such, engineers should have a good understanding of technical, economic, social and human issues, based upon a solid scientific background."And the ESTP considers that the objective of French engineering education is to provide (ESTP Web site):  a high level general scientific knowledge that enables the engineer during his whole professional life to evolve and to adapt to new techniques;  a specialized education that will allow him to possess technical skills and to be operational as soon as he graduates;  a thorough general education that will prepare the future engineer to become a manager in the international market;  an introduction to applied research and innovation activities in order to train creative, innovative and open-minded professionals. We can notice (see the underlined words) that not only the knowledge but also the know-how are aimed at, and even more, their capacity of evolutionin order to adapt themselves to new concepts/tools/situations/technologies … In civil engineering, the necessary job skills should be able to solve problems, i.e. to understand, to analyze and last but not least to make a decision. Now we know the goal to reach, the question is "how?" And this "how" depends on how our students learn, which means that we should look at their basic education.

For that we should explain the French higher scientific curricula. In France, the title of "engineer" and the professional habilitation that goes with it, is awarded with five year degree, accredited by a national authority, theCTI. Studies are normally accomplished in a "Grande Ecoled"Ingénieur". Indeed because of many political conflicts since the 16thcentury, the French higher education is very specific, the only one of its kind in Europe with its "GrandesEcoles" (which is translated literally as"Higher Schools") as "Ecole des Ponts" since 1747, "Ecole des Mines" since 1783, "Ecolepolytechnique" and "EcoleNormaleSupérieure" since 1794). Even if a real definition of this kind of advanced education doesn"t exist, today approximately 170 public and 68 private higher schoolsare authorized to deliver the engineeringdegree (ATTALI, 1998).Thus, to follow higher scientific curricula (until master degree), Universities, "higher school" and so-called "Classes higher integrated school" are proposed. The "GrandesEcoles" are distinguished by a highly selective admission process, a limited number of students and quality programs, after generally two years in specialized institutions, so-called "Classes préparatoires aux GrandesEcoles" ("Preparatory course for entrance to GrandesEcoles"). Only the best students, with high marks in scientific subjects at the secondary education are admitted. The syllabus of these classes is focused on sciences (mathematics, physics, chemistry, general engineering science).(ESTPWeb site), and their teaching are more theoretical and rigorous in order to prepare to competitive examination, there is no space time for practical learning. According to the observatory ofstudent"s life, a student in this kind of training works near 60 hours a week (ONISEP Web site). The numbers of studentsislow, and the evaluations are numerous and regular. However, it is well known that the kind or type of assessment influences the learning process of the student. I think that it is often their first question to their professor: "What are you expecting us to know? What kind of evaluation we will have?" The evaluation conditions the process of learning. We can quote DE KETELE"s sentences [START_REF] De | Objectifsterminauxd"intégration et transfert des connaissances[END_REF]( , in RICHARD, 2004)): "Tell me how you assess and I"ll tell you what your pupils or students learn really […]".Thus the educational treatment of knowledge generally appears inseparable from the processes used to assess it. Indeed several roles of assessment can be cited: (ENDRIZZI and REY, 2008)  certification assessment, i.e. to prove of training;  summative assessment, i.e. to check whether knowledge and competencies have been acquired;  forecasting assessment, i.e. to assess the level reached and the student"s potential to continue in one way or another. Many studies deal with the evaluation, which has a central place in sciences of education [START_REF] Lieury Alain | Manuel de psychologie de l"éducation et de la formation[END_REF]coll., 1996, in LETE Bernard, 1999). But even so, we realize that everywhere in the world the School system attaches too much importance to the assessment of the learning and not enough to the assessment FOR the learning [START_REF] Smith Ian | L"évaluation et l"apprentissage[END_REF]. Nevertheless the term assessment often makes a reference to a summative one: a makk is given for each knowledge to require at a given time.From this outcomes issue, the student has to make the efforts to work again on his paper in order to make progress and complete his learning, and in an autonomous way [START_REF] Coince | Unoutil de diagnostic et d"évaluation pour aider l"élève en physique-chimie[END_REF]. We have many doubts about such a process. That"s why several solutions in order to help students to understand their weaknesses are developed, such asrubrics, scoring scale used to assess student performance along a task-specific set of criteria (MUELLER, 2012[START_REF] Dannelle | Introduction to Rubrics: An Assessment Tool to Save Grading Time, Convey Effective Feedback and Promote Student Learning[END_REF][START_REF] Daele | Choisir ses strategies d"évaluation[END_REF]. We presented previously the necessary engineer job skills, the curricula and the process of learning of the French student intended for the "GrandesEcoles". Now we can tackle how to teach. In France, to teach in higher education there is generally no obligation to undergo formal training. But some studies seems to show that for the higher education teachers learning to teach is still a taboo, and the idea of training and support is often seen as a sign of either deprofessionalization or professionalization (ENDRIZZI, 2011). Sometimes professionals give a lecture. The share of their background is very interesting for a practical learning, but they are not better trained. As ENDRIZZI (2011) writes on the teachers coming from the research: "The identity of the profession is also primarily a matter of allegiance to a particular discipline: academics are researchers first, teachers second". Finally, the choice of the teacher is only based on his good expertise without watching his educational abilities. The case of academics teachers in higher education can be gone deeper with the paper of REGE [START_REF] Rege | Savoir ou être ? Savoirs et identités professionnels chez les enseignants universitaires[END_REF]BERTHIAUME (2009, in ENDRIZZI, 2011).I think that it is today difficult for a researcher to dose out his involvement and his pending times for learning task. Furthermore that the researchers are currently assessed only on their research, without regarding their performance in education, leading today to the food for thought. It is commonly considered that two approaches to teaching exist:  the "teacher-centered" or a "content-based" approachthe students are seen like a passive receivers of the knowledge (content) transmitted by the teacher;  the "student-centered" or a "learning-based" approach -The teacher focus on facilitating learning.

Maybe a few words about geotechnical engineering learning: it should be taught in different ways. It can be done through a stable and "definitive" view or conversely by putting emphasis on the partial and scalable nature [START_REF] Demougeot-Lebel | Identifier les conceptions de l"enseignementet de l"apprentissage pour accompagner le développementprofessionnel des enseignantsdébutants à l"université[END_REF]. [START_REF] Demougeot-Lebel | Identifier les conceptions de l"enseignementet de l"apprentissage pour accompagner le développementprofessionnel des enseignantsdébutants à l"université[END_REF] suggest using the history of geotechnical engineering to teach because it gives "an opportunity to draw the students' attention, to show them the constant evolution and relativity of knowledge, to illustrate the role of observation and experimental analyses in the activities of engineers and help the students in understanding the particularities of geotechnical engineering with respect to mathematical and mechanical sciences […]". When I began teaching geotechnical engineering at ESTP I thought to teach like my higher education teachers did. Thus I thought to present at first the soil mechanics as organized for example in the well-known books of Schlosser"s (1997) or [START_REF] Philipponnat | Fondations et ouvrages en terre[END_REF].Like many young teachers (DEMOUGEOT-LEBEL and PERRET, 2010a and 2010b, in ENDRIZZI I was so anxiousthat my teaching approach was completely teacher-centered, headed more for subject knowledge than student support. Once passed the teaching stress of this first year, I could be able to think on what was important to transmit. According to the WIGGINS and MC TIGHE (1998), the "Enduring Understanding", "What is important to know and to do", and "What is non-essential but worth being familiar with" should be defined.

Concerning the geotechnical engineering learning, I think that the most important is to understand and to analyze (critic approach) a geotechnical report, to be able to discuss with geotechnician and to deal with all the stakes and identify all the risks…I began thinking about what they understand and memorize, and above all "why?", then how they learned. And now I think that they often looked only to obtain a good assessment. It was mainly scramming, they just learned by rote, because our often certification assessment leads to this process, mainly with the Preparatory course for entrance to "GrandesEcoles". But, I think that our role is to transform our students in good professional, and then they should have sustainable knowledge and analyze skills. Then the question for me was how to make understand the utility of some knowledge in Geotechnics. Then I began to redesignpathology centered knowledge. The easiest subject is undoubtedly the swelling and shrinkage of clay, which permit, among others, to introduce what is the soil, its origin, its characteristics, the nature"s influence on its behavior and so,many laboratory tests (Atterberg limits ,Particule-size analysis, …), but even the three kinds of water (hygroscopic, capillary, gravitational/free). What is even more interesting is to show the students the tight link with the structure"s behavior. My teaching approach tries to put emphasis on the understanding of physical phenomena, because I think that it facilitates the sustainable memorization. This entrance by the pathology or the physical phenomena lends itself to the soil mechanics, but it is less adapted to teach engineering design. I would like laying great stress on the place of the geotechnical in the building out. Thus I opted for the project based learning approach. The goal is to make them a kind of geotechnical report.

According to the geotechnical map they should define the geological profile and determine all the possible risks (and quote which are not concerned) with all the necessary justifications. After that, they should determine the geotechnical investigations, i.e. "which tests?", "where?", "how many?"… I give them the tests results and they should choose the kind of foundation and design it. Sometimes, they should design a pumping rate and a retaining system. I think that with the project based learning approach the students follow all the activities of Bloom taxonomy (BLOOM, 1954), i.e. "remember", "understand", "apply" and "Analyze-Evaluate-Create". And when we analyze the project by the Eight learning events model (LECLERCQ and POUMAY, 2005) we use six learning activities: "Receive information" + "Explore"+"Experiment"+"Create"+"Self-reflect" (missing learning activities: "Imitate", "Exercise", "Debate"). Concerning the project based learning approach we can refer to the Catherine Reverdy"s paper (2013).

One last important thing is to give to the students a detailed syllabus which includes not only the course outline, but even the expectation of the professor and the outcomes of this teaching and a real place in the curriculum of future engineers.

Since my teaching experience is not very long, I can"t say that the approach by the pathologies or the project based learning approach are very decisive, I should set up a feed-back assessment. Nevertheless, these approaches allow students to realize the link with real engineer"s situations and difficulties. They are openedto cross-disciplinaryapproaches … Finally I also think that some learning doesn"t require teachers, i.e they don"t provide a real support, and thus I would like to test the flipped-classroom in the near future.


joint work with O Claire Amiot

I Iyama

S Reiten

Oppermann

Preprojective algebras and Calabi-Yau duality

The properties of the preprojective algebra are very different whether the associated quiver is of Dynkin type or not. However in both cases, one can construct from it a triangulated category of Calabi-Yau dimension 2. In this note we explain the generalizations of this fact in the context of higher preprojective algebra, and we give some homological properties that characterize preprojective algebras.

Classical case

Let k = k be an algebraically closed field. Let Q be a finite quiver. The double quiver Q of Q is defined from Q by adding for each arrow a ∈ Q 1 an arrow a in the opposite direction. The preprojective algebra of Q is defined by

Π Q := kQ/ a∈Q1 [a, a] .
This notion has been defined by Gelfand and Ponomarev in [START_REF] Gelfand | Model algebras and representations of graphs[END_REF].

Example 1.1. Let Q be the following quiver 1 To preprojective algebras we can associate some triangulated categories with a duality of Calabi-Yau type. Definition 1.3 (Kontsevich). Let T be a k-linear triangulated category with finite dimensional Hom spaces. The category T is said to be d-Calabi-Yau if for all objects X, Y in T , there exists an isomorphism Hom T (X,

x z z . Then we have kQ ∼ = k[x]. The preprojective algebra of Q is presented by the quiver 1 x z z x $ $ with the relation xx -xx = 0. That is Π Q ∼ = k[x, x].
Y ) ∼ = DHom T (Y, X[d]) functorial in X and Y .
The link between preprojective algebras and Calabi-Yau categories is given by the following classical result.

Theorem 1.4. [START_REF] Erdmann | On Hochschild cohomology of preprojective algebras I,II[END_REF][START_REF] Crawley-Boevey | On the exceptional fibres of Kleinian singularities[END_REF][START_REF] Brenner | Periodic algebras which are almost Koszul[END_REF] Let Q be a finite quiver without oriented cycles. Then

• if Q is Dynkin, the preprojective algebra Π Q is finite dimensional selfin- jective and the stable category mod Π Q is 2-Calabi-Yau. • if Q is not Dynkin, then Π Q is infinite dimensional and the bounded derived category D b (fd Π Q ) of finite dimensional Π Q -modules is 2-Calabi-Yau.
The aim of this note is to explain how this result generalizes to higher preprojective algebras. As a tensor algebra, the preprojective algebra of Λ is naturally equipped with a structure of positively graded algebra, with Λ as degree 0 subalgebra. Remark 2.2. Ringel showed in [START_REF] Ringel | The preprojective algebra of a quiver, Algebras and Modules[END_REF] (see also [START_REF] Baer | The preprojective algebra of a tame hereditary Artin algebra[END_REF]) that there is an isomorphism

Higher preprojective algebras

Π Q ∼ = Π(kQ).
Example 2.3. If Λ is the the polynomial algebra in d variables, it has global dimension d and its associated preprojective algebra is isomorphic to the polynomial algebra in d + 1 variables.

From now on Λ we only consider the case where Λ is finite dimensional. We denote by

S -1 d = - L ⊗ Λ RHom Λ e (Λ, Λ e )[d]
the autoequivalence of the derived category D b (Λ). We define the following subcategories of D b (Λ):

U = add{S -p d Λ, p ∈ Z} and U + = add{S -p d Λ, p ∈ N}. Definition 2.4. [11, 10] Let Λ be a finite dimensional algebra of global dimen- sion d. Then • Λ is said d-representation finite (d-RF) if U = U[d]. • Λ is said d-representation infinite (d-RI) if U + ⊂ mod Λ.
Since the algebra Λ has global dimension d, we have an isomorphism between H 0 (S -p d (Λ)) and Ext d Λ e (Λ, Λ e ) ⊗p which is the homogeneous part of degree p of Π(Λ). Therefore one verifies that if Λ is d-RF, then Π(Λ) is finite dimensional, and if Λ is d-RI, then Π(Λ) is infinite dimensional.

For d = 1, the functor S -1 1 is isomorphic to τ -1 the inverse of the Auslander-Reiten translation of the derived category D b (kQ). Then using Gabriel's theorem it is immediate to check the following equivalences:

kQ is 1-RF ⇔ Q is Dynkin ⇔ kQ is representation-finite kQ is 1-RI ⇔ Q is non Dynkin ⇔ kQ is representation-infinite.
Example 2.5. Let Λ be the algebra presented by the quiver 1 a / / 2 b / / 3 with the relation ba = 0. Then Λ is 2-RF. The preprojective algebra of Λ is presented by the following quiver with relations:

2 b ❂ ❂ ❂ ❂ ❂ 1 a @ @ ✁ ✁ ✁ ✁ ✁ 3 c o o ba = cb = ac = 0.
There is a systematic way of constructing the preprojective algebra of an algebra of global dimension 2. We refer to [START_REF] Keller | Deformed Calabi-Yau completion. With an appendix of Michel Van den Bergh[END_REF] for a description of the precise construction.

Example 2.6. Let Λ be the algebra presented by the quiver 1 y / /

x / / z / / 2 y / /

x / / z / / 3 with the commutativity relations. Then Λ is 2-RI. The preprojective algebra of Λ is presented by the following quiver with the commutativity relations:

2 ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ ❃ 1 @ @ @ @ @ @ 3 o o o o o o .

Results

d-RI case.

The first result can be understood as a generalization of the non Dynkin case of Theorem 1.4. Furthermore it gives a homological characterization for the preprojective algebras of d-RI algebras.

Theorem 3.1. [START_REF] Keller | Deformed Calabi-Yau completion. With an appendix of Michel Van den Bergh[END_REF][START_REF] Herschend | n-representation infinite algebras[END_REF][START_REF] Minamoto | Structures of AS regular algebras[END_REF][START_REF] Amiot | Stable categories of Cohen-Macaulay modules and cluster categories[END_REF] Let Γ = i≥0 Γ i be a graded algebra with finite dimensional degree zero part Λ := Γ 0 . Then the following are equivalent

(1) Λ is d-RI, has global dimension d and Γ ∼ = Π(Λ) as graded algebras;

(2) Γ is (1)-twisted bimodule (d + 1)-Calabi-Yau.

Property ( 2) is an algebraic (and graded) enhancement of the (d+1)-Calabi-Yau property for the category D b (fd Γ). This is the bimodule property that must be satisfied by Γ to ensure that D b (fd Γ) is (d + 1)-Calabi-Yau. It is given as follows: (2) Γ is selfinjective and (1)-twisted stably bimodule (d + 1)-Calabi-Yau.

Here again, property ( 2) is an algebraic (and graded) enhancement of the (d+1)-Calabi-Yau property for the category mod Γ. This is the bimodule property that must be satisfied by Γ to ensure that mod Γ is (d + 1)-Calabi-Yau. It is given as follows:

(2) ⇔ Hom In general the finite dimensional preprojective algebras are not selfinjective but their behaviour is still similar to the one of the preprojective algebras of d-RF algebras. In the case d = 2, it is shown in [START_REF] Amiot | Cluster categories for algebras of global dimension 2 and quivers with potential[END_REF] that when Π(Λ) is finite dimensional, it is the endomorphism ring of a cluster-tilting object in a certain 2-Calabi-Yau category. Keller and Reiten proved that such algebras are Gorenstein (that is projdimDΠ = injdimΠ < ∞). Hence the correct analogue Calabi-Yau triangulated category is given by the stable category of maximal Cohen-Macaulay Π-modules. Indeed they proved in [START_REF] Keller | Cluster-tilted algebras are Gorenstein and stably Calabi-Yau[END_REF] that the category CM Π(Λ) is 3-Calabi-Yau.

These results were the motivation for the following characterization of finite dimensional preprojective algebras. Here property (b) is again an algebraic (and graded) enhancement of the (d+1)-Calabi-Yau property of the category CM Γ.

One also shows in [START_REF] Amiot | Higher preprojective algebras and stably Calabi-Yau properties[END_REF] that these properties are satsified by finite dimensional preprojective algebras in the case d = 2 and d = 3 using the description of Π(Λ) in term of quivers with relations.

Example 1 . 2 . 1 a

 121 Let Q be the quiver 1 a / / 2 . Then the preprojective algebra of Q is presented by the quiver aa = aa = 0.

Definition 2 . 1 (

 21 Iyama, Keller). Let Λ be a k-algebra of global dimension d. The ((d + 1)-) preprojective algebra of Λ is the tensor algebra Π(Λ) := T Λ Ext d Λ e (Λ, Λ e ) where Λ e = Λ op ⊗ k Λ is the envelopping algebra.

( 2 )

 2 ⇔ Γ ∈ per Γ e and RHom Γ e (Γ, Γ e )[d + 1] ∼ = Γ(1) in D(gr Γ e ). Here Γ(1) is the graded bimodule whose degree p part is Γ p+1 . Theorem 3.1 is stated in [10, Thm 4.35]. The implication (1) ⇒ (2) follows from [13, Thm 4.8], while (2) ⇒ (1) was shown indenpendently in [14, Thm 4.8] and [2, Thm 3.4]. 3.2. d-RF case. The next result is the d-RF analogue of Theorem 3.1. It can be seen as a generalization of the Dynkin case of Theorem 1.4, and gives a homological characterization of the preprojective algebras of d-RF algebras. Theorem 3.2. [7, 3] Let Γ = i≥0 Γ i be a finite dimensional graded algebra. Denote by Λ its degree zero part. Then the following are equivalent (1) Λ is d-RF, has global dimension d and Γ ∼ = Π(Λ) as graded algebras;

3 . 3 .

 33 Γ e (Γ, Γ e )[d + 2] ∼ = Γ(1) in gr Γ e . The implication (1) ⇒ (2) is shown in [7, Thm 3.2], while the implication (2) ⇒ (1) is shown in [3, Thm 3.1]. Beyond the RF/RI cases. Most of algebras of global dimension d ≥ 2 are neither d-RF nor d-RI. So one could ask how Theorems 3.1 and 3.2 can be extended to general preprojective algebras. Here we focus on the case where the preprojective algebra is finite dimensional.

Theorem 3 . 3 .

 33 [START_REF] Amiot | Higher preprojective algebras and stably Calabi-Yau properties[END_REF] Let Γ = i≥0 Γ i be a (non trivially) graded finite dimensional algebra. Denote by Λ its degree zero part. Assume that (a) Γ is Gorenstein of dimension ≤ d -1; (b) there is an isomorphism RHom Γ e (Γ, Γ e )[d+2] ∼ = Γ(1) in D b (gr Γ e )/per gr Γ e . (c) Ext i Γ e (Γ, Γ e (j)) = 0 for any i ≥ 1 and any j ≤ -1. Then Λ has global dimension d and Γ ∼ = Π(Λ) as graded algebras.