Bruno Guillon
email: bruno.guillon@uca.fr

Giovanni Pighizzini
email: pighizzini@di.unimi.it

Luca Prigioniero
email: prigioniero@di.unimi.it

Daniel Průša

Weight-reducing Turing machines

Keywords: one-tape Turing machines, descriptional complexity, Hennie machines

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

Introduction

The characterization of classes of languages in terms of recognizing devices is a classical topic in formal languages and automata theory. The bottom level of the Chomsky hierarchy, i.e., the class of type 3 or regular languages, is characterized in terms of deterministic and nondeterministic finite automata (dfas and nfas, respectively). The top level of the hierarchy, i.e., type 0 languages, can be characterized by Turing machines (in both deterministic and nondeterministic versions), even in the following restricted case: there is only a single (infinite or semi-infinite) tape, which initially holds only the input, and whose contents can be rewritten by the finite control.

Considering machines that make a restricted use of space or time, it is possible to characterize other classes of the hierarchy. On the one hand, if the available space is restricted only to the portion of the tape that initially contains the input and nondeterministic transitions are allowed, the resulting model, known as linear-bounded automaton, characterizes type 1 or context-sensitive languages [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF]. On the other hand, when the length of the computations, i.e., the time, is linear in the input length, one-tape Turing machines are no more powerful than finite automata; namely they recognize only regular languages, as proved by Hennie in 1965 [START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF]. 3recurs ively enumera ble (type 0) regular (type 3) context -sensit ive (type 1) d e te rm in is ti c co n te xt -s en si ti ve weight-reducing dHms (wrdHms) deterministic Hennie machines (dHms) halting wrdTms end-marked dTms linear-time dTms weight-reducing dTms (wrdTms) one-tape deterministic Turing machines (dTms)

Figure 1: Variants of one-tape deterministic Turing machines and their expressive power confronted with the Chomsky hierarchy. In particular, end-marked dTms are known as deterministic linear bounded automata in the literature, and recognize the so-called deterministic context-sensitive languages, a subclass of context-sensitive languages; see [START_REF] Walters | Deterministic context-sensitive languages: Part II[END_REF]. It is still unknown if this inclusion is strict. Each line, from top to bottom, connects a model with one of its special cases.

The main purpose of this paper is the investigation of some fundamental properties of several variants of one-tape Turing machines running in linear time. We now give an outline of the motivation for this investigation and of the results we present. (Figure 1 summarizes the models we are going to discuss and their relationships.)

A natural question concerning models that share the same computational power is the comparison of the sizes of their descriptions. In this respect, one could be interested in comparing one-tape Turing machines running in linear time with equivalent finite automata.

Here, we prove that there exists no recursive function bounding the size nonregular language recognition, have been stated in the literature [START_REF] Trakhtenbrot | Turing machine computations with logarithmic delay[END_REF][START_REF] Hartmanis | Computational complexity of one-tape Turing machine computations[END_REF][START_REF] Michel | An NP-complete language accepted in linear time by a onetape Turing machine[END_REF][START_REF] Pighizzini | Nondeterministic one-tape off-line Turing machines[END_REF][START_REF] Tadaki | Theory of one-tape linear-time Turing machines[END_REF].

blowup resulting from the conversion from one-tape Turing machines running in linear time into equivalent finite automata. Hence, one-tape linear-time Turing machines can be arbitrarily more succinct than equivalent finite automata. Furthermore, the problem of deciding whether a given one-tape Turing machine runs in linear time is undecidable, in general. 4 These results remain true in the restricted case of end-marked machines-namely, one-tape deterministic Turing machines that do not have any extra space, other than the tape portion that initially contains the input. Deterministic end-marked machines running in linear time will be called Hennie machines.

To overcome the above-mentioned "negative" results, we consider a syntactical restriction on one-tape deterministic Turing machines, thus introducing weight-reducing Turing machines. This restriction aims to force the machine to run in linear time, by making any tape cell rewriting decreasing according to some fixed partial order on the tape alphabet. However, due to the unrestricted amount of available tape space, these devices can have non-halting computations. Nevertheless, they run in linear time as long as they are halting. Indeed, we prove that each computation either halts within a time that is linear in the input length, or is infinite. In the paper we show that it is possible to decide whether a weight-reducing Turing machine is halting. As a consequence, it is also possible to decide whether such a machine runs in linear time. Furthermore, with a polynomial size increase, any such machine can be made halting, and hence forced to run in linear time.

Our main result is that the tight size cost of converting a weight-reducing Turing machine into a dfa is double exponential. This cost reduces to a simple exponential when the target device is an nfa.

Considering end-marked Turing machines satisfying the weight-reducing syntactic restriction, we obtain weight-reducing Hennie machines. These devices do not allow infinite computations, and hence always run in linear time. The above-stated double exponential blowup is easily extended to them.

The paper is organized as follows. Section 2 presents the fundamental notions and definitions, including those related to the computational models we are interested in. Section 3 is devoted to prove the above-mentioned undecidability and non-recursive trade-off results concerning Hennie machines.

In Section 4, after proving that it can be decided if a deterministic Turing machine is weight-reducing, we describe a procedure that, given a linear-time machine together with the coefficient of its linear bound on time, turns it into an equivalent weight-reducing machine. Furthermore, we present a simulation of weight-reducing machines by finite automata, studying its size cost.

In Section 5 we show how to decide if a weight-reducing machine halts on any input and if it runs in linear time. We also prove that with a polynomial increase in size, each weight-reducing machine can be transformed into an equivalent one that always halts and runs in linear time.

Preliminaries

In this section we recall some basic definitions and notation. We also describe the main computational models considered in the paper.

We assume the reader familiar with notions from formal languages and automata theory (see, e.g., [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]). For a set S, its cardinality is denoted by #S and 2 S is the family of all its subsets. Given an alphabet Σ, the length of a string w ∈ Σ * is denoted |w|, the i-th symbol of w is denoted w i , i = 1, . . . , |w|, and ε denotes the empty string.

The main computational model we consider is the deterministic one-tape

Turing machine (dTm). Such a machine is a tuple Q, Σ, Γ, δ, q 0 , F where

• Q is the set of states,
• Σ is the input alphabet,

• Γ is the tape alphabet including symbols of Σ and the special blank symbol , denoted by b, with b / ∈ Σ, that cannot be written by the machine,

• q 0 ∈ Q is the initial state,

• F ⊆ Q is the set of final states, and

• δ : Q × Γ → Q × (Γ \ { b}) × {-1, +1} is the partial deterministic transition function. 5
In one step, depending on its current state p and on the symbol σ read by the head, a dTm changes its state to q, overwrites the corresponding tape 5 For technical reasons, our Turing machines cannot write the blank symbol. Hence, when the machine scans a blank, it overwrites the contents of the cell with another symbol in Γ \ { b}. It is possible to notice that these machines have the same computational power as machines that can write the blank symbol on the tape. In fact, each machine that can write blanks can be replaced by a machine that writes an auxiliary symbol different than blank. In this way it can be proved that the power of these machines does not change.

cell with τ and moves the head one cell to the left or to the right according

to d = -1 or d = +1, respectively, if δ(p, σ) = (q, τ, d). Since δ is partial,
it may happen that no transition can be applied. In this case, we say that the machine halts. At the beginning of computation the input string w resides on a segment of a bi-infinite tape, called the initial segment, and the remaining infinitely many cells contain the blank symbol. The computation on input w starts in the initial state with the head scanning the leftmost symbol of w, if w = ε, or a blank tape cell, otherwise. The input is accepted if the machine eventually halts in a final state. The language accepted by a dTm A is denoted by L (A).

Let A = Q, Σ, Γ, δ, q 0 , F be a dTm. A configuration of A is given by the current state q, the tape contents, and the position of the head. If the head is scanning a non-blank symbol, we describe it by zqu where zu ∈ Γ * is the finite non-blank contents of the tape, u = ε, and the head is scanning the first symbol of u. Otherwise, we describe it by q bz or zq according to whether the head is scanning the first blank symbol to the left or to the right of the non-blank tape contents z, respectively. If the device may enter a configuration z q u from a configuration zqu in one step, we say that z q u is a successor of zqu, denoted zqu z q u . A halting configuration is a configuration that has no successor. The reflexive and transitive closure of is denoted by * . On an input string w ∈ Σ * , the initial configuration is q 0 w.

An accepting configuration is a halting configuration zq f u such that q f is a final state of the machine. A computation is a (possibly infinite) sequence of successive configurations. It is accepting if it is finite, its first configuration is initial, and its last configuration is accepting. Therefore, L (A) = {w ∈ Σ * | q 0 w * zq f u, where q f ∈ F and zq f u is halting}.

In the paper we consider the following restrictions of dTms (see Figure 1).

End-marked machines. We say that a dTm is end-marked , if at the beginning of the computation the input string is surrounded by two special symbols belonging to Γ, and respectively, called the left and the right endmarkers, which can never be overwritten, and that prevent the head to leave the portion of the tape that initially contains the input. Moreover, and can never be written by the machine. Formally, for each transition δ(p, σ) = (q, τ, d), τ = (resp., τ = ) if and only if σ = (resp., σ = ); furthermore, this implies d = +1

(resp., d = -1). For end-marked machines, the initial configuration on input w is q 0 w . We point out that end-marked machines are the deterministic restriction of the well-known linear-bounded automata [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF].

Notice that any machine without endmarkers can simulate an endmarked machine by overwriting the first blank to the left and to the right of the input word with special symbols representing the left and the right endmarker, respectively. Hence, end-marked machines can be seen as particular cases of machines without endmarkers.

Weight-reducing Turing machines. A dTm is weight-reducing (wr dTm), if there exists a partial order < on Γ such that each rewriting is decreasing, i.e., δ(p, σ) = (q, τ, d) implies τ < σ, for σ, τ / ∈ { , }. By this condition, in a wrdTm the number of visits to each tape cell is bounded by a constant. However, a wrdTm could have non-halting computations that therefore must visit infinitely many tape cells.

Linear-time Turing machines. A dTm is said to be linear-time if for each input w, its computation halts within O(|w|) steps.

Hennie machines. A Hennie machine (dHm) is a linear-time dTm that is, furthermore, end-marked.

Weight-Reducing Hennie machines. By combining previous conditions, weight-reducing Hennie machines (wr dHms) are defined as particular dHms, for which there exists a partial order < over Γ such that δ(p, σ) = (q, τ, d) implies τ < σ, for τ, σ / ∈ { , }. Observe that each endmarked wrdTm can execute a number of steps that is at most linear in the length of the input. Hence, end-marked wrdTms are necessarily weight-reducing Hennie machines.

We also consider finite automata. We briefly recall their definition. A nondeterministic finite automaton (nfa) is a computational device equipped with a finite control and a finite read-only tape that is scanned by an input head in a one-way fashion. Formally, it is defined as a quintuple A = Q, Σ, δ, q 0 , F , where

• Q is a finite set of states,
• Σ is a finite input alphabet,

• q 0 ∈ Q is the initial state,

• F ⊆ Q is a set of final states, and

• δ : Q × Σ → 2 Q is a nondeterministic transition function.
At each step, according to its current state p and the symbol σ scanned by the head, A enters one nondeterministically-chosen state from δ(p, σ) and moves the input head one position to the right. The machine accepts the input if there exists a computation starting from the initial state q 0 with the head on the leftmost input symbol, and ending in a final state q ∈ F after having read the whole input with the head to the right of the rightmost input symbol. The language accepted by A is denoted by L (A). An nfa A is said to be deterministic (dfa) whenever #δ(q, σ) ≤ 1, for any q ∈ Q and σ ∈ Σ. 6The notions of configurations, successors, computations, and halting configurations, previously introduced in the context of dTms, naturally transfer to nfas.

The size of a machine is given by the total number of symbols used to write down its description. Therefore, the size of a one-tape Turing machine is bounded by a polynomial in the number of states and of tape symbols. More precisely, the device is fully represented by its transition function. Hence, having a suitable encoding of the sets Q and Γ, since each element of a set A can be represented in size Θ(log #A), to specify the value δ(q, σ),

for q ∈ Q, σ ∈ Γ, size Θ(log(#Q • #Γ)
) can be used. So, since we have to specify the image of each element of the domain Q × Γ, the size of the machine is

Θ(#Q • #Γ • log(#Q • #Γ)). With the same argument, the size of a dfa is Θ(#Σ • #Q • log #Q).

Hennie Machines: Undecidability and Non-Recursive Trade-

Offs

In this section we investigate some basic properties of dTms. First of all, we prove that it cannot be decided whether an end-marked dTm runs in linear time. As a consequence, it cannot be decided if a dTm is a Hennie machine. Since linear-time dTms accept only regular languages [START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF], it is natural to investigate the size cost of their conversion into equivalent finite automata. Even in the restricted case of deterministic Hennie machines we obtain a "negative" result, by proving a non-recursive trade-off between the size of Hennie machines and that of the equivalent finite automata.

Let us start by proving the following undecidability result.

Theorem 1. It is undecidable whether an end-marked dTm runs in linear time.

Proof. We show that the problem of deciding if a dTm T = Q, Σ, Γ, δ, q 0 , F with a semi-infinite tape halts on the empty word ε reduces to this problem.

From T we can construct an end-marked Turing machine H with input alphabet {a} as follows. Given an input v ∈ a * , the device H starts to simulate T over ε; namely, the transitions of T on the blank symbol are simulated by moves of H on the symbol a. The portion of the tape storing the word v corresponds to the maximum amount of space that H is allowed to use for the simulation of T . If, during the simulation, H reaches the right endmarker, then it stops the simulation and performs additional Θ(|v| 2 ) computation steps. 7 Otherwise, H continues the simulation of T and halts if T halts.

One can verify that the construction yields the following properties:

• If T halts on ε in t steps visiting s tape cells, then H performs O(t) computation steps on any input of length greater than s, while it performs O(t 2 ) steps on shorter inputs. In both cases, the time is bounded by a constant in the input length.

• If T does not halt on ε, then for any input v either the simulation reaches the right endmarker and then H performs further Θ(|v| 2 ) computation steps, or it does not halt because T enters an infinite loop, without reaching such a tape cell. In both cases H is not a lineartime dTm.

This allows to conclude that H is a linear-time dTm if and only if T halts on input ε, which is known to be undecidable.

We now show that the size trade-off from linear-time dTm to finite automata is not recursive. More precisely, we obtain a non-recursive trade-off between the sizes of Hennie machines and finite automata.

Theorem 2. For any recursive function f and arbitrarily large integers n, of the initial segment with a special marker / ∈ Γ, moving the head to the right endmarker after each rewriting. More precisely, from the cell containing the right endmarker, H moves its head to the preceding cell and overwrites the contents with the special marker. After that, it moves its head to the right endmarker, then moves it backward to the rightmost cell not containing the special marker and writes , thus repeating the procedure until all tape cells but those containing the endmarkers have been overwritten with the special marker.

there is a dHm with O(n) states and a fixed tape alphabet whose equivalent finite automata require at least f (n) states.

Proof. We recall that a busy beaver is, among all possible n-state deterministic Turing machines with a two-symbol tape alphabet that start the computation over a blank tape, one that halts after writing on the tape the maximum possible number Σ(n) of (not necessarily consecutive) 1's. The function Σ(n) is known to be not bounded by any recursive function, i.e., it grows asymptotically faster than any computable function [START_REF] Radó | On non-computable functions[END_REF].

Here we consider a modification of the busy beaver that operates on a semi-infinite tape (instead of bi-infinite) and starts the computation on the leftmost cell, according to [START_REF] Walsh | The busy beaver on a one-way infinite tape[END_REF]. This variant defines a different function Σ(n)

that is also not bounded by any recursive function. As a consequence, the amount of the space s(n) used by this modified version of an n-state busy beaver is also not bounded by any recursive function.

For each n > 0, let w n = a s(n) and let Furthermore, the simulation of n-BB does not depend on the input. Hence, it is made in constant time. This allows to conclude that, with respect to the input length, H n runs in linear time, so it is a Hennie machine.

L n = {w n }.
By summarizing, L n is accepted by a dHm with O(n) states, so it is of size O(n log n). On the other hand, since the only string in L n is a s(n) , the minimum dfa accepting it requires s(n)+1 states, so its size is Θ(s(n) log s(n)).

Since s(n) is not bounded by any recursive function, this completes the proof.

Weight-Reducing Machines: Decidability, Expressiveness and Descriptional Complexity

In Section 3 we proved that it cannot be decided whether an end-marked dTm runs in linear time. In this section we show that it is possible to decide whether dTms are weight reducing. Furthermore, every linear-time dTm T with the length of each computation bounded by Kn + C, where K, C are constants and n denotes the input length, can be transformed into an equivalent weight-reducing machine whose size is bounded by a recursive function of K and the size of T .

We also present a simulation of weight-reducing machines by finite automata, thus concluding that weight-reducing machines express exactly the class of regular languages. From such a simulation, we will obtain the size trade-off between weight-reducing machines and finite automata that, hence, is recursive. This contrasts with the non-recursive trade-off from Hennie machines to finite automata, proved in Section 3.

Proposition 1. It is decidable whether a dTm is weight-reducing.

Proof. Let T = Q, Σ, Γ, δ, q 0 , F be a dTm. To decide if there is any order < on Γ proving that T is weight-reducing, it suffices to check whether the directed graph G = Γ, E , with

E = {(τ, σ) | ∃p, q ∈ Q ∃d ∈ {-1, +1} : δ(p, σ) = (q, τ, d)},
is acyclic (each topological ordering of G acts as the required order <).

We now study how linear-time dTms can be made weight-reducing. To this end, we use the fact that each dTm running in linear time makes a constant number of visits to each tape cell. This property is stated in the following lemma, which derives from [4, Proof of Theorem 3].

Lemma 1. Let T = Q, Σ, Γ, δ, q 0 , F be a dTm. If there exist two constants K and C such that every computation of T has length bounded by Kn + C, where n denotes the input length, then T never visits a tape cell

more than 2K • (#Q) K + K times.
The following lemma, which will be used in this section to study trade-offs between the computational models we are investigating and finite automata, presents a transformation from linear-time Turing and Hennie machines into equivalent weight-reducing ones.

Lemma 2. Let T = Q, Σ, Γ, δ, q 0 , F be a dTm such that, for any input, T performs at most k computation steps on each tape cell. Then there is a wr dTm A accepting L(T ) with the same set of states Q as T and tape alphabet of size O(k • #Γ). Furthermore, on each input A uses the same space as T , and if T is linear time or end-marked then so is A.

Proof. To obtain A, we incorporate a counter into the tape alphabet of T . For each scanned cell, the counter records the maximum number of visits A can perform during the remaining computation steps over the cell. More formally, letting Σ b denote the alphabet Σ ∪ { b}, we define A = Q, Σ, Γ , δ , q 0 , F

with Γ = Σ b ∪ ((Γ \ Σ b ) × {0, . . . , k -1})
and, for all q, q ∈ Q, a, a ∈ Γ, d ∈ {-1, +1} where δ(q, a) = (q , a , d), δ fulfils the conditions

δ (q, a) = (q , (a , k -1) , d) , if a ∈ Σ b , δ (q, (a, i)) = (q , (a , i -1) , d) , otherwise, for i = 1, . . . , k -1.
Using an ordering < on Γ such that

(a, i) < b for a ∈ Γ \ Σ b , b ∈ Σ b , i = 0, . . . , k -1, and
(a, i) < (b, j) for a, b ∈ Γ \ Σ b , i, j = 0, . . . , k -1, i < j,
it is easy to see that A is a wrdTm equivalent to T . Furthermore, there is a natural bijection between computations of T and those of A, which preserves time (length of computations) and space (cells visited during the computation). Thus, if T is linear time then so is A.

In the case T is end-marked, we can slightly modify the above construction of A, taking into account that, by definition of end-marked devices, the dTm T does not use the blank symbol and does not overwrite the endmarkers. The tape alphabet of

A is Γ = Σ∪{ , }∪((Γ \ (Σ ∪ { , })) × {0, . . . , k -1})
and, for all q, q ∈ Q, a, a ∈ Γ, d ∈ {-1, +1} where δ(q, a) = (q , a , d), δ fulfils the conditions

δ (q, a) = (q , (a , k -1) , d) , if a ∈ Σ, δ (q, a) = (q , a, d) , if a ∈ { , } , δ (q, (a, i)) = (q , (a , i -1) , d) , otherwise, for i = 1, . . . , k -1.
The ordering < on Γ is defined as

(a, i) < b for a ∈ Γ \ (Σ ∪ { , }), b ∈ Σ, i = 0, . . . , k -1, and
(a, i) < (b, j) for a, b ∈ Γ \ (Σ ∪ { , }), i, j = 0, . . . , k -1, i < j.
By combining the above lemmas, we obtain a procedure to convert lineartime Turing machines into equivalent linear-time weight-reducing machines, as soon as a linear-time bound for the simulated device is explicitly given.

Theorem 3. Let T = Q, Σ, Γ, δ, q 0 , F be a dTm. If there exist two constants K and C such that every computation of T has length bounded by Kn + C, where n denotes the input length, then there is an equivalent lineartime wr dTm with the same set of states Q as T and tape alphabet of size

O(k • #Γ), where k = 2K • (#Q) K + K.
Proof. Direct consequence of Lemmas 1 and 2.

We now investigate the transformation of weight-reducing machines into equivalent finite automata and its cost.

Theorem 4. For every wr dTm T = Q, Σ, Γ, δ, q 0 , F there exist an nfa and a dfa accepting

L(T ) with 2 O(#Γ•log(#Q)) and 2 2 O(#Γ•log(#Q)) states, respec- tively.
Proof. Assume T always ends each accepting computation with the head scanning a blank cell to the right of the initial segment. This can be obtained, at the cost of introducing one extra symbol in the tape alphabet, by modifying the transition function in such a way that when T enters a final state it starts to move its head to the right, ending when a blank cell is reached. Let n = #Q and m = #Γ.

We describe an nfa A = Q , Σ, δ , q I , F that accepts L(T ), working on the principle of guessing the time-ordered sequences of states in which, in accepting computations, T scans each of the tape cells storing the input.

This is a variant of the classical crossing sequence argument. In this case, for a tape cell C, we consider the sequence of states in which the cell is scanned during a computation, while a crossing sequence is defined as the sequence of states of the machine when the border between two adjacent tape cells is crossed by the head. In addition, in our simulation, together with the sequence of states, the input symbol is also guessed for the next cell.

Suppose that the time-ordered sequence of states in which a cell C is scanned in a computation ρ is (q 1 , . . . , q k ). Due to the weight-reducing property, there are k or k + 1 different contents of C in ρ, depending on whether the computation stops in q k . Since the tape alphabet consists of m symbols, we can conclude that k ≤ m.

The set of states Q thus consists of a special initial state q I , a special final state q F , and all sequences of the form (a, q 1 , . . . , q k ) where a ∈ Σ ∪ { b},

1 ≤ k ≤ m, and
q i ∈ Q, for i = 1, . . . , k.
Let w ∈ L(T ) be a non-empty input accepted by T . Let τ l , τ in and τ r denote the portion of T 's tape that initially stores the blank symbols preceding w, the input w, and the blank symbols to the right of w, respectively.

Let ρ = (C 0 , C 1 , . . .) be the accepting computation of T over w. Let q(j)

denote the state of T in configuration C j . Similarly, let a(j) denote the symbol scanned by T in C j . For a tape cell C in τ in , let C j 1 , . . . , C j k , where

j 1 < • • • < j k ,
be the sequence of all configurations in which T scans C. Observe that a(j 1 ) and q(j 1 ), . . . , q(j i-1 ) determine a(j i ) for all i = 2, . . . , k. For each configuration C j i , it is also clear from which direction the head entered C and in which direction it moves out of it (C j 1 is always entered from the left neighboring cell, unless it is the initial configuration; for i > 1, C j i is entered from the same direction as C j i-1 was left, namely, from the opposite direction than C j i-1 +1 was entered). For this reason, we can determine for two neighboring cells C 1 and C 2 of τ in whether two sequences of states assigned to them are consistent with T in the sense that the rightward head movements outgoing from C 1 have corresponding incoming leftward movements to C 2 and vice versa. Similarly, we can determine whether a sequence of states assigned to the first and last cell of τ in is consistent with the computation of T performed over the cells of τ l and τ r , respectively.

We now formalize these ideas.

Given (a, q 1 , . . . , q k ), (b, p 1 , . . . , p ) ∈ Q , with a, b ∈ Σ, let

• a 0 = a and, for i = 1, . . . , k, δ(q i , a i-1 ) = (q i , a i , d i ), q i ∈ Q, a i ∈ Γ,

d i ∈ {-1, +1}; • b 0 = b and, for i = 1, . . . , , δ(p i , b i-1 ) = (p i , b i , e i ), p i ∈ Q, b i ∈ Γ, e i ∈ {-1, +1}.
We say that (b, p 1 , . . . , p ) is consistent with (a, q 1 , . . . , q k ) when there are indices i 1 , i 2 , . . . , i t , h 1 , h 2 , . . . , h t , for some odd integer t ≥ 1, with

1 ≤ i 1 ≤ i 2 ≤ • • • ≤ i t = k, 1 = h 1 ≤ h 2 ≤ • • • ≤ h t ≤
, such that for j = 1, . . . , t the following holds: ) is consistent with (a, q 1 , q 2 , q 3 ). Notice that

a b q 1 q 2 q 3 p 1 p 2 p 3 p 4 p 5
t = 3, i 1 = 2, i 2 = i 3 = 3, h 1 = 1, h 2 = 3, h 3 = 4.
• if j is odd then q i j = p h j , d i j = +1, and, when j < t, i j < i j+1 ,

• if j is even then p h j = q i j , e h j = -1, and h j < h j+1 , while d i = -1 for i / ∈ {i 1 , . . . , i t }, and e h = +1 for h / ∈ {h 1 , . . . , h t }.

Notice that, for any odd j, in the transition from q i j to p h j the head crosses the border between the two adjacent cells by moving from left to right, while for any even j in the transition from p h i to q j i the head crosses the same border by moving in the opposite direction. Furthermore, the conditions t odd, i t = k, h 1 = 1, derive from the fact that, in each accepting computation of T , each cell of the initial segment is entered from the left (with the exception of the leftmost one) and is finally exited by moving the head to the right. (See Figure 2 for an example).

In a similar way, we are going to identify the sequences from Q that can occur on the rightmost cell of the initial segment in an accepting computation (remember that we suppose that when τ reaches a final state it starts to move its head to the right, ending when a blank cell is reached).

Using the above notation, we say that the blank tape segment is consistent with (a, q 1 , . . . , q k ) ∈ Q when there are indices

1 ≤ i 1 < i 2 < • • • < i t = k,
and strings γ 0 = ε, γ 1 , . . . , γ t ∈ Γ * , such that:

• d i j = +1, for j = 1, . . . , t, while d i = -1 for i / ∈ {i 1 , . . . , i t }; namely, the indices i j correspond to transitions moving the head to the right.

• For j = 1, . . . , t -1, T in the state q i j with the head scanning a tape cell C containing a i j -1 and the string γ j-1 written on the non-blank cells to the right of C, moves to the right and makes a finite sequence of moves, which ends when the cell C is re-entered. At this point the state q i j +1 and the string written on the non-blank cells to the right of C is γ j .

• From q it = q k the machine T moves its head to the right and, at some point, reaches a blank cell in a final state, without re-entering the cell C in between.

Let Q R denote the set of states (a, q 1 , . . . , q k ) ∈ Q such that the blank tape segment is consistent with (a, q 1 , . . . , q k ).

Finally, we now identify the sequences from Q that are consistent with τ l , namely sequences that could occur, in accepting computations, on the tape cell that initially contains the leftmost input symbol.

Given (a, q 1 , . . . , q k ) ∈ Q , with a ∈ Σ and, as before, a 0 = a and,

for i = 1, . . . , k, δ(q i , a i-1 ) = (q i , a i , d i ), q i ∈ Q, a i ∈ Γ, d i ∈ {-1, +1}, let 1 ≤ i 1 < i 2 < • • • < i t <
k be the indices corresponding to transitions moving the head to the left, i.e., {i 1 , i 2 , . . . , i t } = {i | d i = -1}. We say that (a, q 1 , . . . , q k ) is consistent with the blank tape segment when there are strings γ 0 = ε, γ 1 , . . . , γ t ∈ Γ * , such that:

• q 1 coincides with the initial state of T ,

• for j = 1, . . . , t, T in the state q i j with the head scanning a tape cell C containing a i j -1 and the string γ j-1 written on the non-blank cells to the left of C, moves to the left and makes a finite sequence of moves, up to re-enter C. At that point the state is q i j +1 and the string written on the non-blank cells to the left of C is γ j .

Let Q L denote the set of states from Q that are consistent with the blank tape segment.

At this point we have developed all the tools to define the automaton A = Q , Σ, δ , q I , F .

• The set of states is

Q = {q I , q F }∪{(a, q 1 , . . . , q k ) | a ∈ Σ∪{ b}, 1 ≤ k ≤ m+1, q i ∈ Q, i = 1, . . . , k}
as already mentioned.

• The initial state is q I .

• The transition function is defined, for (a, q 1 , . . . , q k ) ∈ Q , c ∈ Σ, as follows:

δ ((a, q 1 , . . . , q k ), c) =                      {(b, p 1 , . . . , p ) | (b, p 1 , . . . , p ) is consistent with (a, q 1 , . . . , q k )}, if c = a and (a, q 1 , . . . , q k ) / ∈ Q R {(b, p 1 , . . . , p ) | (b, p 1 , . . . , p ) is consistent with (a, q 1 , . . . , q k )} ∪ {q F }, if c = a and (a, q 1 , . . . , q k ) ∈ Q R ∅, otherwise.
The transitions from the initial state q I are defined, for a ∈ Σ, as follows:

δ (q I , a) = (a,q 1 ,...,q k )∈Q L δ ((a, q 1 , . . . , q k ), a) ,
while there are no transitions from q F ; namely δ (q F , a) = ∅, for a ∈ Σ.

• The set of final states is

F =    {q F } if ε / ∈ L(T ) {q I , q F }, otherwise.
By summarizing, the nfa A simulates T as follows:

• In the initial state q I , reading an input symbol a, the automaton A implicitly guesses a sequence (a, q 1 , . . . , q k ) ∈ Q L , i.e., a sequence consistent with the left tape segment, and a sequence (b, p 1 , . . . , p ) consistent with (a, q 1 , . . . , q k ), where b is supposed to be the symbol in the cell immediately to the right. If (a, q 1 , . . . , q k ) ∈ Q R is consistent with the right blank segment, then the one-symbol string a is accepted by T .

Hence in this case the final state q F can be also guessed.

• When scanning an input cell containing a symbol a, in a state (a, q 1 , . . . , q k ) ∈ Q , the machine A guesses a sequence (b, p 1 , . . . , p ) consistent with it.

If the next input symbol is b, then the simulation can continue in the same way, otherwise it stops because of an undefined transition.

Furthermore, when (a, q 1 , . . . , q k ) ∈ Q R , the device A can also guess to have reached the last input symbol, so entering the final state q F . If the end of the input is effectively reached then A accepts.

The number of states of

A is 2 + (#Σ + 1) m i=1 n i = 2 O(m log n) .
If A is in turn transformed to an equivalent dfa, using the classical powerset construction, the resulting automaton has 2 2 O(m log n) states.

As a direct consequence of Theorem 4, we get that wrdTms recognize exactly the class of regular languages. Corollary 1. A language is regular if and only if it is accepted by some wr dTm.

Theorem 4 gives a double exponential upper bound for the size cost of the simulation of wrdTms by dfas. We now also prove a double exponential lower bound.

To this end, for each integer n ≥ 0, we consider the language B n over

{0, 1, $} consisting of strings v 1 $v 2 $ • • • $v k , where k > 2, v 1 , v 2 , . . . , v k ∈ {0, 1} * , |v k | ≤ n, |v i | ≥ |v k | for i = 1, . . . , k -1,
and there exists j < k such that v j = v k . Informally, every string in B n is a sequence of binary blocks separated by the symbol $, where the last block is of length at most n and it is a copy of one of the preceding blocks, which all are at least as long as the last one. For example,

v 1 $v 2 $v 3 $v 4 $v 5 $v 6 = 0011$0101110$011$0011$001$011 ∈ B 4 since |v 6 | ≤ 4, |v i | ≥ |v 6 | for i = 1, . . . , 5, and v 3 = v 6 .
Lemma 3. For every integer n ≥ 0, the language B n is accepted by a wr dHm with O(1) states and O(n) tape symbols.

Proof. Let Σ = {0, 1, $}. We first describe an end-marked dTm T accepting the union of all B i 's, for i ≥ 0; then we show how T can be modified in order to recognize B n , for any fixed integer n, by bounding the number of visits to each cell, thus obtaining a wrdHm with the desired properties. Let us define the tape alphabet of T as Γ = {0, 1, $, x, f, b}.

Let w ∈ * be an input string of the form

w = v 1 $v 2 $ • • • $v k , where v 1 , . . . , v k ∈ {0, 1} * , and v k = a 1 • • • a , with a i ∈ {0, 1} for i = 1, . . . , .
The machine T performs iterations. In each iteration it moves the head from the left endmarker to the right endmarker and back, thus visiting each input cell twice.

It also rewrites some of the tape cells during this movement. The aim of the i-th iteration is comparing the i-th rightmost symbol of the last block with the i-th rightmost symbol of any other block. This is implemented as follows. Within the first iteration, T memorizes a in the states, rewrites it by the symbol x, and moves the head leftwards. Whenever it encounters the symbol $ and enters the right end of a block v j , it checks if its last symbol equals a . If so, T overwrites the cell contents with x; otherwise it writes f . During the i-th iteration, T memorizes a +1-i (which is in the rightmost input cell not containing the symbol x) in its finite control, overwrites the cell containing it by x and checks whether the i-th rightmost symbol of each v j , with j < k, matches a +1-i (if so, it overwrites the symbol with x; if not it writes f ). Notice that, at the beginning of the i-th iteration, i > 1, the i-th rightmost symbol of a block is located immediately to the left of a nonempty factor consisting only of the symbols x and f . However, it could happen that for some j < k there is no i-th rightmost symbol in the factor v j -namely the block v j is shorter than v k . In this case the machine halts and rejects.

The input w is accepted by T if and only if, after some iteration, all symbols of v k have been overwritten with x and there is some v j with all symbols also rewritten to x (this ensures v j = v k ).

It can be noticed that, for any fixed integer n, a word belongs to B n if and only if it is accepted by T within the first n iterations. Hence, as each iteration yields exactly two visits to each input cell, by bounding the number of visits to each cell by 2n, we can restrict T to accept words from B n only.

This can be obtained by using a construction similar as those used for proving Lemma 2. We thus obtain a halting wrdHm H accepting B n that has the same number of states as T , hence a number that does not depend on n, and O(n) tape symbols. Lemma 4. Each dfa accepting B n has at least 2 2 n states.

Proof. Let S be the family of all subsets of {0, 1} n . Given a subset S = {w 1 , . . . , w k } ∈ S, where

w 1 < • • • < w k in the lexicographical order, consider the string w(S) = w 1 $w 2 $ • • • $w k .
Let S 1 and S 2 be two different elements of S and let u ∈ {0, 1} n be a string that is in S 1 but not in S 2 (or vice versa). Then, w(S 1 )$u ∈ B n and w(S 2 )$u / ∈ B n (or vice versa), hence $u is a distinguishing extension. Therefore, the set w(S), such that S ∈ S, is a set of pairwise distinguishingable strings. By the Myhill-Nerode Theorem, each dfa accepting B n has at least as many states as the cardinality of such a set.

Hence, it is #S = 2 2 n .
From Theorem 4 and Lemmas 3 and 4, we obtain that the size trade-offs from wrdTms and wrdHms to dfas are double exponential:

Corollary 2. For every wr dTm (resp., wr dHm) T = Q, Σ, Γ, δ, q 0 , F there exists a dfa accepting L(T ) with 2 2 O(#Γ•log(#Q)) states. In the worst case, this double exponential gap is also necessary.

As shown in Theorem 2, by dropping the weight-reducing assumption for machines, the size trade-offs in Corollary 2 become not recursive. However, provided an explicit linear bound on computation lengths, we obtain the following result. Note that Corollary 3 is stated for Turing machines, and since this is the most general model among the ones we studied (cf. Figure 1), the same holds for Hennie machines as well.

Corollary 3. Let T = Q, Σ, Γ, δ, q 0 , F be a dTm. If there exist two constants K and C such that every computation of T has length bounded by Kn + C, where n denotes the input length, then there exist an nfa and a dfa accepting

L(T ) with 2 O(k•#Γ•log(#Q)) and 2 2 O(k•#Γ•log(#Q)) states, respec- tively, where k = 2K • (#Q) K + K.
Proof. Consequence of Theorems 3 and 4. Turing machines (that are necessarily Hennie machines) by allowing the use of additional tape cells that initially do not contain the input and to which we refer as initially-blank cells. In particular, this extension allows infinite computations. For instance, a wrdTm can perform forward moves forever, rewriting each blank cell with some symbol. We now show that, however, due to the weight-reducing property, the number of initially-blank cells that are really useful, i.e., that is visited in halting computations, is bounded by some constant that can be computed from the size of the wrdTm and does not depend on the input string. This allows us to transform any wrdTm into an equivalent halting machine of polynomial size, which therefore operates in linear time. Notice that Theorem 4 already gave a simulation of wrdTms by a halting and linear-time computational model. Proof. For ease of exposition, we index the cell positions by integers, starting with the leftmost cell of the initial segment, whose index is 1, and we identify each cell with its position. Let us fix the computation of T on a given input.

The rough idea is that, due to the fact that T is deterministic, given a tape cell c to the right of the initial segment, the parts of computation that visit the cells to the right of c are completely determined by the sequence of states q 0 , q 1 , . . . , q k-1 in which c is visited. Hence, for each h > 0, the sequence of states in which any cell c+h is visited also only depends on q 0 , q 1 , . . . , q k-1 , and h. As a consequence, if for some h the cell c + h is visited in the same sequence of states q 0 , q 1 , . . . , q k-1 in which c is visited, then even the cell c+2h is visited in the same sequence of states, and so on, thus implying that the computation is infinite.

Going more into details, suppose that the computation visits the tape cell c in configurations C 0 , C 1 , . . . , C k-1 , k ≥ 1. Let q i and γ i be the state and the non-blank content of the right part of the tape that starts from cell c, respectively, in configuration C i , i = 0, . . . , k -1. We observe that, since c is located to the right of the initial segment, γ 0 = ε and, for i = 1, . . . , k -1, due to the fact that T is deterministic, q i and γ i are completely determined by q i-1 and γ i-1 , thus implying that, being γ 0 fixed, q i and γ i depend only on q 0 , q 1 , . . . , q i-1 .8

Let us now consider a cell c + h for h > 0. Let P be the sequence of states in which this cell is visited in the computation under consideration. Due to the fact that T is weight reducing, P is finite. Our aim is to prove that P only depends on q 0 , q 1 , . . . , q k-1 , and h.

Since the cell c + h cannot be visited before the cell c, namely before configuration C 0 , the sequence P can be decomposed as

P = P 1 P 2 • • • P k
where, for i = 1, . . . , k, P i is the sequence of states that are reached when the head is visiting the cell c + h after the configuration C i-1 and, for i < k, before the configuration C i .

Again using the fact that T is deterministic, we observe that P i is completely determined by q i-1 , γ i-1 , and h. Since, in turn, γ i-1 is completely determined by q 0 , q 1 , . . . , q i-1 , we conclude that P i only depends on q 0 , q 1 , . . . , q i-1 , at most g, we conclude that the number of consecutive initially-blank cells visited during the computation is less than (n + 1) g .

As a consequence of the above result, we obtain the following dichotomy of computations of wrdTms.

Proposition 2. Let T be an n-state wr dTm that uses g tape symbols and let ρ be a computation of T . Then, either ρ consists of a number of steps that is linear in the input length and it visits less than (n + 1) g initially-blank cells to the left and less than (n + 1) g initially-blank cells to the right of the initial segment, or ρ is infinite and visits infinitely many tape cells.

Proof. If the amount of tape cells visited by ρ is k, for some finite k, then, as a cell cannot be visited more than g times by the weight-reducing property, ρ is finite and has length bounded by gk. Furthemore, by Lemma 6, ρ visits less than (n + 1) g initially-blank cells to the left (resp., to the right) of the initial segment. Thus, k < 2(n + 1) g -1 + |w|, where w is the input. Hence, the total number of steps of ρ is bounded by gk < g(2(n+1) g -1+|w|) ∈ O(|w|),

i.e., it is linear in the length of the input. Conversely, if ρ visits infinitely many tape cells then it is necessarily infinite.

Proposition 3. By a polynomial size increase, each wr dTm can be transformed into an equivalent linear-time wr dTm.

Proof. From an n-state wrdTm T with a tape alphabet of cardinality g, we can build an equivalent halting wrdTm T that works as follows. After an initial phase during which T marks (n + 1) g initially-blank cells to the left and to the right of the initial segment, it performs a direct simulation of T while ensuring that no further cells than those initially marked and those of the initial segment are used.

The initial phase is implemented using a counter in basis (n + 1), stored on g consecutive tape cells, which is incremented up to (n + 1) g and shifted along the tape. We shall describe a procedure marking the (n + 1) g cells to the left of the initial segment. A similar procedure is repeated at the right of the initial segment.

At each step, the counter contains the number of marked cells minus one.

Hence, at the beginning, it is initialized to value g -1 (in basis n + 1) by writing the corresponding digits onto the g cells immediately to the left of the initial segment, the least significant digit being on the rightmost of these cells. Then the counter is incremented and shifted leftward by updating each digit, from right to left, namely starting from the least significant one.

Let d be the digit scanned by the head. The value d = d + 1 mod (n + 1)

is stored in the state control, along with a boolean variable c, for carry propagation. Then the head is moved one cell to the left, d is written on the tape and its value updated according to the previous contents of the cell just overwritten and the value of c. In the case the previous symbol on such a cell was the blank, then all the g digits have been updated. Hence, the head is moved g positions to the right (on the least significant digit) and the counter is incremented again. This procedure stops when, moving rightward to reach the least significant digit, all the g scanned cells contain the symbol n. We now estimate the number of states used to implement this procedure. First, we notice that O(g) states are sufficient to initialize the g cells to the left of the initial segment and to move the head from the most to the least significant digit of the counter, before each increment. Also checking if all the g cells of the counter contain the symbol n, i.e., if the counter has reached the maximum value, can be done within the same state bound. During the phase that increments and shifts the counter, it is enough to remember the above-mentioned values d and c; it is not necessary to count the positions in the counter because, as explained above, the end of this phase is recognized when a cell containing b is overwritten. Hence, this phase can be implemented using O(n) states. By summing up, this entire procedure can be implemented using O(g + n) states. We also observe that the number of visits to each initially-blank cell is bounded by 2g because every cell is visited at most twice when containing the i-th digit of the current counter value, for i = 1, . . . , g.

Once the space is marked, T simulates T , stopping and rejecting if the simulation reaches a blank cell.

From Lemma 6, we can easily conclude that each halting computation of T is simulated by an equivalent halting computation of T , while each infinite computation of T is replaced in T by a computation that reaches a blank cell and then stops and rejects.

To complete the proof we have to show how to convert T into a weightreducing equivalent machine of size polynomial in the size of T . We remind the reader that T has n states and a tape alphabet of g symbols. Since it is weight-reducing, it can visit each tape cell no more than g times. To mark the cells in the initial phase T uses O(g + n) states and an alphabet of n + 1 symbols; hence the total number of states of T is O(g + n) and the total number of symbols is O(g + n). By the previous analysis, we notice that during the initial phase marking the space, each marked cell is visited 2g times. Furthemore, since after marking cells to the left of the input, the head For the sake of completeness, we mention that, with a finer analysis, it can be shown that the size of the tape alphabet of the final machine can be reduced to O(gn) symbols. To this aim, instead of applying Lemma 2 to the whole machine T , we can directly build T introducing only transitions satisfying the weight-reducing property. For the transitions used in the preliminary phase, marking initially-blank cells to the left and to the right of the input, we use an alphabet of O(gn) symbols, encoding suitable counters for visits, together with the n+1 digits. Furthermore, the original alphabet of T is extended with 2g symbols that are used for the two extra visits that T can make to each tape cell before simulating T .

Using Lemma 6 and Proposition 3, we prove the following property.

Theorem 5. It is decidable whether a wr dTm halts on each input string.

Proof. From any given wrdTm T , we construct a halting wrdTm T that, besides all the strings accepted by T , accepts all the strings on which T does not halt. To this end, we can slightly modify the construction used to prove Proposition 3, in such a way that when the head reaches a blank cell outside the initial segment and the initially marked space, the machine stops and accepts. Hence, the given wrdTm T halts on each input string if and only if the finite automata that are obtained from T and T according to Theorem 4 are equivalent.

By Proposition 2, the number of steps of any halting computation of a wrdTm is linear in the input length. Hence, from Theorem 5 we obtain:

Corollary 4. It is decidable whether a wr dTm runs in linear time.

Conclusion

In this work, we investigated deterministic one-tape Turing machines running in linear time. Although these devices are known to be equivalent to finite automata [START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF], one cannot decide whether a given Turing machine is linear-time even in the case of end-marked devices, as we showed in Theorem 1. Furthermore, there is no recursive function bounding the size blowup of the conversion of dHms into dfas (Theorem 2). To avoid these negative results, we introduced a weight-reducing restriction, which forces one-tape Turing machines to run in linear time as long as they halt. Indeed, we proved that each computation of a wrdTm either is infinite or halts within a linear number of steps in the input length (Proposition 2). The weight-reducing restriction is syntactic and can be checked (Proposition 1). Furthermore, we proved in Theorem 4 that each wrdTm can be converted into an nfa (resp., dfa) whose size is exponential (resp., doubly-exponential) with respect to the size of the converted device. These costs are tight (Corollary 2).

  This language is accepted by an end-marked dTm H n with O(n) states and O(1) tape symbols that simulates a given n-state busy beaver (n-BB) and accepts an input w ∈ a * if and only if the space used by n-BB equals |w|. The dTm H n simulates the moves of n-BB on b with moves on a. When n-BB uses more than |w| space, at some point during the simulation the right endmarker is reached. At that point the simulation is aborted and the machine rejects.

Figure 2 :

 2 Figure 2: An example where (b, p 1 , . . . , p 5) is consistent with (a, q 1 , q 2 , q 3 ). Notice that

5 .

 5 Weight-Reducing Machines: Space and Time Usage, Haltingness Weight-reducing Turing machines generalize weight-reducing end-marked

Lemma 5 .

 5 Let be T a wr dTm. If in a computation of T two initially-blank tape cells, both located to the right of the initial segment, are visited in the same sequence of states, then the computation is infinite. The same result holds if the two cells are both located to the left of the initial segment.

  is moved to the right until the first blank to mark the portion to the right of the input, and then back to first cell of the input to start the simulation of T , T can visit each cell two more times. By summing up, we conclude that in each computation of T each tape cell is visited O(g) times. Hence, applying Lemma 2 we can convert T into a weight-reducing machine T , with O((g + n)g) states and a tape alphabet of O((g + n)g) symbols. This completes the proof.

Actually, the model considered by Hennie was deterministic. Several extensions of this result, including that to the nondeterministic case and greater time lower bounds for

For the sake of completeness, we mention that it is decidable whether a machine makes at most cm + d steps on input of length m, for any fixed c, d > 0[START_REF] Gajser | Verifying time complexity of Turing machines[END_REF].

Note that we allow dfas to have partial transition functions.

This can be achieved, for example, by a sequence of steps that overwrites every tape cell

Notice that if the part of computation between C i-1 and C i only visits cells to the left of c, then γ i-1 and γ i differ only in the first symbol, namely the symbol in the cell c.

 [START_REF] Průša | Weight-reducing Hennie machines and their descriptional complexity[END_REF]Partially supported by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM). 2 Supported by the Czech Science Foundation, grant 19-21198S.

and h. This allows us to conclude that the sequence P = P 1 P 2 • • • P k of states reached at the cell c+h depends only on the sequence of states q 0 , q 1 , . . . , q k-1 reached at the cell c and on h, as we claimed.

Suppose now that P coincides with the sequence q 0 , q 1 , . . . , q k-1 of states visited at the cell c. By iterating the previous argument, the sequence of states that are reached in any cell c + hj, j > 0, is q 0 , q 1 , . . . , q k-1 , thus implying that the computation is infinite. This completes the proof when there are two cells that are visited in the same sequence of states and are both located to the right of the initial segment. With a similar argument, the result can be proved if the two cells are both located to the left of the initial segment. Lemma 6. Let T be an n-state wr dTm that uses g tape symbols. A computation of T is infinite if and only if it visits at least (n + 1) g consecutive initially-blank cells, i.e., tape cells to the left or to the right of the initial segment.

Proof. Since T is weight reducing, the number of visits to each tape cell is bounded by a constant that, in turn, is bounded by g. Thus, each infinite computation must visit infinitely many tape cells, hence at least (n + 1) g consecutive initially-blank cells.

To prove the converse, let us consider a halting computation ρ of T over an input word of length . By Lemma 5, ρ cannot visit two tape cells, lying at the same side of the initial segment, in the same sequence of states. Since there are less than (n + 1) g nonempty distinct sequences of states of length Weight-reducing Turing machines are not restrictions of linear-time machines. Indeed, they allow infinite computations. However, whether a wrdTm halts on all inputs can be decided (Theorem 5). Furthermore, with a polynomial increase in size, each weight reducing machine can be made halting and linear-time (Proposition 3). Still, halting wrdTms are not particular dHms as they allow the use of extra space besides the initial segment contrary to dHms that are end-marked. We do not know at the time of writing whether this extra space usage is useful for representing regular languages concisely.

In other words, we leave open the question of the size cost of turning wrdTms into equivalent wrdHms.

In a related paper [START_REF] Guillon | Converting nondeterministic two-way automata into small deterministic linear-time machines[END_REF], we investigate the computational models considered here by focusing on the Sakoda and Sipser question about the size cost of the determinization of two-way finite automata [START_REF] Sakoda | Nondeterminism and the size of two way finite automata[END_REF]. We indeed propose a new approach to this famous open problem, which consists in converting two-way nondeterministic automata into equivalent deterministic extensions of two-way finite automata, paying a polynomial increase in size only. The considered extensions are variants of linear-time deterministic Turing machines, including wrdHms and dHms.