{'fraction_non_alphanumeric': 0.07213763020037098, 'fraction_numerical': 0.022427077600440288, 'mean_word_length': 3.22851663506292, 'pattern_counts': {'":': 0, '<': 73, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 98, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Groups with undecidable word problem and almost quadratic Dehn function

We construct a finitely presented group with undecidable word problem and with Dehn function bounded by a quadratic function on an infinite set of positive integers.


Formulation of results
The minimal non-decreasing function f (n) : N → N such that every word w vanishing in a group G = A | R and having length ||w|| ≤ n, freely equal to a product of at most f (n) conjugates of relators from R is called the Dehn function of the presentation G = A | R [5]. By van Kampen's Lemma, f (n) is equal to the maximal area of minimal diagrams ∆ with perimeter ≤ n. (See Subsection 5.1 for the definitions.) For finitely presented groups (i.e., both sets A and R are finite) Dehn functions are usually taken up to equivalence to get rid of the dependence on a finite presentation for G (see [9]). To introduce this equivalence ∼, we write f g if there is a positive integer c such that f (n) ≤ cg(cn) + cn f or any n ∈ N. Two non-decreasing functions f and g on N are called equivalent if f g and g f.
A function f : N → N is called almost quadratic if there exists a constant C > 0 and an infinite set of integers B, such that f (b) < Cb 2 for all b ∈ B.
It is well known that a finitely presented group has undecidable word problem if and only if its Dehn function d(n) is not bounded by a recursive function (and if and only if d(n) is not recursive itself; see [4], [3]), whence for every recursive function f (n), d(n) > f (n) for infinitely many values of n. The main result of this paper shows that a non-recursive Dehn function can be almost quadratic at the same time.
Theorem 1.1. There exists a finitely presented group G with undecidable word problem and almost quadratic Dehn function.
Note that "almost quadratic" is the smallest Dehn function one can get, because if the Dehn function of a finitely presented group is o(n 2 ) on some infinite set of integers, then the group is hyperbolic and its Dehn function is linear (this follows from Gromov [5, 6.8.M] or Bowditch [2]).
By Theorem 1.1, for some infinite set B of natural numbers b, the Dehn function of G satisfies the condition f (b) < Cb 2 for some constant C. Notice that the set B is not recursive or even recursively enumerable although its complement is recursively enumerable. Indeed, if f (b) ≥ Cb 2 , then there exists a word w of length ≤ b which is equal to 1 in the group, but which is not the boundary label of any van Kampen diagram with less than Cb 2 cells; all diagrams with this number of cells and boundary length at most b can be enumerated; and all words that are equal to 1 in the group can be enumerated too. Moreover, B cannot contain any infinite recursively enumerable subset (i.e. it is immune in the terminology of [8]). Indeed if B contains an infinite recursively enumerable set enumerated by a Turing machine M , then in order to check if a word w is 1 in G (and solve the word problem in G) we would do the following: wait till M produces a word w ′ longer than w. Then the area of the minimal van Kampen diagram for w cannot exceed C||w ′ || 2 (here and below ||w|| denotes the length of the word w), and it would remain to check all diagrams of that area. Thus although B exists and is infinite, there is no algorithm to find any infinite part of it.
As a corollary of Theorem 1.1 and the results of [16] and [6] we get Corollary 1.2. The group G from Theorem 1.1 has a simply connected and a non-simply connected asymptotic cone.
Indeed the asymptotic cone corresponding to the sequence B discussed in the previous paragraph is simply connected by [16]. On the other hand all asymptotic cones of G cannot be simply connected because that would imply decidability of the word problem in G by [6].
Undecidability of conjugacy problem is easier to achieve than undecidability of the word problem. Theorem 1.3. There exists a finitely presented (multiple) HNN extension M of a free group with finitely generated associated subgroups and with Dehn function f (n) such that: 1. The conjugacy problem is undecidable in M ; 2. There is an infinite set N 1 ⊆ N, such that for some constant C we have f (n) < Cn 2 for every n ∈ N 1 ; 3. For every n, f (n) ≤ Cn 3 .
Remark 1.4. Probably the first example of an almost quadratic but not quadratic Dehn function of a finitely presented group was constructed in [12]. However that function is O(n 2 log n/ log log n) which is not much bigger than a quadratic function. A slight modification of the proofs of the present paper provides us with a recursive almost quadratic Dehn function d(n) rapidly increasing on some infinite subset N 2 of N. (For example, almost quadratic d(n) is at least exponential on N 2 and at most exponential on the entire N; see Theorem 13.5 and Remark 13.6 for details.) The difference is that the proof of Theorem 1.1 uses Sapir's Theorem 14.1, but the recursive examples are independent of it.
Remark 1.5. Using [19] and Theorem 14.1 one can easily obtain a weaker version of Theorem 1.1 replacing "almost quadratic" by "almost polynomial". Recall that a function f : N → N is superadditive if f (m+n) ≥ f (m)+f (n) for any m, n ∈ N. The superadditive closuref (n) of a function f (n) is given by the formulaf (n) = max(f (n 1 ) + · · · + f (n k )) over all non-negative partitions n = n 1 + · · · + n k . If a Turing machine M accepts a language L with at least linear time function T (n), and T (n) 4 is equivalent to a superadditive function, then by Theorem 1.3 [19], there is a finitely presented group G(M ) with Dehn function d(n) equivalent to T (n) 4 . But in fact, it is proved in [19] that omitting the assumption that T (n) 4 is superadditive, we have inequalities T (n) 4 d(n) T (n) 4 .
Thus it suffices to construct a Turing machine M with non-recursive but "almost linear" time function T (n). The existence of such a machine follows from Theorem 14.1.
(Moreover, one can derive from Theorem 14.1 that T (n) 4 is "almost n 4 ".) Reducing to "almost quadratic" (as in Theorem 1.1) requires a new approach. The S-machine we are going to use will be different from [19], and the analysis of diagrams will be much more delicate. The main reason for the difficulties arising here is that the "almost quadratic" property is unimprovable. For example, the cubic upper bound of the Dehn function of the group M is obvious in [19] (see also Step 1 in the proof of Lemma 13.1 below), but the main contents of our paper focus on M, starting with the properties of the machine defining M and ending with new quadratic invariants of the diagrams called mixture(s) on their boundaries. In the next subsection of the introduction, we discuss the outline of the proof of Theorem 1.1, and some ideas needed in its proof.

A short description of the proof of Theorem 1.1
Relations of a finitely presented group with undecidable word problem simulate the commands of a Turing machine M 0 with undecidable halting problem, and as in the works of P.Novikov, W.Boone and many other authors (see [17], [18]), one has to properly code the work of a Turing machine in terms of group relations. To obtain an almost quadratic Dehn function of a group G, we must start with a machine having almost linear time function (but which is not bounded from above by any recursive function). Thus we can just demand that the lengths of words accepted by M 0 form a very sparse subset of positive integers B ⊂ N. As a measure of how sparse B is, M.V. Sapir gives the following exact definition.
Let X be a recursively enumerable (r.e.) language in the binary alphabet recognized by a Turing machine M . If w ∈ X then the time of w (denoted time(w) or time M (w)) is, by definition, the minimal time of an accepting computation of M with input w. For an increasing function h : N → N, a number m ∈ N is called h-good for M if for every word w ∈ X of length < m, we have h(time(w)) < m.
For our estimates, it suffices to start with a Turing machine M 0 recognizing a r.e. non-recursive set X such that the set of all f -good numbers for M 0 is infinite, where f is arbitrary double exponential function. Such a machine is constructed in the Appendix written by M.V.Sapir (see Theorem 14.1).
Group relations always interpret the symmetrization of a machine. Thus as a preliminary step, one has to add the inverse commands, in spite of the fact that the machine M 0 is replaced by a non-deterministic machine M 1 . (Of course, one should be concerned that the symmetrization preserves some basic characteristics of the machine.) However the interpretation problem for groups remains much harder than for semigroups even after modifying the machine because the group theoretic simulation can execute unforeseen computations with non-positive words. Boone and Novikov secured the positiveness of admissible configurations with the help of an additional 'quadratic letter' (see [17], Ch.12). However this old trick implies that the constructed group G contains Baumslag -Solitar groups B 1,2 and has at least exponential Dehn function. Since we want to obtain almost quadratic Dehn function, we use a new approach suggested in [19]. Invented by Sapir, S-machines can work with non-positive words on the tapes. Here we use an a composition M 2 of the symmetric machine M 1 with an 'adding machine' Z(A) introduced in [15]. This S-machine is equivalent to M 1 .
Here we have to guarantee at least two important properties of the machine M 2 (since the violation of either of them makes the Dehn function of the group M 2 non-almost quadratic): a reduced computation of M 2 does not repeat the same configuration twice, and every accepting computation of M 2 is uniquely determined by the initial configuration (though M 2 is highly non-deterministic).
Every S-machine is, on the one hand, a rewriting system and, on the other hand, it can be treated as a multiple HNN-extension of a free group (see [15] or [18]). But when one takes an S-machine as an HNN-extension, then the number of working heads can be arbitrarily large and their order on the common tape can be non-standard. Therefore, as in [19] or [15], we have to extend the set of admissible words for the machine treated as a rewriting system. This makes the control of arbitrary computation difficult. (There was no need for such accurate control in [19] or [15].) Hence we are forced to introduce auxiliary control heads which are called upon to examine the order of heads after and/or before the application of every rule of the machine M 2 . The obtained machine M 3 is better than M 2 because it is able to accomplish only 'simple' computations with non-standard disposition of the heads.
When we introduce a new machine, then clearly, we should check that it inherits the important properties of the machines studied earlier. In particular, M 3 inherits the language accepted by M 1 . The next modification is the machine M 4 which has two additional tapes with histories of what M 3 computes. For any computation with the standard order of heads of M 4 (the notion of standard base of M 4 is given in subsection 4.3), we prove that either the time T of this computation is 'close' to the time T i of some computation accepting a word from the sparse set provided by Theorem 14.1,or the space on the 'historical' tapes at the beginning or at the end of the computation is bounded from below by a linear function of T . In the latter case we have a quadratic upper estimate for the area of the trapezium corresponding to the computation. Here the definition of trapezium as a special van Kampen diagram is borrowed from [15], and Lemma 5.10 translates the machine language to the diagram language.
Finally, the machine M is a union of many copies and mirror copies of M 4 working in a parallel way. The corresponding HNN-extension M is the group from Theorem 1.3. The accept word of the machine M is called the hub. There is no algorithm deciding if a given word in the generators of M is conjugate to the hub. The usual adding of the hub relation to the list of defining relations of M (as in [17], and many papers) provides us with the group G for Theorem 1.1. As in [19] or [11] the hub relation has many copies of the accept words of M 4 . This makes the hub graph (with vertices in hub cells; see Subsection 5.3) associated with a van Kampen diagram, hyperbolic, and this is used in Lemmas 5.18 and 5.19. The mirror symmetry of the hub is used for the surgery removing a hub (see Subsection 12.2).
Unsolvability of the halting problem for the S-machine M immediately implies that the Dehn function d(n) of the group G is not bounded from above by any recursive function. Other precautions used in the construction of the machines M 0 , . . . , M 4 , M eliminate a number of visual obstacles standing in the way of the almost quadratic property for the Dehn functions of M and G. (For instance, if one uses only one historic tape for M 4 or the arrangement of the historic heads is different, then the almost quadratic estimate is not achieved by our model.) But how can one prove this property ?
The areas of diagrams whose perimeters are close to some numbers T i mentioned above can be non-recursively high in comparison with their perimeters. Therefore one has to consider a diagram ∆ whose perimeter n is far from the infinite increasing sequence {T 1 , T 2 , . . . }, for example, exp T i−1 < n < T i for some i. Unlike a trapezium, an arbitrary diagram has irregular structure. Therefore we want to find some more regular pieces to cut them off and then use an induction on the perimeter n.
Indeed assume that there is a simple path y in ∆ cutting up ∆ into two subdiagrams ∆ 1 and ∆ 2 with boundary paths yz and y −1 z ′ , resp., where zz ′ is the boundary of ∆. Assume that |z| > |y| (where |x| is the length of a path x) and moreover, Area(∆ 1 ) ≤ C|y|(|z| − |y|), where the positive constant C does not depend on the diagrams. Then it is easy to see that the quadratic estimate Area(∆ 2 ) ≤ C|yz| 2 for the subdiagram ∆ 2 with perimeter < n together with the estimate for Area(∆ 1 ) give Area(∆) ≤ Area(∆ 1 ) + Area(∆ 2 ) ≤ C|zz ′ | 2 = Cn 2 as required. Thus we are looking for pieces whose area can be estimated as for ∆ 1 .
First of all, among such 'good' pieces, we have so called rim θ-bands with a restriction on the length (but here we have to change the usual combinatorial metric by the metric, where the generators from the tape alphabet of the machine M are much shorter than other generators of the groups M and G). The 'good' pieces of second type (again, under some restrictions) are combs defined in Section 7 (and introduced earlier in [15]).
The upper bound of the form C|y|(|z| − |y|) works for many types of combs but unfortunately, it is false for other combs whose areas must also be estimated. We have found another quadratic invariant of the boundaries of the diagrams, called mixture. In Section 6, we associate a two-colored necklace with the boundary p of ∆. The black and white beads of this necklace correspond to different types of edges in p. To obtain the mixture µ(∆) one calculates the number of pairs of white beads separated in p by black ones. (Another quadratic invariant, called dispersion, was introduced and applied earlier in [15], but the dispersion depends on the whole diagram and works for hub free diagrams while the mixture depends on the boundary label only and works for arbitrary diagram over G.) The important observation is that for many types of subcombs ∆ 1 , we have inequalities Area(∆ 1 ) ≤ C|y|(|z| − |y|) + µ(∆ 1 ), and µ(∆ 2 ) ≤ µ(∆) − µ(∆ 1 ). This was a breakthrough which inspired the confidence that the whole project would be completed. However the original mixture cannot help in case of some special combs. Therefore we have to consider boundary necklaces of 3 different types. The different mixtures help to estimate the areas of different combs. But one of these mixtures helps in some cases and can be negative in some other cases, which causes a problem for our induction. Therefore we use a weighted linear combination of 3 mixtures in the Lemma 11.8 summarizing our estimates of comb areas. Hence we have to estimate the behavior of these mixtures in different situations, which makes a number of comb lemmas complicated, and the comb part of the paper is the hardest one.
Then we consider a diagram ∆ with hubs. Due to hyperbolicity of the hub structure mentioned above, there is a hub Π such that almost all 'spokes' starting on Π end on the boundary ∂∆, and they bound (together with ∂∆ and ∂Π) a subdiagram Ψ without hubs. Now we are able to remove redundant combs and rim bands from Ψ. The remaining crescentΨ together with Π can be cut off by a relatively short cutting path. (Thus, one can also induct on the number of hubs in ∆.) As in [19], our surgery uses the mirror symmetry of the hub relation, but our inequalities are more delicate here than those used for the 'snowball decomposition' in [19] since we aim for almost quadratic bounds. Again we estimate the area of the removed part in terms of the reduction of the perimeter, of the mixtures, and more. To complete the proof, we take into account that the auxiliary parameters are quadratically bounded with respect to the perimeter of a diagram.
The author is aware that such a long proof can be arduous to the reader. Making our apology we collect all the definitions and terms at the end of the paper (see Subject Index) and insert many pictures and brief comments throughout the text. Besides, Lemma 5.17 reformulates all machine properties we need in terms of van Kampen diagrams so that the machine constructions can be forgotten after one has read that lemma.
Acknowledgment. The author is grateful to M.V. Sapir who was involved in the joint work when the project started in March 2005. Although he has retired from the absorbing and exhausting struggle against the details, his contribution to the proof is certainly bigger than what is written by him in Appendix.

Definitions and notations related to Turing machines
In this section, we collect all information about Turing machines that we need in the proof of our main results.
As usual we consider words as sequences of symbols from some alphabet X. We shall use the following standard notation for Turing machines. A (multi-tape) Turing machine has k tapes and k heads observing the tapes. One can view it as a structure M = I, Y, Q, Ω, Θ , where I is the input alphabet, Y is the tape alphabet (I ⊆ Y ), Q = ⊔Q i , i = 1, ..., k is the set of states of the heads of the machine (and ⊔ denotes disjoint union), Ω = {α 1 , ω 1 , . . . , α k , ω k } is the set of left and right markers of the tapes, and Θ is a set of commands. The leftmost (the rightmost) square on the i-th tape is always marked by α i (by ω i ). The head is placed between two consecutive squares on the tape. A configuration of the i-th tape of a Turing machine is a word α i uqvω i , where q ∈ Q i is the current state of the head of that tape, u is the word in Y to the left of the head and v is the word in Y to the right of the head, and so the word written on the entire tape is uv; so we do not include α i , ω i and the state letter when we talk about the word written on the tape.
At every moment the head of each tape observes two letters on that tape: the last letter of u (or α i ) and the first letter of v (or ω i ).
A configuration U of a Turing machine is the word where U i is the configuration of tape i. We shall omit the indices i of α i and ω i for the sake of brevity.
Assuming that the Turing machine is recognizing, we can define input configurations and accepted (stop) configurations. An input configuration is a configuration where the word written on the first tape is in I, all other tapes are empty, the head on the first tape observes the right marker ω, and the states of all tapes form a special start k-vector s 1 . An accept (or stop) configuration is any configuration where the state vector for a special k-vector s 0 , the accept vector of the machine. We shall always assume (as can be easily achieved) that in the accept configuration of a Turing machine every tape is empty.
A transition (command) of a Turing machine is given by the states of the heads and some of the 2k letters observed by the heads. As a result of a transition we replace some of these 2k letters by other letters, insert new squares in some of the tapes and may move the heads one square to the left (right) with respect to the corresponding tapes.
For example in a one-tape machine, every transition is of the following form: where u, v, u ′ , v ′ are letters (could be end markers) or empty words. The only constraint is that the result of applying the substitution uqv → u ′ q ′ v ′ to a configuration word must be a configuration word again, in particular the end markers cannot be deleted or inserted. This command means that if the state of the head is q, u is written to the left of q and v is written to the right of q, then the machine must replace u by u ′ , q by q ′ and v by v ′ . For a general k-tape machine, a command is a vector where U i → V i is a command of a 1-tape machine, the elementary commands (also called parts of the command) U i → V i are listed in the order of tape numbers. In order to execute this command, the machine checks if U i is a subword of the configuration of tape i (i = 1, ..., k), and then replaces U i by V i . Notice that for every command [U 1 → V 1 , ..., U k → V k ], the vector [V 1 → U 1 , ..., V k → U k ] is also a command of a Turing machine. These two commands are called mutually inverse. A Turing machine is called symmetric if for every command of that machine, the inverse is also a command of the machine. If a Turing machine is symmetric, we shall always consider a division of the set of its commands Θ into two disjoint subsets, positive and negative commands: Θ = Θ + ⊔ Θ − , so that the inverses of commands in Θ + are in Θ − and vice versa.
We will assume that only input configurations of a Turing machine involve the state letters from s 1 and only one (positive) command θ start is applicable to the input configurations. Similarly, we assume that there is a unique accept configuration s 0 and a unique (positive) accepting command θ accept .
A computation is a sequence of configurations C 0 → · · · → C n such that for every 0 = 1, ..., n − 1 the machine passes from C i to C i+1 by applying one of the commands from Θ. A configuration C is said to be accepted by a machine M if there exists at least one computation which starts with C and ends with the accept configuration.
A word u over I is said to be accepted by the machine if the corresponding input configuration is accepted. The set of all accepted words over the input alphabet I is called the language accepted (recognized) by the machine.
Let C = C 0 → · · · → C n be a computation of a machine M such that for every j = 0, ..., n − 1 the configuration C j+1 is obtained from C j by a command θ j+1 from Θ. Then we call the word θ 1 . . . θ n the history of this computation. The number n will be called the time (or length) of the computation.
Remark 2.1. Note that we can (and will) assume that in every command It is convenient to consider empty computations consisting of one word W . The history of an empty computation is the empty word, the start and end words of this computation are equal to W . We do not only consider deterministic Turing machines, for example, we allow several transitions with the same left side. For example, most symmetric Turing machines are not deterministic.

A conversion of a deterministic Turing machine into a symmetric
Turing machine At first, let us add some useful properties to a machine.
Lemma 2.2. Let M 0 be a deterministic Turing machine recognizing a set of words X. Then there exists a deterministic Turing machine M 1 which recognizes X and such that (a) If W ≡ W ′ (i.e. these two words are letter-for-letter equal) for a computation W → · · · → W ′ , then this computation is empty. (b) The property from Remark 2.1 ("at most one tape letter") holds for every command of M 1 .
(c) The state letters from the start vector − → s 1 (from the accept vector − → s 0 ) occur in the left-hand side of a unique command U → V of M 1 and do not occur in the right-hand side of any command (resp., occur in the right-hand side of a unique command U ′ → V ′ and do not occur in the left-hand side of any command) (d) The letters used on different tapes are from disjoint alphabets. The letters to the left and to the right of the head of any tape are from disjoint alphabets.
Proof. Let W be a configuration of M 0 . The general form of a configuration of M 1 will be W ατ l q k+1 ω, that is the machine M 1 has one more tapes than M 0 . The last tape contains a (non-negative) power of a special tape letter τ . The set of state letters is then increased by one component {q k+1 }. At the beginning the last tape is empty. The machine will execute M 0 on its tapes, adding new τ on the last tape after every step of computation. After M 0 accepts, M 1 erases the last tape and stops. The last tape guarantees Property (a)). In order to get Property (b) of M 1 , we apply the trick from Remark 2.1 since it does not violate Property (a). Property (c) of M 1 for the start command follows from the same property of M 0 , and we can define the accept command of M 1 so that Property (c) also holds for it.
In order to obtain Property (d), we use different copies of the tape alphabet for different tapes, and moreover, we use different copies from the left and from the right of each head.
If M 1 is a deterministic Turing machine, satisfying the properties of Lemma 2.2, with the set of commands Θ such that Θ ∩ Θ −1 = ∅, then let Sym(M 1 ) be the Turing machine with the set of commands Θ⊔Θ −1 and the same sets of state and tape letters. The division of the commands of Sym(M 1 ) into positive and negative is natural: the commands of M 1 are positive, their inverses are negative. The computation of Sym(M 1 ) is called reduced if its history is a reduced word. Clearly, every computation can be made reduced (without changing the start or end configurations of the computation) by removing consecutive mutually inverse commands.  (e) For every W ∈ X there exists only one accepting computation of Sym(M 1 ). It is equal to the computation accepting W by M 1 , and if M 1 is given by Lemma 2.2, then the length of this computation is big-O of the length of the accepting computation of M 0 with input W .
Proof. Property (a) is obvious. Property (b) follows immediately from the fact that in a reduced computation, a command from Θ −1 cannot be followed by a command from Θ (since M 1 is deterministic). Properties (c), (d), (e) follow from (b).

S-machines as rewriting systems
There are several interpretations of S-machines in groups, the most complicated so far is in [14]. Another interpretation is given in [15], and in fact it is probably the easiest way to view an S-machine as a group that is a multiple HNN extension of a free group.
Here we use a definition which is close to the original one [19] and define S-machines as rewriting systems, similar to Turing machines. S-machines work with words in group alphabets and they are almost "blind", i.e., the heads do not observe the tape letters. But the heads can "see" each other if there are no tape letters between them. We will use the following precise definition of an S-machine S.
The elements from Q are called state letters, the elements from Y are tape letters. The sets Q i (resp. Y i ) are called parts of Q (resp. Y ).
The language of admissible words consists of reduced words of the form has the form quq −1 for some q ∈ Q j and u ∈ F (Y j+1 ), or (3) is of the form q −1 uq for q ∈ Q j and u ∈ F (Y j ).
We shall follow the tradition of calling state letters q-letters and tape letters a-letters, even though we shall use other letters as state or tape letters. Usually parts of the set Q of state letters are denoted by capital letters. For example, a set K would consist of letters k with various indices. Then we shall say that letters in K are k-letters or K-letters.
If a group word W over Q∪Y has the form q 1 u 1 q 2 u 2 ...q s , and q i ∈ Q ±1 j(i) , i = 1, ..., s, u i are group words in Y , then we shall say that the base of W is base( Here Q i are just letters, denoting the parts of the set of state letters. Note that the base is not necessarily a reduced word, and the last equality is in the free semigroup. The subword of W between the Q ±1 j(i) -letter and the Q ±1 j(i+1) -letter will be called a Q ±1 For aesthetic reasons, we shall substitute the capital names of parts of Q by the corresponding small letters. For example, if t ∈ T, k ∈ K, ..., we shall say that the base is tk..., that is the state letters in W start with a t-letter, followed by a k-letter, and so on. Usually instead of specifying the names of the parts of Q and their order as in Q = Q 0 ⊔ Q 2 ⊔ ... ⊔ Q N , we say that the standard base of the S-machine is Q 0 ...Q N or q 0 ...q N .
The S-machine also has a set of rules Θ. Every θ ∈ Θ is assigned two sequences of reduced words: The words U i , V i satisfy the following restriction: (**) For every i = 0, ..., N , the words U i and V i have the form The pair of words U i , V i is called a part of the rule, and is denoted U i → V i . We will denote the rule θ by [U 1 → V 1 , ..., U N → V N ]. This notation contains all the necessary information about the rule except for the sets Y i (θ). In most cases it will be clear what these sets are. In the S-machines used in this paper, the sets Y i (θ) will be equal to either Y i or ∅. By default Y i (θ) = Y i . If Y i+1 (θ) = ∅, then the corresponding component U i → V i will be denoted U i ℓ → V i and we shall say that the rule locks the Q i Q i+1 -sectors. In that case we always assume that U i , V i do not have tape letters to the right of the state letters, i.e., it has the form v Similarly, these words have no tape letters to the left of the state letters if the Q i−1 Q i -sector is locked by the rule. Every . We always divide the set of rules Θ of an S-machine into two disjoint parts, Θ + and Θ − such that for every θ ∈ Θ + , θ −1 ∈ Θ − and for every θ ∈ Θ − , θ −1 ∈ Θ + (in particular Θ −1 = Θ, that is any S-machine is symmetric). The rules from Θ + (resp. Θ − ) are called positive (resp. negative).
To apply an S-rule θ to an admissible word (3.1) W means to check if all tape letters of W belong to the alphabet Y (θ) and then, if W satisfies this condition, to replace simultaneously subwords U ±1 i by subwords V ±1 i (i = 1, . . . , k + 1) and to trim a few first and last a-letters (to obtain an admissible word starting and ending with q-letters). This replacement is allowed to perform in the form followed by the reducing of the resulted word. The following convention is important in the definition of S-machine: After every application of a rewriting rule, the word is automatically reduced. The reducing is not considered a separate step of an S-machine.
If a rule θ is applicable to an admissible word W (i.e., W belongs to the domain of θ) then the word W is called θ-admissible. The definitions of computation, its history, input admissible words, are similar to those for Turing machines. Similarly, we sometimes choose a distinguished stop word W 0 from the free group F (Q). It will always have the standard base (and no a-letters). We say that a word W ∈ F (Q ∪ Y ) is accepted if there exists a computation connecting this word and W 0 .

Modifying the rules of S-machines
We shall need the following properties of our S-machines. All S-machines that appears in this paper, except for M 2 , satisfy Property 3.1 (1) below, andM 2 satisfies Property 3.1 (2).
i || ≤ 1 (see the notation in (**) above). (2) For every rule, we have i (||v i || + ||v ′ i || + ||u i || + ||u ′ i ||) ≤ 1. Suppose that Property 3.1 (1) is not satisfied. For example, suppose that a positive rule θ of an S-machine S has the i-th part of the form i are words in the appropriate parts of the alphabet of a-letters, v i−1 is not empty, a is a a-letter, q i , q ′ i are q-letters (a very similar procedure can be done in all other cases). Then we create a new S-machineS with the same standard base and the same a-letters as S. In order to makeS, we add one new (auxiliary) q-letterq i to each part of the set of q-letters, and replace the rule θ by two rules θ ′ and θ ′′ . The rule θ ′ is obtained from θ by replacing the part , and all other parts U j → V j by U j →q j (hereq j is the auxiliary q-letter in the corresponding part of the set of q-letters). The rule θ ′′ is obtained from θ by replacing the part The key property of the new S-machine is in the following obvious lemma.
There is a one-to-one correspondence between computations w 0 → ... → w n ofS (with any base) such that w 0 , w n do not have auxiliary q-letters and computations of S connecting the same words. For every history H of such computation of S, the corresponding history of computation ofS is obtained from H by replacing every occurrence of the rule θ by the 2-letter word θ ′ θ ′′ .
Note that the sum of lengths of words in all parts of θ ′ (resp. θ ′′ ) inS is smaller than the similar sum for θ. Clearly, applying this transformation to an S-machine S several times, we obtain a new S-machine satisfying Property 3.1 (1). Similarly, one can obtain Property 3.1 (2). Thus Lemma 3.2 implies the following Lemma 3.3. For every S-machine S there exists an S-machineS with the same standard base, the same set of a-letters, and some new, auxiliary, q-letters such thatS satisfies Property 3.1 (2), and there exists a one-to-one correspondence between computations w 0 → ... → w n ofS (with any base) such that w 0 , w n do not have auxiliary q-letters and computations of S connecting the same words. For every history H of S, the corresponding history of computation ofS is obtained from H by replacing every occurrence of the rule θ by the word φ(θ) such that all rules in φ(θ) are different, and φ(θ), φ(θ ′ ) do not have common rules provided θ = θ ′ .

Some general properties of S-machines
Note that the base of an admissible word is not always a reduced word. But we have the following immediate corollary of the definition of admissible word.
In this paper we are often using copies of words. If W is a word and A is an alphabet, then to obtain a copy of W in the alphabet A we substitute letters from A for letters in W so that different letters from A substitute for different letters. Note that if U ′ and V ′ are copies of U and V respectively corresponding to the same substitution, and U ′ ≡ V ′ , then U ≡ V.
The following lemma is obvious.
Lemma 3.5. Suppose that the base of an admissible word W is Q i Q i+1 . Suppose that each rule of a reduced computation starting with W ≡ q i uq i+1 and ending with W ′ ≡ q ′ i u ′ q ′ i+1 multiplies the Q i Q i+1 -sector by a letter on the left (resp. right). And suppose that different rules multiply that sector by different letters. Then the history of computation is a copy of the reduced form of the word u ′ u −1 read from right to left (resp. of the word u −1 u ′ read from left to right). In particular, if u ≡ u ′ , then the computation is empty. Lemma 3.6. Let W 0 → · · · → W t be a sequence of transformations of reduced words, where W i is a conjugate of W i−1 (i = 1, ..., t) by a letter, and H -a product of these letters, i.e. W t = H −1 W 0 H. Then H is equal to a reduced product H 1 Proof. One may assume that the consecutive transformations W i−1 → W i → W i+1 are not mutual inverse. If ||W i−1 || < ||W i ||, then ||W i ||−||W i−1 || = 2, and moreover, ||W i ′ ||− ||W i ′ −1 || = 2, for every i ′ ≥ i. Similar observation is true for inverse transformations W t → · · · → W 0 . It follows that there exist subscripts i, j such that 0 ≤ i ≤ j ≤ t, and each of the transformations W 0 → · · · → W i decreases the length by 2, while ||W i || = ||W i+1 || = · · · = ||W j ||, and each of the transformations W j → · · · → W t increases the length by 2. Thus, we have We also have j − i one-letter cyclic shifts W i → · · · → W j , and this procedure is periodic with period ||W i ||, whence the middle part of the conjugating word H must be of the formH k 2H , with k ≥ 0 and ||H|| < ||H 2 || = ||W i || ≤ min(||W 0 ||, ||W t ||), whereHis a prefix of the wordH 2 . ReplacingH 2 by a cyclic permutation H 2 one rewrites the same middle part as

Lemma 3.6 immediately implies
Lemma 3.7. Suppose that the base of an admissible word W is is a letter, and for different θ-s the b θ -s (resp., a θ -s) are different. Then the history of the computation has the form H 1

Turing machines as S-machines
Every symmetric Turing machine M satisfying Condition (d) of Lemma 2.2 can be viewed as an S-machine SM [19,Page 372], such that the positive (negative) commands of M are the positive (negative) rules of SM . More precisely, we consider the α and ω symbols as state letters (hence the set of state letters has 2 more parts for each tape of the Turing machine). A part of a command of the form where u and v are tape letters or empty words, is replaced by and a part of the form The language recognized by SM is in general much bigger than the language recognized by M since M works with a positive tape alphabet only. Nevertheless the following property statement holds: Lemma 3.8. (compare with [19,Proposition 4.1]) Let M be a symmetric Turing machine satisfying the conditions of Lemma 2.3 (i.e. the symmetrization of some deterministic Turing machine satisfying conditions of Lemma 2.2). Let W 1 → W 2 → · · · → W k be a computation of the S-machine SM with the standard base consisting of positive words. Then it is a computation of the Turing machine M (with the same history).
Proof. Indeed, every positive admissible word W of SM with the standard base is a configuration of the Turing machine M . If a rule θ of SM satisfying Property (c) of Lemma 2.2 or its inverse applies to this W and the word W ·θ is positive, then, obviously, the command θ of M applies to W and the result of the application is the same (here we essentially use the fact that the rule θ or its inverse inserts (deletes) at most one letter). This immediately implies the statement of the lemma.

The S-machine
We turn to the proof of Theorem 1.1. From now M 0 is the deterministic Turing machine recognizing language X from Theorem 14.1, the machine M 1 is constructed as in Lemma 2.2 and recognizes the language X 1 , where X 1 = X. We keep the same notation M 1 for the symmetrization of M 1 given by Lemma 2.3. Note that by claim (e) of that lemma, the machine M 1 has infinitely many h α -good numbers for every α > 0, where the functions h α are defined in Theorem 14.1. First, we need to construct a new S-machine which inherits important properties of the Turing machine M 1 .
As in Section 3.3, we can view M 1 as an S-machine. We shall denote that S-machine by the same letter M 1 .
Let Q 0 ...Q N be the standard base of M 1 , let the components of the alphabet of aletters be Y 1 , ..., Y N (letters from Y i are in the Q i−1 Q i -sectors of admissible words with the standard base).

The machine M 1 • Z
Let A be a finite set of letters. Let the sets A 1 , A 2 be copies of A. It will be convenient to denote A by A 0 . For every letter a 0 ∈ A 0 let a 1 , a 2 denote its copies in A 1 , A 2 .
As in [15], consider the following auxiliary "adding" S-machine Z(A). Its set of state letters is P 1 ∪ P 2 ∪ P 3 , where The machine Z(A) has the following positive rules (there a is an arbitrary letter from A). The comments explain the meanings of these rules.
Comment. The state letter p(1) moves left searching for a letter from A 0 and replacing letters from A 1 by their copies in A 2 .
Comment. The state letter p(2) moves toward R.
Comment. p (2) and R meet, the cycle starts again.
Comment. If p(1) never finds a letter from A 0 , the cycle ends, p(1) turns into p (3); p and L must stay next to each other in order for this rule to be executable.
Comment. The letter p(3) returns to R.
The following Lemmas from [15] contain the main properties of Z(A) used later. If u ≡ a 1 ...a m is a word, a i are letters, then we set r 3 (u) ≡ r 3 (a 1 )r 3 (a 2 )...r 3 (a m ), r 2 (u) ≡ r 2 (a 1 )r 2 (a 2 )...r 2 (a m ), r 1 (u) ≡ r 1 (a m )...r 1 (a 2 )r 1 (a 1 ). Lemma 4.1. ([15,Lemma 3.18] Then the projections of uv and u ′ v ′ onto A are freely equal. 2. If W ≡ LupR, where p = p(1) (resp. p = p(3)), u is positive, then there exists a computation starting with W and ending with Lup(3)R (resp. Lup(1)R). Moreover if u is any word in a-letters, and for some history of computation H, W ·H contains p(3)R (resp. p(1)R) and all a-letters in W, W · H are from A ±1 0 , then the length of H is between 2 ||u|| and 6 · 2 ||u|| , u and all words in the computation W → ... → W · H are positive, all words in that computation have the same length, and H is uniquely determined by u. That computation (resp. its inverse) has the history of the following form We define the S-machine M 2 as the composition M 1 • Z (this operation is defined in [15], see also below).
Essentially we insert a p-letter between any two consecutive q-letters in admissible words of M 1 with standard base, and treat any subword q i ...p i+1 ...q i+1 as an admissible word for Z(A) (that is q i plays the role of L and q i+1 plays the role of R). The only differences with the construction in [15] are that, for every state letter q, we keep the sets of a-letters that can appear to the left and to the right of q disjoint, and after application of a main rule, not only the state letters of copies of Z(A) remember the main rule but also the state letters coming from M 1 remember that rule. These changes do not affect the proofs of statements in [15] that we are going to use.
Let us describe M 2 in details. First, for every i = 1, ..., N , we make three copies of the alphabet Let Θ be the set of positive commands of M 1 (viewed as rules of an S-machine). The set of state letters of the new machine is Thus every "old" state letter of M 1 gets "multiple" copies indexed by positive rules of M 1 , and the state letters of various copies of Z have upper indices corresponding to the positive rules of M 1 and the number of sector where the machine is inserted. The Q ′ 0 P 1 -sector of an admissible word with the standard base will be called the input sector of that word.
The set of tape letters is the components of this union will be denoted byȲ 1 , ...,Ȳ 2N We shall call the new (second) indices of tape letters the M 2 -indices of these letters. The set of positive rulesΘ of M 1 • Z is a union of the set of suitably modified positive rules of M 1 and |Θ|N copies Z (θ,i) (θ ∈ Θ, i = 1, ..., N ) of positive rules of the machine Z(Y i ) (also suitably modified).
More precisely, every rule θ ∈ Θ of the form withȲ 2i−1 (θ) = Y i,0 (θ) andȲ 2i (θ) = ∅. If θ = θ start is the unique start rule of M 1 then all p (i) -s in the above definition ofθ must be replaced by the special start letters p (1,i) -s. Thus each modified rule from Θ turns on N copies of the machine Z(A) (for different A's). The ruleθ will be called the rule of M 2 corresponding to the rule θ of M 1 . (θ,i) , and R with (q ′ ) (θ,i+1) , and for s = i,Ȳ 2s−1 (τ i (θ)) = Y s,0 (θ). Thus while the machine Z (θ,i) works all other machines Z (θ,j) , j = i must stay idle (their state letters do not change and do not move away from the corresponding q-letters). After the machine Z (θ,i) finishes (i.e. the state letter p (θ,i) 3 appears next to (q ′ ) (θ,i) ), the next machine Z (θ,i+1) starts working.
In addition, we need the following transition rule ζ(θ) that removes θ from all state letters, and turns all p If θ is the unique accept rule of M 1 then all p (j) -s in the above definition of ζ(θ) must be replaced by the special (accept) letters p (0,i) -s.
where each H s is the computation of the machine Z (θ,s) whose history is a copy of D(u s ) (described in Lemma 4.2,part 2), and all words in the computation W ·θ → ... → W · H are positive. We shall denote H by Π 1,2 (θ, W ). That computation is completely determined by its first (last) word and θ.
Proof. By assumption, H ′ consists of the rules of various S-machines Z (θ,i) since only rulesθ −1 and ζ(θ) can remove the θ-index of state letters. Since the word W ′ = W ·(θH ′ ) is in the domain of ζ(θ), all p-letters in W ′ have the form p (θ,i) 3 . Since rules from Z (θ,i) can apply to an admissible word with the standard base only if p j -letters (j = i) stay next to the left of the corresponding (copies of) state letters of M 1 , and have the form p (θ,j) 3 , if j < i, and the form p where each H s is a non-empty history of the computation of some Z (θ,j(s)) such that j(s + 1) = j(s) ± 1, j(1) = 1, and each m between 1 and N occurs as j(s) for some s. Note that if j(s + 1) = j(s) − 1, then there must be s ′ > 1 such that j(s ′ − 1) = j(s ′ + 1) = j(s ′ ) − 1. But then the subcomputation of the S-machine Z (θ,j(s)) with history H s starts and ends with the p-letter of the form p M 1 , H ′ does not contain rules corresponding to rules of M 1 and occurrences of ζ(θ) ±1 , ǫ 1 , ǫ 2 = ±1, i = 1, 2. Then H ′ is empty, ǫ 1 = 1, and ǫ 2 = −1.
Proof. At first, let us prove that H ′ is empty. If ǫ 1 = 1, then the p-letters in W · ζ(θ 1 ) have the form p (j) , and no rules from any Z (θ,s) apply to words with such p-letters, hence H ′ is empty (because by assumption it can contain only rules of various Z (θ,j) ). Thus we can assume that ǫ 1 = −1. Similarly ǫ 2 = 1. As in the proof of Lemma 4.6, where each H i is a non-empty history of computation of some Z (θ 1 ,j(s)) such that j(s + 1) = j(s) ± 1, j(1) = N. Note that the p-letters in W · ζ(θ 1 ) −1 and in . Therefore for some s, we must have j(s − 1) = j(s + 1) = j(s) + 1. As in the proof of Lemma 4.6, this implies that H s is empty, a contradiction.
Since H ′ is empty, the p-letters in W · ζ(θ 1 ) have no θ-indices because otherwise they have to be equal to both θ 1 and θ 2 , and H ≡ ζ(θ 1 ) −1 ζ(θ 1 ) would not be reduced. Therefore ǫ 1 = 1, and ǫ 2 = −1.  Proof. If H does not contains the rule ζ(θ 1 ), we get that H ′ is empty as in the proof of Lemma 4.7. Note that the p-letters of the admissible words in the domain ofθ −1 ). It follows that θ 1 ≡ θ 2 , and so the history H is not reduced, a contradiction.
Hence we can assume that H contains ζ(θ 1 ). Then the next rule in H must be ζ(θ 3 ) −1 for some θ 3 because only rules of the formθ and ζ(θ) −1 for positive θ are applicable to admissible words in the range of ζ(θ 1 ) and H ′ does not contain rules corresponding to rules of M 1 . After application of ζ(θ 3 ) −1 , all p-letters in the admissible word have the form p . Recall that the p-letters of the admissible words in the domain ofθ −1 2 have the form p where H ′′ does not contain rules of the form ζ(θ) and their inverses. By Lemma 4.7, H ′′ is empty, and the computation is not reduced, a contradiction. Hence H ′ has the form H ′′ ζ(θ 1 )ζ(θ 2 ) −1 H ′′′ , where H ′′ , H ′′′ do not contain rules of the formθ ±1 and rules of the form ζ(θ) ±1 by Lemma 4.7. Applying now Lemma 4.6 to the computation with historȳ θ 1 H ′′ ζ(θ 1 ) and the first word W , and to the computation with historyθ 2 (H ′′′ ) −1 ζ(θ 2 ) and the first word W · H, we obtain the desired equality H ≡ Π 1,2 (θ 1 , W )Π 1,2 (θ 2 , W · H) −1 and the fact that all words in that computation are positive except possibly the first and the last words. Now if θ 1 = θ 2 , then H ′ must be empty (since the computation is reduced and H ′ is a product of two mutually inverse words in that case by the uniqueness statement of Lemma 4.6) (b), and so the computation is empty, a contradiction.
For every admissible word W of M 2 with the standard base, let π 2,1 (W ) be the word obtained by removing state p-letters, removing θ-indices (if any exist) of other state letters, and removing the M 2 -indices of a-letters, and reducing the resulting word. We obtain a word in the alphabet of state and tape letters of M 1 .
With every admissible word W of the S-machine M 1 with the standard base we associate the admissible word π 1,2 (W ) of M 2 by inserting the state letters p (j) -s next to the left of q j -s, and replacing every a-letter a by a 0 . (We insert the special letters p (1,j) -s instead of p (j) -s if the word W is admissible for the unique start command of M 1 .) Let W 0 be the stop word of M 1 (considered as an S-machine). It exists because the Turing machine M 1 is recognizing. We call the word π 1,2 (W 0 ) the stop word of M 2 .
Note that we have For every input configuration W of the S-machine M 1 , we call π 1,2 (W ) an input word of M 2 . Note that an input word of M 2 has the standard base and all sectors except the q 0 p 1 -sector are empty. For does not correspond to a rule of M 1 , we denote by Π 2,1 (θ ′ ) the empty rule. The map Π 2,1 extends to histories of computations in the natural way. If π 2,1 (W ) is an admissible word for the S-machine M 1 , then π 2,1 (W ) · Π 2,1 (H) = π 2,1 (W ′ ). Proof. The fact that π 2,1 (H) is a history of computation of the S-machine M 1 , and (4.3), immediately follows from the definition of M 2 and the fact that application of rules from Z (θ,i) does not change the value of π 2,1 by Lemma 4.1. The fact that π 2,1 (H) is reduced follows from Lemmas 4.9 and 4.8 The next lemma-definition gives in a sense an inverse function of Π 2,1 .
Lemma 4.11. For every positiveθ-admissible word W of M 2 with the standard base such that there exists a computation w → w 1 → · · · → w · H of the Turing machine M 1 with positive history H, starting with w ≡ π 2,1 (W ) and having the first rule θ, and all admissible words positive there exists a unique reduced computation of M 2 starting with W → W ·θ, whose history is H ′ such that Π 2,1 (H ′ ) ≡ H and the last rule is of the form ζ(θ). That history H ′ will be denoted by Π 1,2 (H, W ). This definition agrees with the notation Π 1,2 (θ, W ) of Lemma 4.6.
Every time we are using the notation Π 1,2 (H, W ) below, the conditions of Lemma 4.11 will be assumed or clearly satisfied. Remark 4.12. Note that if π 2,1 (W ) · H = W 0 , that is the computation of the Turing machine M 1 is accepting, then the corresponding computation of M 2 with history Π 1,2 (H, W ) is also accepting. Proof. Assume that such a computation exists and W ·θ −1 is positive too. Then by Lemma 3.8 this computation is a reduced computation of the symmetric Turing machine M 1 with history θ −1 θ ′ , contrary to the Property (b) of M 1 given by Lemma 2.3. Now assume that the word W ·θ −1 is not positive. By Property (b) from Lemma 2.2, each θ, θ ′ inserts/deletes at most one tape letter. The only non-trivial case is when θ, θ ′ insert an a-letter: in other cases the second word in the computation is obviously positive. But thenθ −1 must insert a letter a −1 which is then removed byθ ′ (in the same sector). Since both rulesθ,θ ′ have word W ·θ −1 in their domains, the left hand sides in all parts of the rules of θ, θ ′ coincide. Since M 1 is the symmetrization of a deterministic Turing machine by construction, θ ≡ θ ′ and our computation is not reduced, a contradiction. Suppose that the length of Π 2,1 (H) is at least 2. Suppose further that the second letter of Π 2,1 (H) is positive, that is H ≡θ 1 H 1θ3 H 2 for some positive θ 3 and H 1 not containing rules corresponding to the positive rules of M 1 . Then H 1 must end with ζ(θ ′ ) for some θ ′ . Then we can apply the induction assumption to the computations with historiesθ 1 H 1 andθ 3 H 2 and conclude that H and all words, except for the first one, in the computation with history H are positive as desired. Now suppose that the second letter in Π 2,1 (H) is θ −1 3 for some positive θ 3 . Since H ends with ζ(θ 2 ) , the last rule in Π 2,1 (H) is positive. Indeed the rule used in any reduced computation of M 2 immediately after a rule of the formθ −1 for some positive θ is either ζ(θ ′ ) −1 for some positive θ ′ orθ ′ for some positive θ ′ (this can be seen by looking at the indices of q-letters of the admissible words). The first option is impossible by Lemma 4.7 , the second option is impossible since we consider the last rule in Π 2,1 (H). 2 ). By the inductive hypothesis, all words in this computation, starting with the second one, and all words in the computation W ·θ 1 → ... → W · Π 1,2 (θ 1 , W ) are positive. By the induction assumption, the computation W ′ ·θ m+1 → ... → W · H also consists of positive words. Therefore the first and the third words in the subcomputation with historyθ −1 mθm+1 are positive contrary to Lemma 4.13. (2) It is nothing to prove if n = 0. The case ǫ 2 = 1 was considered in the proof of claim (1)   Proof. Assume that w t = w 0 , and t > 0 is minimal. Then the computation w 1 → · · · → w t−1 is not a counter-example, and so H is a cyclically reduced word. If H ′ ≡ Π 21 (H) is empty, we consider the computation w 0 → · · · → w 0 • H = w 0 → · · · → w 0 • H 2 → . . . with history H k , where k as large as we want. As in Lemmas 4.6 and 4.9, we have a decomposition H ≡ H 1 . . . H s , where H i corresponds to the work of some Z (θ,i) or equal to some ζ(θ) ±1 and s is bounded by a constant independent of k. It follows that H corresponds to only one Z (θ,i) , and then the equality w t = w 0 and Lemma 4.5 imply that ||w 0 || = ||w 1 || = · · · = ||w t ||. Now ||H k || is uniformly bounded for all k-s, contrary to Lemma 4.3. If ||H ′ || ≥ 1, then Lemma 4.10 gives a reduced computation π 21 (w 0 ) → · · · → π 21 (w t ) with history H ′ . As above we can obtain reduced computations π 21 (w 0 ) → . . . of the S-machine M 1 with histories H ′k . For k ≥ 3, Lemma 4.14 (2) implies that all words in the computation with history H are positive. Then the same property must be true for the computation with history H ′ , and by Lemma 3.8, it is also a computation of the Turing machine M 1 with the same history H ′ , contrary to Lemma 2.3 (c). Thus the lemma is proved by contradiction.
Lemma 4.16. (a) Let X 2 be the set of all words π 1,2 (W ) accepted by M 2 , where W is an input word of the Turing machine M 1 . Then a word W ′ belongs to X 2 if and only if W ′ ≡ π 1,2 (W ), and W is an input word of M 1 accepted by the Turing machine M 1 . Hence the set of words accepted by M 2 is not recursive. (b) For every W ′ ≡ π 1,2 (W ) ∈ X 2 there exists only one reduced computation of M 2 accepting W ′ , the length of that computation is between the length T of the reduced computation of M 1 accepting W (this computation is unique by Lemma 2.3 (e)) and exp(O(T )).
Proof. (a) Let W ′ ≡ π 1,2 (W ), where W is an input word of the Turing machine M 1 . Suppose that W is accepted by the (symmetric) Turing machine M 1 . By part (b) of Lemma 2.3, the history H of the accepting computation consists of positive commands only. Then the computation of M 2 with history Π 1,2 (H, W ) accepts W ′ by Remark 4.12. Suppose that W ′ is accepted by M 2 , and H ′ is the history of an accepting computation C ′ . By Lemma 4.10, Π 2,1 (H ′ ) is a reduced history of an accepting computation of the S-machine M 1 starting with the input admissible word π 2,1 (W ′ ). Therefore by part (c) of Lemma 2.2, the first rule in H ′ isθ for some positive rule θ of M 1 . Again by Lemma 2.2 (c), the last rule of Π 2,1 (H ′ ) is positive. It follows that the last rule of H ′ must be ζ(θ ′ ) for some positive rule θ ′ since the accepted admissible word of M 2 has state letters having no θ-indices. By Lemma 4.14, then all words in computation C ′ are positive because both W and W ′ ≡ π 1,2 (W ) are positive too. Therefore all words in the accepting computation W → ... → π 2,1 (W ′ · H ′ ) of the S-machine M 1 are positive. By Lemma 3.8, the latter computation is an accepting computation of the Turing machine M 1 , whence W ∈ X 1 .
(b) The existence and the uniqueness follow from part (a) of this lemma and Lemmas 4.6 and 4.11. The part about the length of computation follows from Lemma 4.2 (2).
Similarly to the case of Turing machines, for every function f (n), we define f -good numbers for M 2 . We call a number b f -good provided for every input word W from X 2 , if the length of the input sector (that is the Remark 4.18. The machine Z(A) and the copies of it Z (θ,i) do not satisfy Property 3.1 since two a-letters are involved in the (copies of) rules r 12 (a). Therefore further we will use the machineM 2 obtained from M 2 by the application of Lemma 3.3. Note that the claim of Lemma 4.15 is correct forM 2 as well. Indeed if the words w 0 ≡ w t in a computation w 0 → · · · → w t ofM 2 with non-empty reduced history H involve auxiliary state letters, then there is a computation ofM 2 with a reduced history H ′ , where H ′ is a freely conjugate of H, which starts and ends with the words w ′ 0 ≡ w ′ t ′ , having no special state letters. Then Lemma 3.3 and Lemma 4.15 for M 2 lead to a contradiction. Since the modification of M 2 does not touch the rulesθ corresponding to the rules θ of M 1 , the statements of Lemmas 4.16 and 4.17 also remain valid forM 2 . Thus Lemmas 4.15,4.16,and 4.17 will be applied to the modified machineM 2 . Moreover, it follows from the definitions of M 2 andM 2 that these S-machines inherit the Property (c) from Lemma 2.2 of the Turing machine M 1 (for positive rules).
If the sum from Property 3.1 (2) is positive for some rule ofM 2 , then this sum is 1, and we have ||v i || + ||v ′ i || = 1 or ||u i+1 || + ||u ′ i+1 || = 1 for a unique i. In the first case (in the second case) we say that the rule is left (is right). Remark 4.19. Note that similarly, we can define the •-product S • S ′ of any S-machine S and S-machine S ′ = S ′ (A) depending on the tape alphabet A. Furthermore, one can replace the auxiliary machine S ′ by several S-machines S 1 , . . . , S d . Namely, one inserts a p-letter between two consecutive state letters in the standard base of S and treats any subword q i . . . p . . . q i+1 as an admissible subword for S i -s. For each rule θ of S, one has a modified ruleθ of the composition. The application of the ruleθ is normally framed by alternated works of the auxiliary machines S (θ,i) j , and the priorities of the work of these machines may depend on θ. We are not going to define this construction formally, leaving it to the reader. In the next subsection, we shall introduce the •-product ofM 2 and two primitive S-machines.

The machine M 3
Let M 2 be the S-machine M 1 • Z andM 2 the modification from Remark 4.18. For every set of letters A, let A ′ and A ′′ be disjoint copies of A, the maps a → a ′ and a → a ′′ identify A with A ′ and A ′′ , resp. Let (1), p(2), p(3)} and the following positive S-rules. For − → Z we have the rules The head moves from left to right, replacing the word on the tape by its copy in the alphabet A ′ .
Comment: When the head meets R, it turns into p (2).
Comment: The head p(2) moves from right to left, replacing the word in A ′ by its copy in A ′′ .
Comment: When the head reaches the left end of the tape, it turns into p(3).
Remark 4.20. For every a ∈ A, i = 1, 3, it will be convenient to denote ξ i (a) −1 by ξ i (a −1 ). It is clear from the definition ξ i (a) that this does not lead to a confusion.
Remark 4.21. Note that if the machine − → Z (the machine ← − Z ) starts with the word Lp(1)u ′′ R (resp., with Lu ′ p(2)R) and ends with the word Lu ′ p (2) where u ′′ is the word in A ′′ -letters, then the history H of the only reduced computation such that Lp (1) Similarly, any reduced computation of − → Z (of ← − Z ) ending with Lu ′ p(2)R (resp., with Lp(3)u ′′ R) is uniquely determined by its initial admissible word and has length ≤ ||u||+1.

Remark 4.21 implies, in particular
with history H and the standard base. Suppose that both W and W · H contain Lp(1) or both contain p(2)R (resp., p(2)R or Lp (3)). Then H is empty. Remark 4.19), that is we insert copies of ← − Z and ← − Z between every two consecutive state letters ofM 2 . We simplify and unify the notation by changing the value of N and renaming the parts of the state alphabet of M 2 . In this section we assume thatM 2 has the standard base s 0 s 1 ...s N (and forget more detailed earlier notations).
For every i = 1, ..., N , we make copies Y ′ i and Y ′′ i of the alphabet Y i ofM 2 (i = 1, ..., N ). Let Θ be the set of positive commands ofM 2 . The set of state letters of M 3 is Thus the state letters L and R of the copies of machines − → Z and ← − Z are identified with the corresponding S-letters as in the case of M 2 = M 1 • Z. We shall call the state letters from P i -s the control state letters or p-letters, and the other state letters (i.e. the copies of the state letters ofM 2 ), the basic state letters.
The set of tape letters of As an exception , the left-hand sides of the parts ofθ are of the form s 0 ℓ →, p (1,1) →, s 1 ℓ →, p (2,1) →, . . . , s N → if θ is the unique start rule, i.e., they do not depend on the index θ.
A right positive rule θ of the form is replaced by the right ruleθ of M 3 : and Y 2i (θ) = ∅. Now we want to describe the alternating work of the auxiliary machines ← − Z (θ,i) and − → Z (θ,i) . Normally each of them is switched on exactly once in the frame of the rule θ, but the sequence of their turning on depends on θ.
First, we need the following transition rule ζ − (θ). This rule adds θ to all state letters and turns all p (j) into p (θ,j) (1): so that the ruleθ becomes applicable if θ is not a right rule. Again, as an exception, we do not introduce ζ − (θ) for the start rule θ = θ start ofM 2 .
If θ is a right rule, then the rule ζ − (θ) successively switches on the machines − → Z (θ,1) , . . . , − → Z (θ,N ) . (We will not present formulas for the rulesτ i (θ) as in the definition of M 2 , since the explicit form of these rules are not necessary.) Then the state letters p (θ,j) (1) (j = 1, . . . , N ) successively turn into p (θ,j) (2), find themselves just before s i -letters, and the ruleθ can be applicable.
After an application of a non-right ruleθ, the machines − → Z (θ,j) move the p-letters to the write, change p (θ,j) (1) by p (θ,j) (2), and then the machines ← − Z (θ,j) move the p-letters to the left and change p (θ,j) (2) by p (θ,j) (3). After an application of a right ruleθ, only machines ← − Z (θ,j) work. Finally, the transition rule ζ + (θ) removes index θ from all state letters, and turns all If θ is the unique accept rule ofM 2 then all p (j) -s in the above definition of ζ + (θ) must be replaced by special letters p (j,0) -s. An important specification is the following. If θ is a right rule and ||u i+1 ||+||u ′ i+1 || = 1 (see (**)), then the application ofθ always switches on the auxiliary machines in the order . For every admissible word w ofM 2 with standard base, let π 2,3 (w) be the admissible word of M 3 obtained by inserting control state letters p (i) (p (i,1) or p (i,0) if the word w has state letters from the start vector − → s 1 , resp., from the accept vector − → s 0 ofM 2 ) next to the right of each s i−1 , i ≤ N . The stop word of M 3 is π 2,3 (π 1,2 (W 0 )), where W 0 is the stop word of M 1 . For every input word w ofM 2 we call π 2,3 (w) an input word of M 3 . The p (1) s 1 -sector of an admissible word of M 3 is called the input sector of that word.
Assume that w → w · θ is a computation of the machineM 2 with standard base and a positive rule θ. Then, by the definition of M 3 , we have the canonically defined reduced computation · · · → π 2,3 (w) → π 2,3 (w) ·θ → . . . starting and ending with words whose state letters have no θ-indices and all other words do have θ-indices. The computation of M 3 with these properties is unique since the base is standard. Indeed Remark 4.21 and the definition of M 3 uniquely determine the order of rules for each of the auxiliary can start working only if the state letter p (θ,j) (1) is the right neighbor of a letter s (θ,j−1) since the p (θ,j) (1)s (θ,j−1) -sector is locked before the start, and − → Z (θ,j) cannot finish its work until the p-letter becomes the left neighbor of s (θ,j) and turns into p (θ,j) (2), etc.) Thus the following claim is true.
Lemma 4.24. For every computation w → w · θ of the machineM 2 with standard base and a positive rule θ, there is a unique reduced M 3 -computation · · · → π 2,3 (w) → π 2,3 (w) ·θ → . . . such that it starts and ends with words whose state letters have no θ-indices and all other words have θ-indices. The history of this computation starts with ζ − (θ) and ends with ζ + (θ).
We denote the history of this computation by Π 2,3 (θ, w). It follows from Remark 4.21 that the length of this history is 1 + 2(|w| a + N ), where |w| a is the number of a-letters in the word w. If θ is a negative rule ofM 2 , then we invert the computation constructed for θ −1 , and so Similarly, with arbitrary reduced computation w → · · · → w · H with the standard base ofM 2 and having a history H ≡ θ 1 . . . θ t we associate the reduced computation of M 3 with history It follows from the previous paragraph that ||H|| ≤ ||Π 2,3 (H, w)|| = O(||H|| 2 ) for every accepted computation. Indeed |w| a = O(||H||) since the stop word has no tape letters.
Recall that only rules of the form ζ ± (θ) and the start rule involve state letters without θ-indices. Therefore it follows from Lemma 4.24 that every reduced computation with the standard base of M 3 starting and ending with the admissible words without θ-indices in their state letters, has history of the form Π 2,3 (H, w) for some reduced computation w → · · · → w · H ofM 2 . In particular, our discussion and Lemma 4.16 (b) imply the following Lemma 4.25. (a) Let X 3 be the set of all words π 2,3 (w) accepted by M 3 , where w is an input word ofM 2 (or M 2 ). Then a word W belongs to X 3 if and only if W = π 2,3 (w), and w ∈ X 2 . Hence the set of words accepted by M 3 is not recursive. (b) For every W ≡ π 2,3 (w) ∈ X 3 there exists only one reduced computation of M 3 accepting W , the length of that computation is between the length T of the reduced computation ofM 2 accepting w and O(T 2 ).
We can define f -good numbers of M 3 in a similar way as for M 2 . Lemmas 4.17 and 4.25 imply Lemma 4.26. For every constant c > 0, the set of exp(cn)-good numbers of M 3 is infinite.
As in the previous section, we need to define more maps between S-machinesM 2 and M 3 .
For every admissible word W of M 3 with the standard base, let π 3,2 (W ) be the word obtained by removing state p-letters, θ-indices of state letters, and the indices that distinguishes a-letters from the left and from the right of p-letters. We obtain an admissible word ofM 2 . Note that we have For every ruleθ of M 3 corresponding to a rule θ ofM 2 we denote θ = Π 3,2 (θ). Ifθ does not correspond to a rule ofM 2 , we denote by Π 3,2 (θ) the empty rule. The map Π 3,2 extends to histories of computations in the natural way.
Remark 4.27. It can be proved similarly to Lemma 4.10, that if H is a history of a computation of M 3 with standard base and W · H = W ′ , then Π 3,2 (H) is reduced and for some positive θ 1 and θ 2 , and η = ±1.
(1) if B is standard, then the word W ·θ 1 is completely determined by H ′ ; for the rule θ 1 , and B is not a subword of the standard base or of its inverse. Then θ η 2 ≡ θ −1 1 , and no rule from H ′ locks the s (θ,j) p (θ,j+1) -sector (resp., the p (θ,j) s (θ,j) -sector).
Proof. (1) The argument used for Lemma 4.24 shows that since the base is standard, each of the machines − → Z (θ,j) must accomplish its standard work after the application of the rulē θ 1 . Therefore the history of the work of − → Z (θ,j) completely determines the p (j) s j -sector subword of the word W ·θ 1 . The θ-indices of the state letters of this word are obviously determined by the histories of − → Z (θ,j) , and Statement (1) is proved. (2) The assumptions implies that the θ-indices that the state letters have after the application ofθ 1 , must disappear earlier than one appliesθ η 2 . Again by Remark 4.21, it follows that each of the machines − → Z (θ 1 ,j) must perform its standard work. Therefore for every j = 1, . . . , N, the history H ′ has rules locking s (θ,j−1) p (θ,j) (1)-sectors and it has rules locking p (θ,j) (2)s (θ,j) -sectors. Hence, by Lemma 3.4, the base B has no subwords of the form q ±1 q ∓1 , and so B ±1 is a subword of the standard base by the definition of admissible word.
The locking rule τ must belong to the machine ← − Z (θ 1 ,j+1) since other auxiliary machines working after the application of the right ruleθ 1 do not lock this sector. Taking into account the order of the work of auxiliary machines after an application of a right rule, we conclude that the machines Since the last rule of ← − Z (θ 1 ,j+2) locks the p (θ,j+1) s (θ,j+1) -sector, H ′ has a rule locking p (θ,j+1) s (θ,j+1) -sector. Proceeding in this manner, we then consider the work of the preceding machine ← − Z (θ 1 ,j+2) and conclude that the s (θ,j+1) p (θ,j+2) -sectors was locked by by some rules from H ′ . Finally, we see that every sector except for p (θ,j) s (θ,j) was locked by some rule from H ′ . The p (θ,j) s (θ,j) -sector was locked byθ 1 since θ 1 is a right rule. By Lemma 3.4, B is a subword of the standard base or of its inverse, a contradiction. Similar argument works if θ 1 is a left rule. In this case if p (θ,j) s (θ,j) -sector is locked by a rule from H ′ , thenθ 1 switches on the machines , and we again come to a contradiction. Lemma 4.29. Suppose that the admissible word W of M 3 has the standard base. Suppose that a reduced computation applicable to W has history of the form H 3 . Then H does not contain rulesθ corresponding to the rules θ of the S-machineM 2 .
Proof. Suppose that H contains a ruleθ ±1 0 . Thenθ 0 occurs in a subword H ′ of the form where all θ i are positive rules fromM 2 , ǫ i ∈ {−1, 1}, and H i consists of rules of various copies of the S-machines ← − Z and − → Z . We can assume that ǫ 0 = 1 (if not, we can replace H by H −1 ).
Let W be the initial word of the computation with history H 1 . Then the word W ·θ 0 is completely determined by H 1 by Lemma 4.28. Similarly, the word Remark 4.27, the equal words π 32 (W ′ ) and π 32 (W ′′ ) are connected by a non-empty reduced computation of the machineM 2 . This contradicts Lemma 4.15, and the lemma is proved.

The machine M 4
Recall that the set of state letters of M 3 is S 0 ⊔ P 1 ⊔ S 1 ⊔ P 2 ... ⊔ S N where ∪P i contains the control state letters. Let Θ(3) be the set of positive rules of M 3 except for the start and the accept rules. We introduce two copies Y (3) and Y ′ (3) of Θ(3) which will be parts of the tape alphabet of M 4 . Let maps θ → y θ and θ (Every state letter is called a q-letter as earlier, but from now on, we also can use t-, k-, s-, p-letters or s 0 -, p 1 -letters, and so on.) As for M 3 , the p 1 s 1 -sector of an admissible word is called the input sector of that word.
The new parts of the set of state letters are T The new sets of state letters are now denoted by T, K, S 0 , P 1 , ..., P N , S N , K ′ , T ′ . The set of tape letters in the tk-sector is Y (3), the sets of tape letters in ks 0 -sector and in the s N k ′ -sector are empty, and the set of tape letters in the The tape letters in the other sectors are as in M 3 .
The positive rules of the machine M 4 are divided into three Steps. Each rule below contains subrules s 0 → s 0 , t → t and t ′ → t ′ , so we sometimes omit these subrules.
where the s-and p-letters form the start vector − → s 1 for the machine M 3 . Comment: The machine writes the Y (3)-copy of a (positive) history word in the tksector to the left of k 1 . The word between k and k ′ is an input word of M 3 . All sectors except for the tk-sector and the p (1,1) s 1 -sector are locked by the rules of Step 1.
Transition rule (12) from Step 1 to Step 2 is the 'extension' θ(M 4 ) of the unique start rule θ = θ start of the machine M 3 : where the parts of the rule (12) between k-and k ′ -letters are the parts of θ start . Comment: After that rule is applied, the machine is ready to execute copies of the machines − → Z (θstart,j) and ← − Z (θstart,j) , on tapes 1 through N . All sectors except the tk-sector and the p (1,1) s 1 -sector are locked by this rule.
Step 2. For every θ ∈ Θ (3): Comment: On tapes 1 through N , the machine executes (backwards) the history written in the tk-sector, erases the word in that sector, and copies it to the k ′ t ′ -sector. Transition rule (23)=θ(M 4 ) from Step 2 to Step 3 'extends' the accept rule θ = θ accept of M 3 : where the parts of the rule (23) between k-and k ′ -letters are the parts of θ accept .
Comment. All sectors except for the k ′ t ′ -sector are locked by this rule.
where the state letters between k-and k ′ -letters form the accept vector − → s 0 of M 3 Comment: The machine erases the history from the k ′ t ′ -sector. All other sectors are locked by the rules of this Step.
For every admissible input word W ∈ X 3 of M 3 let π 3,4 (W ) ∈ X 4 be the admissible word of M 4 obtained by adding state letters k (1) Remark 4.30. From now on, we do not show the indices (i) (i = 1, 2, 3)) of the letters k, and k ′ assuming that the indices are appropriate for an admissible word.
Step 1 Step 2 Normal work of M 4 from a start word to the accept word (12) (23) The history of that computation is denoted by Π 3,4 (H). That computation first uses rules of Step 1 and writes a mirror copy of H ′ (i.e. H without the start and the accept rules) in the alphabet Y (3) in the tk-sector, then executes rule (12), then executes the computation with history H ′ on the subword between k and k ′ while erasing the word in the tk-sector and moving it onto the k ′ t ′ -sector (written in Y ′ (3)). After H ′ is completed, rule (23) is executed, then the k ′ t ′ -sector is erased using rules of Step 3. Let X 4 = π 3,4 (X 3 ). Every word from this set of input configurations is accepted by M 4 . To simplify the notation, we can include the rules (12) and (23) to Step 2. Suppose that a history of computation of M 4 has the form H ≡ H 1 H 2 ..., where all rules of each H i belong to the same Step j i , and H i is a maximal subword of H with this property. Then we say that the step history of that computation is (j 1 )(j 2 )... (or that H is of type (j 1 )(j 2 )...). The following lemma is a straightforward consequence of the definition of M 4 and will be used without reference throughout the paper. Lemma 4.31. Every 2-letter subword of any step history of a computation of M 4 (with any base) is one of the following words: (1)(2), (2)(1), (2)(3), (3)(2). Two consecutive steps are separated by (12) ±1 or by (23) ±1 , resp., and the letters of the history neighboring any (12) (or (23)) from the left and from the right belong to different Steps. Lemma 4.32. An admissible word of M 4 is not in the domain of the reduced histories of types: Proof. Cases (a) and (b) are almost identical, so suppose that the history H contains a subword (12) 12) from the computation that is in the domain of H must have the subword between k ′ and t ′ empty (since it is in the domain of (12) −1 ). Similarly, the word V · H must have the subword between k ′ and t ′ empty.
Since this word is empty, we conclude that H is not reduced, a contradiction.
Suppose that the step history is of the form (c). Then the history H has the form Step i only. Restricting the computation to the subwords between k and k ′ of the admissible words, we obtain two reduced accepting computations of M 3 with the same initial word from X 3 and histories H −1 2 , H ′ 2 (this follows from the definitions of the rules of Step 2). By Lemma 4.25 Since every rule of Step 1 multiplies the tk-sector of the admissible word by an a-letter uniquely determined by the rule, the tk-sectors A tk , B tk in the words W · H 3 (23) −1 H 2 and W · H 3 (23) −1 H 2 (12) −1 H 1 (12) respectively are the same. Since every rule of Step 1 multiplies that sector by a letter uniquely determined by that rule, we deduce that a copy of the word H 1 multiplied by A tk is A tk . Hence H 1 is empty, which contradicts the assumption that the computation is reduced. (2) The word W 2 is from X 3 and θ 1 ...θ n is a computation of M 3 accepting W 2 .
Proof. Immediately follows from Lemmas 4.34 and 4.31. Lemma 4.36. Recall that X 4 is the set of all words of the form π 3,4 (W ), W ∈ X 3 .
An input word W ′ ≡ π 3,4 (W ) is accepted by M 4 if and only if W ∈ X 3 . Hence the language accepted by M 4 is not recursive.
Proof. If W ∈ X 3 then π 3,4 (W ) ∈ X 4 since the corresponding computation was constructed together with the definition of M 4 . Let W ′ ≡ π 3,4 (W ) for some admissible input word W of M 3 and H be the history of an accepting computation for W ′ . By Lemma 4.34 (b) Definition 4.37. Let T 1 < T 2 < ... be all the times of acceptance of acceptable input words of M 3 .
We will call a computation of M 4 standard if it has the standard base and history of the form (12)(2)(23). The following lemma gives (almost) linear upper bounds for the lengths of many computations with standard base.
Then the length of this accepting computation of W is at most 6|W | a .
(b) Let b be an integer such that any standard computation starting with a word W with |W | a ≤ b has the history of length < log b. Suppose W is any accepted admissible word for M 4 with ||W || < b. Then the time of accepting W by any reduced computation of M 4 is at most 4|W | a + 3 log b.
Suppose that the step history of H is (2) consists of rules of Step 1 (resp. Step 3). By Lemma 4.33, the length of (12)H ′ 2 (23) is one of the T i . Since every rule of Step 2 multiplies the tk-sector by a letter uniquely determined by that rule, and in any word in the domain of (23), the tk-sector is empty, we conclude that the tk-sector of the word W · H 2 (12) −1 H 1 (12) is a copy of H ′ 2 , hence its length is T i − 2. The k ′ t ′ -sector of that word is empty and every rule from H ′ 2 multiplies that sector by a letter uniquely determined by the rule. Hence the Since every rule of Step 3 multiplies that sector by a letter, and in the stop word of M 4 that sector is empty, we conclude that ||H 3 || = T i − 2. Hence || (12) Note that since every rule of Step 2 multiplies the k ′ t ′ -sector by a letter uniquely determined by that rule, and in a word in the domain of (12) −1 that sector is empty, we can conclude that ||H 2 || ≤ |W | a . Similarly since the rules of Step 1 multiply the tk-sector by letters uniquely determined by these rules, we conclude that (We use that if a group word U of length l is obtained from a word V of lengths k after a series of one-side multiplications by one letter, and successive multiplications are not mutual inverse, then the number of multiplications does not exceed k + l.) Therefore and since in the case under consideration, we have ||H|| ≥ 9T i by the condition of the lemma, it follows that |W | a ≥ (||H||−3T i )/3 > ||H||/6, as required for the part (a). Now assume that the assumption of (b) holds. Note that every rule of H 2 multiplies the k ′ t ′ -sector by a letter and the input p 1 s 1 -sector also by at most one letter, the rules of H 1 do not touch the input sector. Therefore the input sectors or W · H 2 and W · H 2 (12) −1 H 1 (12) are the same and their lengths are at most the sum of lengths of the input sector of W and the k ′ t ′ -sector of W . Hence the length of the input sector of 2,3). Then again by Lemma 4.33 ||H 2 || = T i − 2 for some i, and the length of the tk-sector in W · H 1 is T i − 2. As in the previous paragraph, Under the assumptions of (a) then ||H 1 || > 9T i − 2T i + 2 > 7T i . Since every rule of H 1 multiplies the tk-sector by a letter, we also have that ||H 1 || does not exceed the sum of lengths of tk-sectors in W and in W · H 1 , whence ||H 1 || ≤ |W | a + T i − 2. Therefore |W | a > 6T i and Suppose that the assumptions of (b) hold. Then since the input sectors of W and W · H 1 (12) are the same, and their length is ≤ |W | a < b, we conclude that T i ≤ log b, and Suppose that the step history is (2)(3), that is H ≡ H 2 (23)H 3 , and, again, H i has rules only from Step i, i = 2, 3. Note that every rule of H 2 multiplies the tk-sector by a letter, and that sector in any word which is a domain of (23) must be empty. Hence ||H 2 || ≤ |W | a . Every rule in H 2 , H 3 multiplies the k ′ t ′ -sector by a letter, hence This implies both (a) and (b).
Finally suppose that the step history is (3). Then clearly ||H|| ≤ |W | a , and both (a) and (b) follow.
We conclude that in every case both (a) and (b) hold. Proof. Indeed, W · H does not contain a-letters, and each rule of H decreases the number of a-letters in the admissible word by at most 4 (every rule of M 4 affects at most four a-letters: two letters in the subword between k and k ′ , one letter in the subword between t and k and one letter in the subword between k ′ and t ′ ).
Definition 4.40. Let Q i be a base letter. (Recall that usually we take a representative q i ∈ Q i .) We say that Q i (or q i ) is active from the left (resp., from the right) for a rule θ if in the corresponding component is not trivial (and so equal to a letter the free group by Property 3.1 (1) of M 4 ). If q i is active from the left (right) for θ, then we say that q −1 i is active from the right (left) for θ. We also say that q i active for θ if it is active from the left or active from the right. Otherwise q i is passive for θ. Proof. Recall, that the rule (12) extends the start rule θ = θ start of M 3 . Therefore the first rule of H has p θ,1 (1) in the left-hand side. If no rule of H changes p θ,1 (1), then every rule is (the extension of) a rule of the machine − → Z θ,1 with the p 1 -part of the form where p 1 is active from the both sides. Otherwise the history has a subword of type either (12) Step 2 but it is passive. However this case is impossible since then every rule of H ′ inserts (or deletes) one letter a ′ in the s 0 p 1 -sector from the right, different rules insertes different letters, and the s 0 p 1 -sector is empty when the rule (12) or (12) −1 is applicable.
Every rule either makes a control state letter p i active from both sides or locks a neibor sector. This property is useful for computations with non-standard bases as in the following Lemma 4.42. If the base of a reduced computation of M 4 contains a subword (pp −1 p) ±1 , where p is a control state letter, then all rules of the computation correspond to the copy of the S-machine − → Z or of ← − Z containing that state letter, and either every rule is a copy of some ξ 1 (a) ±1 (a depends on the rule) or every rule is a copy of some ξ 3 (a) ±1 .
Proof. Indeed, suppose that p ∈ P i . Then every rule not from the copy of − → Z or of ← − Z containing that state letter, locks the sector s i−1 p i or the sector p i s i , and the copies of ξ 2 and of ξ 4 lock either sector s i−1 p i or sector p i s i . Now we can apply Lemma 3.4. Lemma 4.38 and the following lemma show the role of the 'historical' tk-and k ′ t ′sectors.
Proof. Let W be the initial word of the computation. Since every rule of H 2 , H ′ 2 multiplies the k ′ t ′ -sector by one letter which determines the rule, and every word in the domain of (12) ±1 has that sector empty, we conclude that ||H 2 || is equal to the length of the Similarly, every rule from H 3 multiples the k ′ t ′ -sector by a letter that determines the rule. Hence ||H 3 || ≤ ||U || + ||V || = ||H 2 || + ||H ′ 2 || as required.

The machine M
Consider now 2L ≫ 1 copies of the machine M 4 , denote them by M 4 (i), i = 1, . . . , 2L, We denote the state and tape letter of M 4 (i) accordingly, by adding index i to all letters, and all rules. Let Θ(M 4 ) be the set of positive rules of M 4 . Let B be the standard base of M 3 , B(i) be the copy word B with new extra index i added to all letters, and We now consider the S-machine M with the rules (we shall denote θ(M ) by θ also) and the standard base where we identify the state t-letters t(1) and t ′ (1) of M 4 (1) with t 1 and t 2 , resp., the t-letters t(2) and t ′ (2) of M 4 (2) with t −1 3 and (t ′ 2 ) −1 , resp, an so on. Moreover we identify t 2L+1 with t 1 and consider the standard base of M up to cyclic permutations which may start with any t-letter and end with the same t-letter. The stop word is defined accordingly (every letter in the standard base is replaced by the corresponding letter in the stop word of M 4 (i)). The stop word without the last letter t 2L+1 is called the hub. We also may take the hub up to cyclic permutations.
That construction is similar to the construction in [19] and [14], though the application of mirror copies of machines goes back to the works of Boon and P.S. Novikov (see [17]). The condition L >> 1 makes hub graph hyperbolic (see Lemmas 5.18 and 5.19), and the mirror symmetry of the word (4.6) is used for the surgery we define in Subsection 12.2.
For every admissible word W of M 4 with the standard base we denote by W (M ) the corresponding admissible word t 1 k (1) The letters in the copy W (i) of the word W are equipped with the extra index (i). Thus every a-letters and every q-letter (except for t and t ′ -letters), and every letter θ(i) of the alphabets of M has this extra index. We call it the M -index of the letter and take it modulo 2L.
(2) Also notice that ||W (M )|| < 2L||W || for every W .    4.46. Considered as a cyclic word, the hub has the following symmetries: it does not change if we reflect it about any t-letter or any t ′ -letter (with indices changing appropriately, and state letters, except for t-and t ′ -letters, replaced by their inverses). From Remark 4.44 (1), it follows, that every admissible accepted word of M has similar symmetries.

Groups and diagrams
Every S-machine can be considered as a finitely presented group (see [19] and also [15], [13]). Here we apply the construction to the machine M. To simplify formulas, it is convenient to redefine N once again. From now on we shall denote by N + 1 the length of the smallest subword of the hub containing two t-letters. Thus the length of the hub and Θ is the set of rules of the S-machine M. (But we will remember that, as for the machine M 4 , the state letter of M are partitioned into the subsets of t-letters, t ′ -letters, k-letters, k ′ -letters, s-letters, and p-letters.) The finite set of generators of the group M (the same letter as for the machine) consists of q-letters corresponding to the states Q, a-letters corresponding to the tape letters from Y, and θ-letters corresponding to the rules from the positive part Θ + of Θ.
The relations of the group M correspond to the rules of the machine M ; for every for all a ∈Ȳ j (θ). (Here θ LN ≡ θ 0 .) The first type of relations will be called (θ, q)-relations, the second type -(θ, a)-relations. Finally, the required group G is given by the generators and relations of the group M and by one more additional relation, namely the hub-relation where W M is the hub, i.e., the accept word (of length LN ) of the machine M.
Remark 5.1. The word W M has the symmetries mentioned in Remark 4.46. Since the machine M is built of 2L copies M 4 (i), the set of relations is also symmetric in the following sense. Every relation θ j a = aθ j from (5.7) has 2L copies (including itself) (5.7) involves neither t-nor t ′ -letters then it has L copies (including itself) and L mirror copies. Every relation containing a t-or a a t ′ -letter (denote this letter byt) has formtθ i+1 = θ it , i.e., it contains no a-letters.

Minimal diagrams
Recall that a van Kampen diagram ∆ over a presentation P = A | R (or just over the group P ) is a finite oriented connected and simply-connected planar 2-complex endowed with a labeling function Lab : E(∆) → A ±1 , where E(∆) denotes the set of oriented edges of ∆, such that Lab(e −1 ) ≡ Lab(e) −1 . Given a cell (that is a 2-cell) Π of ∆, we denote by ∂Π the boundary of Π; similarly, ∂∆ denotes the boundary of ∆. The labels of ∂Π and ∂∆ are defined up to cyclic permutations. An additional requirement is that the label of any cell Π of ∆ is equal to (a cyclic permutation of) a word R ±1 , where R ∈ R. The label and the combinatorial length ||p|| of a path p are defined as for Cayley graphs. The van Kampen Lemma states that a word W over the alphabet A ±1 represents the identity in the group P if and only if there exists a diagram ∆ over P such that Lab(∂∆) ≡ W, in particular, the combinatorial perimeter ||∂∆|| of ∆ equals ||W ||. ( [7], Ch. 5, Theorem 1.1). The word W representing 1 in P is freely equal to a product of conjugates to the words from R ±1 . The minimal number of factors in such products is called the area of the word W. The area of a diagram ∆ is the number of cells in it. A diagram having the smallest number of cells among all diagrams with the same boundary label is called minimal. By van Kampen's Lemma, Area(W ) is equal to the area of a minimal diagram ∆ over P with Lab(∂∆) ≡ W. This definitions imply Lemma 5.2. Assume that a diagram ∆ 0 is divided into two subdiagrams ∆ 1 and ∆ 2 by a simple path p. Let a minimal diagram ∆ have the same boundary label as ∆ 0 . Then Area(∆) ≤ Area(∆ 0 ) = Area(∆ 1 ) + Area(∆ 2 ).
We will study diagrams over the groups M and G. The edges labeled by state letters ( = q-letters) will be called q-edges, the edges labeled by tape letters (= a-letters) will be called a-edges, and the edges labeled by θ-letters are θ-edges.
Remark 5.3. The symmetries of relations observed in Remark 5.1 makes possible the following construction for given i ≤ 2L and a diagram ∆ over M. Let ∇ be a mirror copy of the map ∆. For every edge e of ∆ whose label is equipped with an M -index (j) (i.e., if e is neither t-nor t ′ -edge), the mirror copy of e in ∇ is marked by the same letter but with M -index equal to (2i − j − 1). The label t j of e (the label t ′ j ) should be replaced for the mirror image by t −1 2i−j (resp., by (t ′ 2i−j ) −1 ). It is easy to see that ∇ is also is a diagram over M. We say that ∇ is obtained by t i -reflection from ∆. Similarly one can speak on t i -reflections for paths of ∆.
We denote by |p| a (by |p| θ , by |p| q ) the a-length (resp., the θ-length, the q-length) of a path/word p, i.e., the number of a-edges/letters (the number of θ-edges/letters, the number of q-edges/letters) in p.
The cells corresponding to Relation (5.8) are called hubs, the cells corresponding to (θ, q)-relations are called (θ, q)-cells, and they are called (θ, a)-cells if they correspond to (θ, a)-relations.
Every minimal van Kampen diagram is reduced, that is it does not contain two cells (= closed 2-cells) that have a common edge and are mirror images of each other (if such pairs of cells exist, they can be removed to obtain a diagram of smaller area and with the same boundary label). To study (van Kampen) diagrams over the group G we shall use their simpler subdiagrams such as bands and trapezia, as in [11], [19], [1], etc. Here we repeat one more necessary definition.
Definition 5.4. Let Z be a subset of the set of generators X of the group M . A Z-band B is a sequence of cells π 1 , ..., π n in a reduced van Kampen diagram ∆ such that • Every two consecutive cells π i and π i+1 in this sequence have a common edge e i labeled by a letter from Z.
• Each cell π i , i = 1, ..., n has exactly two Z-edges, e i−1 and e i (i.e. edges labeled by a letter from Z).
• If n = 0, then B is just a Z-edge.
The counterclockwise boundary of the subdiagram formed by the cells π 1 , ..., π n of B has the factorization e −1 q 1 f q −1 2 where e = e 0 is a Z-edge of π 1 and f = e n is an Z-edge of π n . We call q 1 the bottom of B and q 2 the top of B, denoted bot(B) and top(B). Top/bottom paths and their inverses are also called the sides of the band. The Z-edges e and f are called the start and end edges of the band. If n ≥ 1 but e = f, then the Z-band is called a Z-annulus.
We will consider q-bands, where Z is one of the sets Q i of state letters for the machine M , θ-bands for every θ ∈ Θ, and a-bands, where Z = {a} ⊆ Y . The convention is that a-bands do not contain (θ, q)-cells, and so they consist of (θ, a)-cells only.
Remark 5.5. To construct the top (or bottom) path of a band B, at the beginning one can just form a product x 1 . . . x n of the top paths x i -s of the cells π 1 , . . . , π n (where each π i is a Z-bands of length 1). No θ-letter is being canceled in the word W ≡ Lab(x 1 ) . . . Lab(x n ) if B is a q-or a-band since otherwise two neighgbor cells of the band would be mirror copies of each other which is impossible in a reduced diagram.
Also there are no cancellations of a-letters if B is a q-band. Indeed if both π i and π i+1 have a-edges on their top then the corresponding rules of M must belong to the same Step since every cell is passive for (12)and (23)-rules. Similarly they correspond to the rule of the same machine is a q-band for some control letter p i since the rules ξ 2 and ξ 4 provide no active cells. Then the rules are determined by the a-letters, and the cells should be mirror copies as in the previous paragraph. Similar argument works if q corresponds to any other letter of the standard base except for s i . But active s i -cell cannot have a common edge too since this edge has a θ-index in the label, and so the diagram is not reduced again.
Thus, if B is a q-band (or an a-band), then the top/bottom label is a product x 1 . . . x n . If B is a θ-band then a few cancellations of a-letters (but not θ-letters) are possible in W. (This can happen if one of π i , π i+1 is a (θ, q)-cell and another one is a (θ, a)-cell.) We will always assume that the top/bottom label of a θ-band is a reduced form of the word W . This property is easy to achieve: by folding edges with the same labels having the same initial vertex, one can make the boundary label of a subdiagram in a van Kampen diagram reduced (e.g., see [19]).
If the path (e −1 q 1 f ) ±1 or the path (f q −1 2 e −1 ) ±1 is the subpath of the boundary path of ∆ then the band is called a rim band of ∆. We shall call a Z-band maximal if it is not contained in any other Z-band. Counting the number of maximal Z-bands in a diagram we will not distinguish the bands with boundaries e −1 q 1 f q −1 2 and f q −1 2 e −1 q 1 , and so every cell having two Z-edges belongs to a unique maximal Z-band.
We say that a Z 1 -band and a Z 2 -band cross if they have a common cell and Z 1 ∩Z 2 = ∅.
Sometimes we specify the types of bands as follows. A θ-band corresponding to the transition rule (12) (to (23)) is called a (12)-band ((23)-band), and it consists of (12)-cells (of (23)-cells). A q-band corresponding to one of the letters t i of the base (4.6) (resp., to t ′ i , k(i), k ′ (i)) is called a t-band ( t ′ -band, k-band, k ′ -band) since the M -index i is, generally, not important for further considerations (but we may keep it if it is essential). Similarly, we can omit the M -index speaking on s-and p-bands, but we distinguish different letters of each particular B i in the standard base, e.g., the s 0 -letter follows after the k-letter in each subword B i hence the standard base (4.6) has 2L different s 0 -letters (one in each subword B i ), 2L different p 1 -letters, and so on. Also this agreement allows to speak on (12)-letters and (12)-edges, . . . , p i -letters, p i -edges, and p i -(or s i -) bands. The papers [12], [1], [16] contain the proof of the following lemma in a more general setting. (In contrast to Lemmas 6.1 [12] and 3.11 [16], we have no x-cells here.) Lemma 5.6. A reduced van Kampen diagram ∆ over M has no q-annuli, no θ-annuli, and no a-annuli. Every θ-band of ∆ shares at most one cell with any q-band and with any a-band.
If W ≡ x 1 ...x n is a word in an alphabet X, X ′ is another alphabet, and φ : X → X ′ ∪ {1} (where 1 is the empty word) is a map, then φ(W ) ≡ φ(x 1 )...φ(x n ) is called the projection of W onto X ′ . We shall consider the projections of words in the generators of M onto Θ (all θ-letters map to the corresponding element of Θ, all other letters map to 1), and the projection onto the alphabet {Q 0 ⊔ · · · ⊔ Q LN −1 } (every q-letter maps to the corresponding Q i , all other letters map to 1).
Definition 5.7. The projection of the label of a side of a q-band onto the alphabet Θ is called the history of the band. The Step history of this projection is the Step history of the q-band. The projection of the label of a side of a θ-band onto the alphabet {Q 0 , ..., Q LN −1 } is called the base of the band, i.e., the base of a θ-band is equal to the base of the label of its top or bottom.
As for words, we will use representatives of Q j -s in base words. (If p ∈ Q 4 , s ∈ Q 5 , we shall say that the word pas has base ks instead of Q 4 Q 5 , and so on.) Definition 5.8. Let ∆ be a reduced diagram over M which has boundary path of the form p −1 1 q 1 p 2 q −1 2 , where p 1 and p 2 are sides of q-bands, and q 1 , q 2 are maximal parts of the sides of θ-bands such that Lab(q 1 ), Lab(q 2 ) start and end with q-letters. Then ∆ is called a trapezium. The path q 1 is called the bottom, the path q 2 is called the top of the trapezium, the paths p 1 and p 2 are called the left and right sides of the trapezium. The history (Step history) of the q-band whose side is p 2 is called the history (resp., Step history) of the trapezium; the length of the history is called theheight of the trapezium. The base of Lab(q 1 ) is called the base of the trapezium. Remark 5.9. Notice that the top (bottom) side of a θ-band T does not necessarily coincides with the top (bottom) side q 2 (side q 1 ) of the corresponding trapezium of height 1, and q 2 (q 1 ) is obtained from top(T ) (resp. bot(T )) by trimming the first and the last a-edges if these paths start and/or end with a-edges. We shall denote the trimmed top and bottom sides of T by ttop(T ) and tbot(T ). By definition, for arbitrary θ-band T , ttop(T ) is obtained by such a trimming only if T starts and/or ends with a (θ, q)-cell; otherwise ttop(T ) = top(T ). The definition of tbot(T ) is similar. By Lemma 5.6, any trapezium ∆ of height h ≥ 1 can be decomposed into θ-bands T 1 , ..., T h connecting the left and the right sides of the trapezium. The word written on the trimmed top side of one of the bands T i is the same as the word written on the trimmed bottom side of T i+1 , i = 1, ..., h. Moreover, the following lemma claims that every trapezium simulates the work of M. It summarizes the assertions of Lemmas 6.1, 6.3, 6.9, and 6.16 from [14]. For the formulation (1) below, it is important that M is an S-machine. The analog of this statement is false for Turing machines. (See [13] for a discussion.) Lemma 5.10. (1) Let ∆ be a trapezium with history θ 1 . . . θ d (d ≥ 1). Assume that ∆ has consecutive maximal θ-bands T 1 , . . . T d , and the words U j and V j are the trimmed bottom and the trimmed top labels of T j , (j = 1, . . . , d). Then U j , V j are admissible words for M, and (2) For every reduced computation U → · · · → U · H ≡ V of M with ||H|| ≥ 1 there exists a trapezium ∆ with bottom label U , top label V , and with history H.
If H ′ ≡ θ i . . . θ j is a subword of the history θ 1 . . . θ d from Lemma 5.10 (1), then the bands T i , . . . , T j form a subtrapezium ∆ ′ of the trapezium ∆. This subtrapezium is uniquely defined by the subword H ′ (more precisely, by the occurrence of H ′ in the word θ 1 . . . θ d ), and ∆ ′ is called the H ′ -part of ∆.

Properties of the group M.
In this subsection, we want to translate the properties of the machine M in the language of diagrams over the group M.
Recall that every (θ, q)-cell π has a boundary label of the form U i θ i+1 V −1 i θ −1 i (see Relations (5.7)), where the word U i (the word V i ) has exactly one positive q-letter q i ∈ Q i (q ′ i ∈ Q i ). Hence the boundary label of π is q i w 1 (q ′ ) −1 i w 2 for some words w 1 , w 2 . Definition 5.11. The cell π considered as a one-cell q-band with base q i is called active from the right (from the left) if the word w 1 (the word w 2 ) has at least one a-letter. If π with base q i is active from the right (from the left) then, by definition, the same cell considered as a q-band with base q −1 i is active from the left (resp., from the right). A (θ, q)-cell is called passive if it is not active either from the left or from the right.
The comparison with Definition 4.40 shows that the cell π with base q ±1 i is active from the left (resp., active from the right, passive) iff the base letter q ±1 i is active on the left (resp., active on the right, passive) for the rule corresponding to the θ-edges of π.
Definition 5.12. We say that a q-band with base q i is active from the left (from the right) if every cell of it (with the same base) except for the first cell and the last one (if the first and/or the first cell corresponds to the rules (12) ±1 or (23) ±1 ), is active from the left (from the right). A q-band is called passive if every its cell is passive. Similarly one can speak on a q-band with base q i which is passive from the left or passive from the right.
Remark 5.13. The letter s 0 in the standard base of M 4 corresponds to the left-most α-marker of the machines M 1 − M 4 , and so every s 0 -band is passive (from both sides).
Definition 5.14. We say that a q-band C with base q i is strongly active from the left (resp. right) if every its cell π is active from the left (from the right), ∂π has exactly one a-edge on the left side (right side) of C, and these a-letters are different for the cells corresponding to different rules of the history of C. Lemma 5.15. Let ∆ be any reduced diagram over M. Let C be a q-band, corresponding to the part Q i of Q. Suppose that C is strongly active from the left (resp. right). Then ∆ does not have an a-band starting and ending on the left side (resp., right side) of C.
Proof. Suppose that an a-band A starts and ends on bot(C) which is the left side of C. Let ∆ ′ be the subdiagram bounded by A and C.
Then ∆ ′ has no other maximal q-bands except the part C ′ = C ∩ ∆ ′ because a-bands and q-bands do not intersect and ∆ ′ has no q-annuli by Lemma 5.6. Since maximal a-bands do not intersect, we can assume without loss of generality that ∆ ′ does not have any other a-bands starting and ending on bot(C ′ ). Since C ′ is strongly active on the left, and the sides of A consist of θ-edges, we conclude that C ′ consists of two cells having common q-and a-edges. A θ-cell in C is completely determined by its a-letter on its bottom side (see Remark 5.5 for the argument). Therefore those two q-cells cancel, a contradiction with the assumption that ∆ is reduced.
The next Proposition summarizes previously proved properties of the various submachines of the S-machine M . We formulate these properties in the language of van Kampen diagrams which makes it more convenient to apply these properties to the group G.
Recall that the standard base of M 3 is denoted by B. Note that the standard base of M contains L copies B(i) of B (i = 1, 3, . . . , 2L − 1) and L copies of B −1 . We call the base of an admissible word of M aligned, if every maximal subword of this base without letters t, k, k ′ , t ′ is a subword of a copy of B ±1 .
A base of an admissible word of M is called normal if it is a subword of a power of the base of the hub. (Recall that t 1 and t 2L+1 were identified in the definition of the machine M.) A base is called large if it contains a copy of B ±1 .
We shall say that a (θ, q)-cell π in a van Kampen diagram over M is odd if it contains exactly one a-edge on its boundary, and its base is not k or k ′ . A θ-band with (1-letter) history of type (2) is called odd if it contains odd cells.
A trapezium over M whose top label is one of 2L copies of the stop word of M 4 will be called M 4 -accepting trapezium. (The trapezium pictured in Subsection 4.3 is M 4 -accepting and in addition, its bottom label is an input word of M 4 .) A trapezium whose base is a copy of the standard base of M 4 is standard if its bottom label is in the domain of the rule (12) and its top label is in the domain of (23) −1 . By Lemmas 4.33 and 5.10, every standard trapezium has height T i for some i and corresponds to a standard computation of M 4 .
Proposition 5.17. The following properties of the group M hold. In all these properties we assume that we are given a reduced van Kampen diagram ∆ over M , all bands, cells and edges are bands, cells and edges of that diagram.
(i) A two letter base of a θ-band is either a subword of the word (4.6) or of the inverse word, or it has form q ±1 q ∓1 for a base letter q.
(ii) Every cell with base k (every cell with base k ′ ) corresponding to a rule of Step 1 or Step 2 except for the (12) ±1 -rule (corresponding to a rule of Step 2 or Step 3 except for the (23) ±1 -rule), is active from the left (resp., from the right) and passive from the right (resp., from the left). Every non-k-cell (non-k ′ -cell) corresponding to a rule of Step 1 (resp., of Step 3) is passive.
(iii) (a) The boundary of every cell has at most two a-edges. It has either 0 or 2 a-edges if it is a (θ, q)-cell corresponding to a control letter p i , otherwise is has at most one a-edge.
(b)If there are two a-letters a and a ′ in the boundary label of a cell π then a ′ is a copy of a −1 and π is either a (θ, a)-cell or a (θ, q)-cell corresponding to a control letter p i , and the a-edges are separated by q-edges in ∂π.
(c) A (θ, a)-cell has two mutually inverse θ-letters in the boundary label.
(d) Two (θ, q)-cells corresponding to control letters p i and p j with i = j, have no common a-letter in the boundary labels.
(iv) If a θ-band T has 3 consecutive cells π 1 , π 2 , π 3 , where π 2 corresponds to a control letter p ±1 i and π 2 is not active from both sides then one of the cells π 1 , π 3 is a (θ, q)-cell whose base is an s-letter.
(v) Let a (θ, q)-cell π i of a θ-band T have base q. If T corresponds to a rule of Step 1 or to (12) (respectively, Step 3 or to (23)), and the next cell, π i+1 in T is a (θ, a)-cell, then q can be only one of the following letters: t, p 1 , k −1 , s −1 1 (resp., k ′ or (t ′ ) −1 ) (with some indices) . For other values of q the next after q letter in the base of T cannot be q −1 .
(vi) If in the base of a θ-band, there is a subword p ±1 i p ∓1 i p ±1 i for some control letter p i and there are neither k ±1 -nor (k ′ ) ±1 -letters, then the active cells in this band are precisely the p i -cells, and these cells are active from both sides.
(vii) Suppose that C is a k ±1 -, (k ′ ) ±1 -, or p ±1 i -band with top path y. Suppose that each cell of C has a common a-edge with y. Then no a-band of ∆ can start and end on y.
In the remaining parts of the Proposition, ∆ is a trapezium.
(ix) If p 1 p −1 1 s −1 0 is a subword of the base of ∆, and the history of ∆ has the form (12)H, then H is of type (2), it has no rules (12) ±1 , (23) ±1 , and in the H-part of ∆, all p 1 -cells are active both from the left and from the right.
(x) Suppose that ∆ is M 4 -accepting. Then the step history of ∆ is a subword of (2)(1) (2)(3). If W is the label of the bottom path of ∆, and h is the height of ∆, then ||W || a ≤ 4h.
(xiii) Suppose that the base of ∆ is not aligned and the history is of type (2). Then the label of the top (and of the bottom) of every maximal s j -band of ∆ admits a factorization of the form u is an a-letter or 1 (i = 1, . . . , m) , v i is a group word in θ-letters, b i commutes with every letter of v i by virtue of (θ, a)-relations, and each of u, w has at most one a-letter.
(xiv) If the base of ∆ is large, and its history has the form H 3 , then ∆ does not have odd cells π.
(xv) Suppose that the base of ∆ has the form k −1 k or k ′ (k ′ ) −1 , and all k-(resp. k ′ -cells) of ∆ are active. Let W and W ′ be the labels of the bottom and top of ∆ respectively. Then the history of ∆ has the form H 1  (xvii) Let m > 0 be an integer such that for every standard trapezium with a bottom label W, inequality |W | a ≤ m implies ||H|| < log m. Suppose that ∆ is M 4 -accepting, the history of ∆ is H, and the bottom label W ′ satisfies the inequality |W ′ | a ≤ m. Then we have ||H ′ || ≤ 4|W ′ | a + 3 log m.
(xviii) The set of numbers m satisfying the assumption from (xvii) is infinite. (iv) Indeed, if a component p i → ... of a rule from M is not active from both sides, then it locks either s i−1 p i -sector or the p i s i -sector, and we can apply Property (i) and Lemma 3.4. (v) Indeed, the rules from Step 1 and the rule (12) (resp. Step 3 and the rule (23)) lock all sectors except the the tk-sectors, and p 1 s 1 -sectors (resp. the k ′ t ′ -sectors) of the admissible words of M . It remains to use Lemma 3.4. (vi) This also follows from Lemma 3.4: if a rule of M does not lock the p i s i -sectors or s i−1 p i -sectors, then its component involving p i has the form p i → ap ′ i b, where a, b are tape letters, and all other components, exept for k-and k ′ -components, do not involve tape letters.
(vii) The condition means that the band C is active on the left and has no (passive) (12)-or (23)-cells. It follows from the definition of M that then k ±1 , (k ′ ) ±1 or p i -band is strongly active on the left. It remains to apply Lemma 5.15. (viii) This follows from Lemmas 4.32 (a,b) and 5.10.
(ix) Let us apply Lemma 5.10 and consider the reduced computation corresponding to ∆. The rule (12) switches on the copy of the machine − → Z θ,1 where θ = θ start is the start rule of M 3 . The (copies of the) rules of the form ζ 1 (a) ±1 cannot follow by the (copy of the) rule ζ 2 since ζ 2 locks the p 1 s 1 -sector. Also, by Lemma 3.5, it cannot follow by the rules (12) ±1 or (23) ±1 locking the s 0 p 1 -sector. Therefore each of the rules of H is of the form ζ 1 (a) ±1 , and the statement follows.
(x) The first statement follows from Lemma 4.34 (b) because ∆ is the trapezium corresponding to an accepting computation of a copy of the machine M 4 . The second property immediately follows from Lemma 4.39.
(xi) Indeed, every sector of the standard base of M is locked by either (12) or (23). It remains to use (i) and Lemma 3.4. (xii) Indeed, by Property (xi), the base of ∆ is normal. Since its length is at least N , it must contain a copy of the base of M 4 , and it remains to use Lemma 4.34 (a).
(xiii) The base has non-aligned subword B 0 without k-and t-letters. Hence the copy of B ±1 0 is not a subword of the standard base of the machine M 3 . If H is the history of the corresponding computation of M 3 , then by Lemma 4.28 (2) for some positive rules θ, θ 1 , . . . , θ ′ ofM 2 (θ and/or θ ′ may be absent).
Recall that a (θ, s j )-cell has at most one a-edge, and it has no a-edges, if it corresponds to a rule of one of the auxiliary machines − → Z , ← − Z . Hence the label of a side of the s j -band has form u( is an a-letter or 1 (i = 1, . . . , m) , v i is a group word in θ-letters, and each of u, w has at most one a-letter; and we should prove Let us consider the right side of the s j -band. (The 'left' case is similar.) Then θ i is a right rule, and by Lemma 4.28 (3), no rule of the subword θ i H ′ θ −1 i of H locks the s j p j+1 -sector, and so the letter b i commutes with every θ-letter of v i by the definition of relations for the machine M.
(xiv) follows from Lemma 4.29 since the cells corresponding to M 3 -rules can have exactly one a-edge in the boundary only if they correspond to the rules ofM 2 .

Diagrams with hubs
Given a reduced diagram ∆ over the group G, one can construct a planar graph whose vertices are the hubs of this diagram plus one improper vertex outside ∆, and the edges are maximal t-bands of ∆.
Let us consider two hubs Π 1 and Π 2 in a minimal diagram, connected by a t i -band C i and a t i+1 -band C i+1 , where there are no other hubs between these t-bands. These bands, together with parts of ∂Π 1 and ∂Π 2 , bound either a subdiagram having no cells, or a trapezium Ψ of height ≥ 1. The former case is impossible since in this case the hubs have a common t-edge and they are mirror copies of each other contrary to the reducibility of the diagram. We want to show that the latter case is not possible either.
Indeed, in the latter case, both the top and the bottom of Ψ are the subwords of the hub W ±1 M , i.e. , the history H of Ψ and H −1 are the histories of M 4 -accepting subtrapezia of Ψ. Therefore, by Property (xii) (b), the history H is of type (3). We may assume that the base of Ψ has a subword (k ′ t ′ ) ǫ with ǫ = 1 since otherwise one can replace Ψ by its mirror copy. Let Γ be the maximal subtrapezium of Ψ with base k ′ t ′ . Then every cell of the maximal k ′ -band C of Γ is active from the right by Property (ii). But the a-bands starting on C cannot end on the passive (see Property (ii)) t ′ -band of Γ. They also cannot end on C by Property (vii). Hence ||H|| = 0, a contradiction.
Thus, any two hubs of a reduced diagram cannot be connected by two t-bands, such that the subdiagram bounded by them contains no other hubs. This property makes the hub graph of a reduced diagram hyperbolic, in a sense, since the degree L of every proper vertex (=hub) is high (L ≥ 40). Below we give a more precise formulation (proved for diagrams with such a hub graph, in particular, in [19], Lemma 11.4 and in [11], Lemma 3.2). 18. If a reduced diagram over the group G contains a least one hub, then there is a hub Π in ∆ such that L − 3 consecutive maximal t-bands B 1 , . . . B L−3 start on ∂∆ , end on the boundary ∂Π, and for any i ∈ [1, L − 4], there are no discs in the subdiagram Γ i bounded by B i , B i+1 , ∂Π, and ∂∆.
A maximal q-band starting on a hub of a diagram is called a spoke. Lemma 5.18 implies Lemma 5.19. If a reduced diagram ∆ has m ≥ 1 hubs then the number of q-edges in the boundary path of ∆ is greater than mLN/2 .
Proof. ∆ has a hub Π satisfying the assumption of Lemma 5.18. Then we can separate a subdiagram with only one hub Π from ∆ by making cuts along the t-bands B 1 , B L−3 , and along the part of ∂Π having 3 t-edges. Since by Lemma 5.6, every spoke of Γ i (i ∈ [1, L − 4]) starting on Π must end on ∂Π, the remaining diagram ∆ ′ with m − 1 hubs has at most |∂∆| q − (L − 4)N + 4N q-edges in the boundary. Since L − 8 > L/2 the statement follows by induction on m.

Parameters
The following constants will be used for the proofs in this paper.
L, N << J << δ −1 << (δ ′ ) −1 << c 0 << c 1 << · · · << c 7 (5.9) For each of the inequalities of this paper, one can find the highest constant (with respect to the order <<) involved in the inequality and see that for fixed lower constants, the inequality is correct as soon as the value of the highest one is sufficiently large. This principle makes the system of all inequalities used in this paper consistent.

Modified length of words and paths.
Recall that the standard length ||w|| of a word (a path) is called the combinatorial length.
To introduce new length function on the group words in the generators of the groups M and G we first consider a word w having no q-letters. We set the length |a| of every a-letter a equal to δ. We set the length of any θ-letter equal to 1, but the the length |v| of any θa-syllable, i.e., a 2-letter word v with one θ-letter and one a-letter, will be equal to 1 + δ ′ . The length of a decomposition of w in a product of letters and θasyllables is the sum of lengths of the factors of this decomposition. The length |w| of w is the smallest length of such decompositions. Finally, the length |W | of arbitrary word W ≡ w 0 u 1 . . . u n w n , where u i -s are q-letters and the words w j -s have no q-letters, is, by definition, n + n i=0 |w i |. The length of a path in a diagram is the length of its label. The perimeter |∂∆| of a diagram is similarly defined by cyclic decompositions of its boundary ∂∆.
Why do we need such a modification ?
The assumption that a-edges are much shorter than other edges is used in Lemma 13.2 (Step (2)) and in other lemmas. The assumption that δ ′ << δ, and so the length of a θa-syllable is less than the sum of lengths of its letters, is used in Lemma 7.18 and in many other lemmas.
Proof. (a) Since every path is a product of q-, θ-, and a-edges, the first inequality follows. The second one is true because at most e a-edges can be joined with θ-letters to form 2-edge subpaths of s, and the remaining a-edges has to be taken alone with coefficient δ when one calculate |s|. To make the reader more familiar with the definition of |s|, we leave claims (b), (c), (d) for exercises.

Mixture on the boundary of a diagram
Let O be a circle with two-colored finite set of points (or vertices) on it, more precisely, let any vertex of this finite set be either black or white. We call O a necklace with black and white beads on it. We want to introduce the mixture of this finite set of beads.
Assume that there are n white beads and n ′ black ones on O. We define sets P j of ordered pairs of distinct white beads as follows. A pair (o 1 , o 2 ) (o 1 = o 2 ) belongs to the set P j if the simple arc of O drawn from o 1 to o 2 in clockwise direction has at least j black beads. We denote by µ J (O) the sum J j=1 cardP j (the J-mixture on O). Below similar sets for another necklace O ′ are denoted by P ′ J . In this section, J ≥ 1, but later on it will be a fixed large enough number J from the list (5.9). Proof. (a) It is clear from the definition that cardP j ≤ n 2 − n , and the statement (a) follows. The statements (b) and (c) are obvious.
. Then for some j ∈ {1, . . . , J}, the pair (o, o ′ ) belongs to P j but does not belongs to P j+1 . Now, on the one hand, the same pair (o, o ′ ) considered on O ′ does not belong to P ′ j . On the other hand, we clearly have which is equal to m 1 m 2 . The lemma is proved.
We will use also the mixture of beads on a closed interval x = [a, b] with real a < b. A string of beads is a finite sets of white and black beads on x, but in the definition of mixture µ c (x) we consider only pairs (o, o ′ ) of white beads, where o < o ′ . This gives us the mixture µ c J (x) as above. Lemma 6.2. Let x be a string of beads and J ≥ 1.
(a) µ c J (x) ≤ J(n 2 − n)/2. (b) Suppose a string x ′ is obtained from x after removal of a white bead v. Then cardP j − n < cardP ′ j ≤ cardP j for every j, and µ c J (x) − Jn < µ c J (x ′ ) ≤ µ c J (x). (c) Suppose a string x ′ is obtained from x after removal of a black bead v. Then cardP ′ j ≤ cardP j for every j, and µ c J (x ′ ) ≤ µ c J (x). (d) Assume that there are three black beads v 1 < v 2 < v 3 on x such that the interval (v 1 , v 3 ) has at most J black beads, and the intervals (v 1 , v 2 ) and (v 2 , v 3 ) have m 1 and m 2 white beads, respectively. If x ′ is obtained from x after removal of the bead v 2 , then Assume that the set of black beads is non-empty. Then there is a black bead v, such that it divides x into two subsegments with m 1 and m 2 white beads, respectively, m 1 ≥ m 2 , and m 1 m 2 ≤ µ c 1 (x) ≤ (2m 1 − 1)m 2 .
Proof. The proof of statements (a) -(d) is similar to the proof of Lemma 6.1. To prove claim (e), we choose the black bead v so that the difference |m 1 − m 2 | is minimal. We can assume that m 1 ≥ m 2 . Since m 1 white beads are separated by v from m 2 white beads, we have µ c 1 (x) ≥ m 1 m 2 . On the other hand, there is a subsegment with m 1 − m 2 pairwise non-separated (by black beads) white beads. Therefore For any diagram ∆, we introduce the following invariant κ(∆) = µ 1 (∂∆). To define them, we consider the boundary ∂(∆), as a κ-necklace, i.e., we consider a circle O with ||∂∆|| edges labeled as the boundary path of ∆. By definition, the white beads are the mid-points of the θ-edges of O and black beads are the mid-points of the q-edges O. Then, by definition, the κ-mixture on ∂∆ is κ(∆) = µ 1 (O).
We will need an analogous parameter ν J (∆). The definition of the ν-necklace on ∂∆ is similar, but the black beads of it correspond to t-and t ′ -edges only while the set of white beads coincides with that for the κ-necklace. The ν-necklace has ν J -mixture for every J ≥ 1, which is called the ν J -mixture on ∂∆ and denoted by ν J (∆).
Recall that a θ-letter is said to be (12)-letter ((23)-letter) if it corresponds to the rule (12) (to (23)). Such a letter is special if it is involved in a ( (12), t)-relation or in a ((23), t ′ )-relation. An edge is a (12)-edge (a (23)-edge, a special edge) if it is labeled by a (12)-letter (by a (23)-letter, by a special θ-letter, respectively). Note that if a q-band C has a special (12)-edge (a special (23)-edge) on the left side, then the base of C is either a t ±1 or a k (resp., either a (t ′ ) ±1 or a (k ′ ) −1 ).
To define an auxiliary parameter λ(∆) we consider, the λ-necklace, where white beads are the middle points of all θ-edges of O which are neither (12)-edges nor (23)-edges, and the black beads are the middle points of all non-special (12)-and (23)-edges and all qedges of O. The λ-necklace defines the λ J -mixture on ∂∆ for every J, and for J = 1, we denote it by λ(∆).
Similarly we have κ(x), λ(x), µ(x), and ν J (x) for any path x in a diagram. (Consider the strings of beads to define.) Clearly, each of this values remains unchanged if one replaces x by x −1 .

General properties of combs
By Lemma 5.10, every property of a trapezium can be formulated as a property of a computation of the S-machine M , and vice versa. Unfortunately minimal diagrams can be much more complicated than trapezia. Now we define diagrams which are the main subject of our research in this paper.
As in [15], we say that a reduced diagram Γ over M with reduced boundary path (having no subpaths of the form ee −1 ) is a comb if it has a rim q-band C (the handle of the comb), and every maximal θ-band of Γ has a cell in C. In particular, every trapezium is a comb.
Suppose that a maximal q-band C of a diagram ∆ starts and ends on ∂∆. Then it divides ∆ into two subdiagrams Γ and Γ ′ , where Γ ′ contains C. Suppose Γ is a comb with handle C. Then we call Γ a subcomb of ∆.
By Lemma 5.6, any maximal q-band C ′ of a comb Γ is itself a handle of a subcomb Γ ′ of Γ which does not contain (by definition of subcomb of a comb) cells from the handle C of Γ if C ′ = C. In this case Γ ′ is a proper subcomb of the comb Γ.
The base width of a comb is by definition the maximal number of letters in the bases of its θ-bands. The history H and the Step history of a comb are the history and Step history of its handle. If H ′ is a subword of H then H ′ -part of the comb is the union of all maximal θ-bands corresponding to H ′ .
It will be convenient to view a comb Γ with the handle on its right. Thus the bottom of the handle C is the right side of C, and it is the part of ∂Γ. Respectively, every q-band of Γ has the right side and the left side. The words written on tops/bottoms of θ-bands of Γ and their bases will be read from left to right, and so, for a base letter q, one can distinguish q-and q −1 -bands of Γ. In particular, a q-band of Γ can be active from the left, active from the right (or passive). If a q-band D is passive from the left (from the right), then h = |y ′ | ≤ |y|, where h is the number of cells in D, (resp., |y ′ | ≥ |y| = h) by the definition of length and Lemma 5.20.
We introduce the following permanent notation for a comb Γ with a handle C. Denote by H the history of C and set h = ||H||, i.e., h is the length of C, the number of q-cells in C. The comb Γ is a one-Step comb if the history H is one-Step, i.e., H has one of the types (1), (2), or (3).
The boundary of C is x 1 yx 2 y ′ , where x 1 and x 2 are the boundary q-edges of the band C and yz is the boundary of Γ. (Thus, y is the right side of C, and (y ′ ) −1 is the left side.) Similarly we have the decomposition (y ′ ) −1 z ′ for the boundary of Γ\C, where z = x 2 z ′ x 1 . By definition, Area ′ (Γ) = Area(Γ\C). Since z starts (ends) with the q-edge x 2 (with x 1 ), we have |∂Γ| = |y| + |z| by Lemma 5.20 (b). We also use y ∆ , z ∆ , ... instead of y, z, . . . if we want to stress that the notation relates to a particular comb ∆.
Proof. (a), (b) Since the path y has no q-edges, we have κ(y) = 0 (ν J (y) = 0, respectively), and so κ c (Γ) = κ(z) ≥ 0 ( ν c J (Γ) = ν J (z) ≥ 0, resp.). (c) Consider the strings of beads on z and on y used in the definitions of the comb mixture λ c (.). By Lemma 5.6, the maximal θ-bands of Γ establish a bijection between the white vertices of z and white vertices of y, preserving the order of the beads on z and y −1 , respectively. Every black bead on y must belong to a non-special θ-edge f. By the condition of the lemma, we have a black bead on the corresponding edge e of z. Hence one can apply Lemma 6.1 (c) to the strings of beads on z and y several times to conclude that λ(z) ≥ λ(y), and so λ c (Γ) ≥ 0.
If∆ is a subcomb of a diagram ∆ and Γ is a subcomb of∆, then for every J ≥ 1, Proof. (a) Let y = y Γ , and z = z Γ , xz the boundary path of ∆. To obtain the necklace O ′ corresponding to ∆\Γ, one replaces the subpath z of the boundary by y −1 . Therefore the pairs of white beads counted to get λ(z) are replaced by pairs counted to get λ(y).
(Note that the white beads of z are in bijective correspondence with white beads of y by the definition of comb and Lemma 5.6.) Since every white bead of z is separated from any white bead of ∂∆\∂Γ by the black beads in the middle of the first and the last edges of z, Inequality (a) is proved for λ-mixtures. The case of κ-mixtures is similar. The proofs of claims (b), (c), and (d) are also similar. The path y Γ has no t-edges, and the first inequality of (e) follows. Similarly, every pairs of white beads which makes a contribution to ν c J (∆) but not to ν c J (∆\Γ) also contributes to ν J (∆) but not to ν J (∆\Γ), and the second inequality of (e) follows. The proof of the version in the parentheses is similar.
Let Γ be a comb and z 1 , . . . , z r the maximal subpaths of z = z Γ containing no q-edges. We denote by l 1 , . . . , l r their θ-lengths, and define l − = l Γ − to be h − max r i=1 l i . (Note that h = h Γ = l i by Lemma 5.6.) A θ-band which starts on the handle C of a comb Γ will be called simple if it has no (θ, q)-cells except for the cell of C, and is maximal with respect to this property.
We call a maximal q-band B a derivative band, if it is not C but it can be connected with C by a simple θ-band. Throughout the paper, we will use notation C 1 , . . . C s for derivative bands of a comb Γ. It is possible that s = 0, and every maximal θ-band is simple in this case.
Every derivative band C i is a handle of a subcomb Γ i (which does not contain C). We will use this notation and call Γ i a derivative subcomb of Γ. It follows from the definitions that every cell of a comb belongs either to a derivative subcomb or to a simple band of Γ.
Recall that every maximal θ-band of a comb, in particular, a maximal θ-band crossing a derivative band C i , must cross the handle C. Therefore every cell of C i is connected with C by a θ-band. Since there is a simple θ-band among these θ-bands, no other derivative C j can intersect these connecting θ-bands by Lemma 5.6, i.e., all of them are simple. It follows that different derivative subcombs are disjoint, and if C 1 , . . . , C s is the system of all derivative bands in Γ with histories H 1 , . . . , H s , then H 1 , . . . , H s are pairwise disjoint subwords in the history H of Γ. Therefore s Then, either every maximal θ-band ending on z i 0 crosses some derivative band C j , where j = j(i 0 ), or every maximal θ-band crossing z i 0 crosses no derivative bands because otherwise a q-band would cross z i 0 . (This follows from the definitions of comb, of z i -s and from Lemma 5.6.) In the former case, Lemma 7.5. In the above notation, we have hh − ≤ hl − ≤ 2κ c (Γ).
Proof. By (7.10), it suffices to prove the second inequality. There are h white beads on z. Every such a bead o belongs to one of the paths z i having θ-length at most max r i=1 l r . Therefore for every such o, there are at least l − white beads o ′ on z such that o and o ′ are separated on z by a black bead. Thus, we obtain at least hl − pairs (o, o ′ ) of white beads on z separated by black beads. Since one of the pairs (o, o ′ ) and (o ′ , o) contributes 1 to κ c (Γ), the lemma is proved.
Let the handle C of a comb Γ is a t ±1 -or (t ′ ) ±1 -band with history having no (23)rules or no (12)-rules, respectively; and every derivative C i is a k ±1 -or a (k ′ ) ±1 -band such that there are no special θ-edges (corresponding to the rules (12) and (23)) in the derivative subcomb Γ i . A subband B of some C i which has neither (12)-nor (23)edges and is maximal with respect to this property, is called a short derivative of C. By Property (vii), there are no maximal a-bands starting and ending on the same short derivative band. Let h ′ 1 , . . . be the lengths of all short derivatives. Let h ′ be the number of maximal θ-bands in Γ, which do not correspond to the rules (12) and (23).
Proof. The sets of ends of the θ-bands crossing two short derivatives are separated in z Γ either by a q-edge or by a non-special θ-edge. Therefore arguing as in the proof of Lemma 7.5, we come to inequality h ′ h ′ − ≤ 2λ(z Γ ) = 2λ c (Γ). (We note that under the assumption on the history, λ(y Γ ) = 0 since C is a t ±1 -or (t ′ ) ±1 -band.) This implies the statement of the lemma if h ′ − = 0 since in this case we have h ′ ≥ h/3 because the handle C, being a reduced diagram, cannot have two consecutive cells corresponding to the rules (12), (23) (or inverse). If h ′ − = 0 the claim of the lemma is obvious.
Lemma 7.7. Let Γ be a comb with a handle C of length h. Then the number a ij of all maximal a-bands of Γ starting on a derivative band C i and ending on the bands C j with j = i is at most h − . The total number of cells in these a-bands over all i < j does not exceed hh − ≤ 2κ c (Γ).
Proof. Recall that derivative subcombs with different handles C i and C j are disjoint and separated by these handles (which are q-bands) from the remaining part of Γ. Therefore every a-band A connecting some C i and C j (i = j), connects a-edges of cells on the right sides of these derivative bands. But every q-cell of C i has at most one a-edge on the right side of it by (iii) (b). Besides, a connecting a-band A under consideration either starts or ends on some C j , where j = i. Thus the total number of all connecting a-bands cannot exceed h − h r for arbitrary r ≤ s. Now the first statement of the lemma follows from the definition of h − . Since the number of cells in A is at most h by Lemma 5.6, the second statement is also proved by Lemma 7.5.
Lemma 7.8. Let Γ be a comb and let its handle C be a t ±1 -or (t ′ ) ±1 -band with history having no (23)-rules or (12)-rules, respectively, and every derivative C i is a k ±1 -or a (k ′ ) ±1 -band such that there are no special θ-edges in the derivative subcomb Γ i . Let B 1 , . . . Proof. (a), (b) Note that every white bead of Γ i (of Γ(i)) is placed on the boundary of Γ, and two white beads of ∂Γ i separated by a black bead are also separated by the same black bead on ∂Γ. Since the sets of white beads of Γ i and Γ j (of Γ(i) and Γ(j)) are disjoint for i = j, the statements (a) and (b) follow from the definition of κ c (.).
Assume in addition that the handle C is passive from the left and there are no derivative bands C i such that some non-trivial a-band starts and ends on ∂C i . Then the total area of all simple θ-bands S 1 , . . . , S h of Γ is at most Proof. (a) Notice that |z ′ | ≥ h + δ ′ α by Lemmas 5.6 and 5.20 (a), and so The total number of cells in all a-bands connecting the derivative bands is at most hh − by Lemma 7.7. If a (θ, a)-cell π of a simple θ-band S j does not belong to any such connecting a-bands, then one of the ends of the maximal a-band containing π must belong to ∂Γ because C is passive from the left. The number of such a-bands is at most α, and the total number of their cells is at most αh, because their lengths do not exceed h by Lemma 5.6 . Since a simple band has one q-cell, the number of cells in all the simple θ-bands is at most h(h − + α + 1).
Remark 7.11. If C i is a derivative band of a comb Γ, then every a-band connecting two cells from C i is of length at most h i , and the total area of of such bands crossing simple bands of Γ at most h 2 i /2. Hence if we omit the assumption that there are no derivative bands C i such that some non-trivial a-band starts and ends on C i , then we may add Lemma 7.10 (b), and in this case the total number cells n s in all simple bands satisfies If we use both Lemmas 7.7 and 7.8 instead of Lemma 7.7 in the proof of Lemma 7.10 we get Lemma 7.12. Let Γ be a comb and let its handle C be a t ±1 -or (t ′ ) ±1 -band with history having no (23)-rules or no (12)-rules, respectively, and every derivative C i is a k ±1or a (k ′ ) ±1 -band such that there are no special θ-edges in the derivative subcombs of Γ i . Then the total area of all simple θ-bands of Γ is at most h The proof of the following lemma can be obtained from the proof of [15,Lemma 4.10] by replacing |Γ| a by |z| a and replacing the constant C by 2 (since C was the maximum of the numbers of a-letters in (θ, q)-relations in [15]). Lemma 7.13. Let h and b be the height and the base width of a comb Γ, respectively, and let T 1 , . . . T h be consecutive θ-bands of Γ . We can assume that bot(T 1 ) and top(T h ) are contained in ∂Γ. Let α = |z Γ | a , and we denote by α 1 the number of a-edges on bot(T 1 ). Then α + 8hb ≥ 2α 1 , and the area of Γ does not exceed 4bh 2 + 2αh.
Remark 7.14. For a comb Γ, we will use symbol [Γ] to denote the product h Γ (|z Γ |−|y Γ |). As we noted in Introduction, an estimate of the form Area(Γ) ≤ C[Γ] (where C does not depend on Γ) would be perfect for the proof of the main theorem. It follows from the definition of comb that every maximal θ-band of Γ starting on y Γ ends on z Γ and vice versa, that is |z Γ | θ = |y Γ | θ = h Γ . Clearly |z Γ | q − 2 ≥ |y Γ | q = 0 since the path z Γ contains at least 2 q-edges of the handle of Γ, and therefore, when we estimate |z Γ | − |y Γ | from below in the proofs of several lemmas, our goal is to obtain a lower bound for the difference |z Γ | a − |y Γ | a .
We observed earlier that if the handle of a comb Γ is passive from the right, then |y Γ | = h Γ , and so [Γ] is equal to h Γ (|z Γ | − h Γ ), and therefore it is positive. Moreover: Proof. By Lemma 5.20 (c), |y Γ | ≤ h Γ + 1. If the base width of Γ is b, then, by Lemma 5.6, z Γ has at lest 2b q-edges and at least h Γ θ-edges. Hence by Lemma 5.20(a), Remark 7.16. Further we are finding appropriate estimates for the areas of combs Γ-s or for the areas of some proper subcombs of them provided the base width b of Γ is not too small and not too large. It is not small in some lemmas because we need a choice to select a suitable subcomb of Γ, and b is not too large since the estimates of Lemma 7.13 and of other lemmas depend on b. The sufficiency of the upper bound b ≤ 15N will be seen later. Lemma 7.17. Let Γ be a comb with base width b ≤ 15N and with passive handle C. Assume that Γ has a derivative band C i 0 which contains an active from the right subband C of length h 0 . Assume also that at most (1 − δ)h 0 maximal a-bands starting onC and ending on one of the bands C, C 1 , . . . , Proof. To prove statement (a), we consider two cases.
The proof of statement (b) is similar, but now two cases appear due to the comparison of α with δ 2 ( h i )/2, which leads to inequality h i < 4δ −2 in the second case. Also one takes into account inequalities h i ≤ h and (|z i | − |y i |) ≤ |z| − |y| in both cases.
Lemma 7.18. Assume that a comb Γ has no maximal q-bands except for its handle C, and there are no non-trivial a-bands both starting and terminating on y ′ = (y ′ ) Γ . (a) If C is active from the left or passive from the left, then If C is active from the left or C is passive (from both sides), then Proof. (a) Let T be a longest θ-band in Γ, d the number of a-cells in T . Denote by T 1 and T 2 the top and the bottom of T . Consider the families S 1 and S 2 of a-bands starting on T 1 and T 2 , respectively, which are maximal with respect to the requirement that these bands do not contain cells from T . Observe that the cardinalities |S 1 | and |S 2 | of these sets satisfy inequality −1 ≤ |S 1 | − |S 2 | ≤ 1 (7.12) since every maximal a-band of Γ crossing T 1 has to cross T 2 (and vice versa), with at most one exception for the a-band stating on the a-edge of the unique (see (iii) (b)) (θ, q)-cell of T .
If there were a non-trivial a-band from S 1 and a non-trivial a-band from S 2 both ending on the path y ′ , then the maximal extension of one of them would connect different edges of y ′ contrary to the assumption of the lemma. Therefore either no non-trivial band from S 1 ends on y ′ or no non-trivial band from S 2 ends on y ′ .
We may consider the former case only.
Observe that a derivative band of a comb is close to the handle of this comb.
Definition 7.19. If C ′ is close to C, then there is a unique minimal subtrapezium in ∆ containing both C ′ and a subband B of C, where the numbers of (θ, q)-cells in C ′ and in B are equal. We will denote this filling subtrapezium by T p(C ′ , C).
Lemma 7.20. Assume that a comb ∆ has no active k-or k ′ -cells and contains a θ-band T having a subword (pp −1 p) ±1 in the base, where p is a control letter. Then ∆ has a one- Step subcomb Γ such that Area(Γ) ≤ (δ ′ ) −1 [Γ].
Proof. Consider the maximal p-bands C ′ and C ′′ of ∆ crossing T at the (q, θ)-cells corresponding to the first and the third letters of the subword (pp −1 p) ±1 , respectively. Then C ′ is a handle of a subcomb ∆ ′ of ∆, and the filling trapezium T p(C ′ , C ′′ ) has base (pp −1 p) ±1 . By (v), (vi), all the q-cells of T p(C ′ , C ′′ ), in particular, of C ′ , are active from both sides and has one-step history. It follows from Property (vi) applied to the comb ∆ ′ ∪ T p(C ′ , C ′′ ), that every q-band of ∆ ′ is either active from both sides or passive, and no non-trivial a-band of ∆ ′ can start and end on the same q-band by (vii). Hence there is a subcomb Γ of ∆ ′ satisfying the condition of Lemma 7.18 (b), and the statement is proved.

Intersections of chains and θ-bands
Let the boundary ∂π of a (θ, q)-cell π have a p i -edge for a control state letter p i . Then by Property (iii) (a), ∂π either has no a-edges or contains two a-edges. Below we utilize this property in the definition of chain. Assume that A 1 , . . . , A m are maximal a-bands such that A i terminates on an a-edge of an active p-cell π i and A i+1 starts with a different a-edge of π i (i = 1, . . . , m − 1). Then we say that A 1 , π 1 , A 2 , π 2 , . . . , A m form a chain with m − 1 links π 1 , . . . , π m−1 . By Property (iii), all links are p-cells for the same control base letter p = p j . A chain A is called a chain-annulus if the first a-edge of A 1 coincides with the last one of A m .
It also follows that if A 1 starts with an edge e 1 and A m ends with f m , then the letters Lab(f m ) and Lab(e 1 ) are either equal or they are copies of each other in different subalphabets Y i and Y i+1 (corresponding, respectively, to some parts Y ′ j and Y ′′ j of the tape alphabet of the machine M 3 ).
A chain A is non-trivial if it has at least one cell.
Lemma 8.1. Let x be a subpath of the boundary of a reduced diagram ∆ without hubs, and Lab(x) a reduced word in a tape subalphabet Y i of the machine M. Then no chain A can start and end on x.
Proof. Proving by contradiction, we assume that a non-trivial chain A starts and ends on x. Notice that it cannot cross itself since every cell has at most two a-edges by (iii) (a). Thus it starts with an edge e of x and ends at an edge f of x, where e = f, but Lab(e) ≡ Lab(f ) −1 since these two letters belong to the same subalphabet Y i . We may assume that A is chosen so that ex ′ f is a subpath of x, where the subpath x ′ is of minimal possible length. Now the chain A and the path x ′ bound a subdiagram ∆ ′ all of whose boundary aedges belong to x ′ . By our observation, every q-edge on the boundary ∂∆ ′ is a p ±1 -edge for the same control base letter p = p j . Also every p-cell π of ∆ ′ is active from both sides. Indeed if a cell π of ∆ ′ is not active from both sides it does not belong to the chain A by definition. Therefore π must have a neighbor (θ, s i )-cell in ∆ ′ by ((iv)) (consider the maximal θ-band of ∆ ′ containing π). Then we may apply Lemma 5.6 to the maximal s i -band of ∆ ′ containing the (θ, s i )-cell and obtain a letter of the form s i in the boundary label of A or in Lab(x), a contradiction.
It follows that every (θ, q)-cell in ∆ ′ is a p-cell (corresponds to a control letter) active from both sides. Since a maximal chain cannot end on a p-cell, every maximal chain of ∆ ′ must start and end on x ′ . This property and the minimality of choice for x ′ imply that |x ′ | = 0, and so Lab(x) has a non-empty freely trivial subword Lab(ef ); a contradiction. The lemma is proved. Lemma 8.2. Let a non-trivial chain A crosses a maximal p-band C of a reduced diagram ∆ over M twice at cells π ′ and π ′′ . Then there is a p-cell π 0 in C between π ′ and π ′′ , which is not active from both sides.
Proof. As in the proof of Lemma 8.1, there is a subdiagram ∆ ′ bounded by the portion of A and a segment x of the side of C between π and π ′ . As there, arguing by contradiction, we may assume that x has no a-edges. Hence, if there is no cell π 0 lying between π ′ and π ′′ in C which is not active from both sides then the cells π and π ′ must share a p-edge. Since the chain A connects π and π ′ , we obtain that these two cells must have the same a-letter in the boundary labels (being letters from the same subalphabet Y i ), and they are mirror copies of each other as it follows from the defining relations of the group M, having two a-letters.
We come to a contradiction because ∆ is a reduced diagram. The lemma is proved. Lemma 8.3. Assume that no θ-band of a comb ∆ has a base with a subword (pp −1 p) ±1 , where p is a control letter. Then every chain A of ∆ has at most 9 common (θ, a)-cells with any θ-band T of ∆.
Proof. Let π 1 , . . . π m be the common cells of A and T counted on T from left to right. Denote by T ′ the subband of T starting with π 1 and ending by π m . Every (θ, q)-cell of T ′ must be a p-cell since every maximal q-band of ∆ crossing T ′ , has to cross the chain A too by Lemma 5.6. Since by the assumption of the lemma and by Property (i), the base of T has no triples of consecutive p ±1 -letters, the subband T ′ can have at most two (θ, q)-cells.
Assume that A crosses T consequently at 3 (θ, a)-cells π i 1 , π i 2 , π i 3 , and i 1 < i 3 < i 2 , i.e., A has a 'convolution of a spiral' A ′ , starting at π i 1 and ending at π i 3 .
T By Lemma 8.1 for the part ∆ ′ of ∆ bounded by the subchain A 23 of A ′ connecting π i 2 and π i 3 and the subband of T connecting the same cells, T has a p-cell π between π i 2 and π i 3 . The maximal p-band C crossing T at π must cross A ′ at least twice (above and below T ). Hence there is a part of A ′ satisfying, together with C, the condition of Lemma 8.2, and so there is a cell π 0 given by that lemma, inside the part ∆ ′′ of ∆ bounded by A ′ and the part T 13 of T connected π i 1 and π i 3 . But then, according to Property ((iv)), ∆ ′′ has to contain some s i -cell neighboring π 0 , contrary to Lemma 5.6 since neither A ′ nor T 13 have s i -cells. Thus our assumption on the existence of A ′ leads to a contradiction, and so i 3 > i 2 if i 2 > i 1 .
Assume that A crosses T consequently at 4 (θ, a)-cells π i 1 , π i 2 , π i 3 , π i 4 . We may assume that i 1 < i 2 , and so i 1 < i 2 < i 3 < i 4 . Then again by Lemma 8.1, we have at least 3 p-cells on T ′ (between π iu and π i u+1 for u = 1, 2, 3), a contradiction. Hence such a series of common (θ, a)-cells is impossible, and since A has at most 2 common (θ, q)-cells with T , we conclude that traveling along A one meets m ≤ 3 + 1 + 3 + 1 + 3 = 11 cells of T (at most 3 (θ, a)-cells, then a (θ, q)-cell, and so on) , and the number of a-cells among them does not exceed 9. Proof. Assume that A is a chain-annulus. By Lemma 5.6 it must have a link π i . Then there is a left-most maximal p ±1 i -band C ′ of the comb ∆ containing a link π i from A, where p i is a control letter, i.e., the subcomb Γ of ∆ with handle C ′ has no links of A except for those on C ′ . But ∂π i has an a-edge from the left by (iii), and so two different a-edges of C ′ are connected by an a-band A j from the left of C ′ . We will assume that A j is the shortest a-band with this property, and so the (θ, q)-cells π 1 , . . . , π m situated on C ′ between π j−1 and π j (if any) are inside the subdiagram ∆ ′ bounded by the chain A. By Lemma 5.6 for ∆ ′ , these cells cannot have common edges with (θ, q)-cells which do not correspond to p ±1 i . Now it follows from (iv) that the cells π 1 , . . . , π m are active from both sides. Since the cells π j−1 and π j of the chain-annulus are also active from both sides, the existence of the a-band A j contradicts Property (vii). The lemma is proved.

An application of quasicombs
The surgery we use in Lemma 8.6 requires a slight modification of the notion of comb.
Let ∆ be a reduced diagram over M with boundary yz such that every maximal θ-band of ∆ has exactly one θ-edge from y. Assume that one can construct a q-band Q with a top or bottom path y 0 , and Lab(y) can be obtained from Lab(y 0 ) after deleting of some a-letters. Then we say that ∆ is a quasicomb with the support y. As for combs, we use the standard factorization yz = y ∆ z ∆ of the boundary path of a quasicomb. The number h = h ∆ is the θ-length |y| θ ; the notation [∆] is also extended to quasicombs as well as h − , and the κ-, λ-, µ-, and ν-mixtures.
In particular, every comb is a quasicomb. (Take Q to be the handle of the comb.) It follow from the definition that the history H of the quasicomb ∆ is the history of Q, and by Lemma 5.6, the boundary label of ∆ uniquely determines the end edges of all maximal θ-bands T 1 , . . . , T h starting on y. It is easy to see that the set of cells of T 1 is also uniquely determined by the boundary of ∆, and by induction, the same is true for T 2 , . . . , T h . Hence every quasicomb (in particular, every comb) is a minimal diagram. We say that a diagram ∆ admits a (proper) quasicomb Γ if it has a (proper) subcomb Γ 0 such that Lab(z Γ ) ≡ Lab(z Γ 0 ), the handle of Γ 0 serves for Γ as Q in the definition of quasicomb, and the words Lab(y Γ ) and Lab(y Γ 0 ) are equal modulo (θ, a)-relations. In particular, every subcomb of ∆ is admitted. Lemma 8.6. Let ∆ be a comb with history of type (2). Assume that ∆ has a subcomb Γ 0 of base width ≤ 3 with a s ±1 j -handle C ′ such that the filling trapezium T p(C ′ , C) is not aligned. Also assume that all maximal q-bands of Γ 0 except for C ′ , are p ±1 -bands. Then ∆ admits a proper quasicomb Γ such that Area(Γ) ≤ 5(δ ′ ) −1 [Γ].
Proof. By Property (xiii), Lab(y Γ 0 ) has a factorization of the form is an a-letter or 1 (i = 1, . . . , m) , v i is a group word in θ-letters, b i commutes with every letter of v i by virtue of (θ, a)-relations, and each of u, w has at most one a-letter. Similar property holds for Lab(y ′ Γ 0 ). Hence one can separate the band C ′ from the diagram Γ 0 and attach several (θ, a)-cells to the left and to the right sides of it, and obtain an auxiliary subdiagram E with the boundary exf x ′ whose label 'almost' equal to the boundary label of C ′ , but Lab(x) (resp., Lab(x ′ )) are obtained from Lab(y Γ 0 ) (from Lab(y ′Γ 0 )) by deleting of the a-letters b ±1 i -s, and therefore each of x and x ′ has at most 2 a-edges.
Then we continue the surgery as follows. We can construct the mirror copies of the (θ, a)-cells attached to y ′Γ 0 in E, and attach these copies to the diagram Γ 0 \C ′ to obtain (after possible cancellations of some (θ, a)-cells) a reduced quasicomb E ′ whose support can be denoted by x ′ since its label is Lab(x ′ ), and the boundary of E ′ is x ′ (z ′ ) Γ 0 . Finally, we identify E ′ and E along x ′ and (after possible cancellations of (θ, a)-cells) we have a desired quasicomb Γ with support x. Now, to estimate the area of the minimal diagram Γ from above it suffices to estimate Area(E ′ ) (and use Lemma 5.2) since obviously Area(E) ≤ 3(Area(C ′ )) ≤ 3h.
Since the path x has at most 2 a-edges we obtain 8.15) by the definition of the length of a path. Note that at most two non-trivial chains of E ′ can start/end on x ′ since |x ′ | a ≤ 2. Consequently, by Lemma 8.3 (and Remark 8.5) , every θ-band of E ′ has at most 18 cells belonging to such chains.
Let d be the maximal number of a-cells in θ-bands of E ′ . Taking into account the argument of the previous paragraph and the lack of chain-annuli in E ′ , we conclude that there are at least (d − 18)/9 maximal chains having both ends on (z ′ ) Γ 0 . Now it follows from Lemma 5.20 and Inequality (8.15) that because δ ′ ≤ 1/7. This implies d + 2 ≤ 5(δ ′ ) −1 (|z Γ | − |x| − 1), and since every θ-band of E ′ has at most 2 p-cells, we have, as required: Lemma 8.7. Let ∆ be a comb with base width b ≥ N. Assume that ∆ has a one-Step history and has no active k-or k ′ -cells. Then ∆ admits a proper quasicomb Γ such that Proof. We first assume that the history of ∆ is of type (2). It follows from the conditions of the lemma and (ii) that ∆ cannot have k-or k ′ -cells at all, with the possible exception for the cells of the first and the last (12) ±1 or (23) ±1 -bands. By Lemma 7.20, we may also assume that the base of any θ-band of ∆ does not have subword (pp −1 p) ±1 , where p ±1 is any control letter. Therefore a left-most maximal s ±1 i -, k ±1 -, (k ′ ) ±1 -, t ±1 -, or (t ′ ) ±1 -band C ′ of ∆ is a handle of a subcomb Γ of base width b Γ ≤ 3 and all other q-bands of Γ (if any exist) correspond to the same control letter p ±1 by (i). One may assume that C ′ has h ′ > (δ ′ ) −1 cells because otherwise Lemma 7.15 is applicable to the subcomb with handle C ′ .
The filling trapezium ∆ ′ = T p(C ′ , C) has height h ′ > (δ ′ ) −1 > 2, and therefore it has a maximal θ-band without k-or k ′ -cells. Hence the base of ∆ ′ has no k-or k ′ -letters. Since b ≥ N , ∆ ′ is of base width b ′ ≥ N − 2, but having no k-or k ′ -letters, the base of ∆ ′ is not aligned or has only t ±1 or (t ′ ) ±1 -letters by Remark 5.16. In the former case, we are done by Lemma 8.6. In the later case we may refer to Lemma 7.18 since there are no derivative p ±1 -bands for a t-band by Property (i).
If the history of ∆ is of type (1) or (3), then it follows from the absence of active k-and k ′ -cells in ∆ that all q-cells of ∆ are passive by Property (ii), and the statement follows from Lemma 7.18.

Combs with one-Step histories
In this section we obtain the estimates of the areas of one-Step combs. Lemmas 9.2,9.6,9.7 will be used in the next sections.
Lemma 9.1. Let Γ be a comb whose proper subcombs have no active k-or k ′ -cells and the handle C of Γ is passive from the left. Assume that Γ has one-Step history and admits no proper quasicombs ∆ such that Area(∆) ≤ 5(δ ′ ) −1 [∆]. Assume that Γ has at most L 0 odd maximal θ-bands for some L 0 . Then (a) C is also passive from the right, then Area(Γ) < 5(δ ′ ) −1 h(|z| − |y| + L 0 ); Proof. (a) By Lemma 8.7, we may assume that the base width b of Γ does not exceed N. By Lemma 7.20, we may assume that ∆ has no bands with p ±1 p ∓1 p ±1 in the base for arbitrary control letter p. By Lemma 8.3, every chain of Γ and every θ-band of Γ have at most 9 a-cells in common. We also use below that Γ has no chain-annuli by Lemma 8.4. At most 2(b − 1)L 0 non-trivial maximal chains can start/terminate on the odd θbands of Γ by (iii) (a) -(c). Let T be a θ-band of Γ having maximal number of a-cells d. Then among maximal chains crossing T , we have at least (d − 18(b − 1)L 0 )/9 chains with both ends on z ′ , and so |z ′ | a ≥ 2(d − 18(b − 1)L 0 )/9. Therefore by Lemma 5.20, Since C is passive from the right, we have |y| ≤ |y ′ |+2δ ′ and |z| = |z ′ |+2. Therefore |z| − |y| > |z ′ | − |y ′ | + 1, and so statement (a) implies (b) because Area(C) ≤ h.
Lemma 9.2. Let Γ be a one-Step comb of base width b ≤ 15N . Assume that its handle C is a t ±1 -or (t ′ ) ±1 -band. Then (1) Γ has a subcomb ∆ such that its handle C ∆ is passive from the right, and Proof. (1) We may assume that Γ has no t ±1 or (t ′ ) ±1 -bands except for C, since otherwise we obtain a smaller subcomb ∆, and ∆ also satisfies the assumptions of the lemma. In particular, the derivative bands C 1 , . . . , C s are all k −1 -or k ′ -bands by Property (i). Assume first that the history of Γ is of Step (1) or (3), and the derivative bands are not active from the right. Then either Γ has a maximal k-or (k ′ ) −1 -band C ′ active from the left and passive from the right (and there exists the left-most band with this property), or all its q-bands are passive by Properties (i) and (ii). In any case Lemma 7.18 (b) is applicable to a subcomb of Γ. Thus we may further assume that the history of Γ is of Step 2. Property (v) implies that the derivative bands of Γ are active from the right.
The sum of areas of derivative subcombs Γ 1 , . . . , Γ s is at most (60N h 2 i + 2αh i ) by Lemma 7.13, where α = |z| a . Hence by Property (vii) and Lemma 7.10, We also recall that by Lemma 7.10, (9.17) and the subsequent estimate for α that by the choice of c 1 , as required. Now assume that there is i 0 such that h i 0 > 2 j =i 0 h j . Then less than h i 0 /2 maximal a-bands starting on C i 0 end on other derivative bands, and we can refer to Lemma 7.17 (b). Therefore as required, since c 1 > (δ ′ ) −2 + 3(δ ′ ) −1 Thus the desired inequality is true in any case.
Let Γ be a comb with a handle C. Assume that Γ is a subcomb of (or can be embedded as a subcomb in) a larger combΓ with a handleC, and the filling trapezium is T p(C,C). Then the combΓ is called an extension of Γ. The extension is called regular if the base width of T p(C,C) is at least N. A comb Γ is called regular if there exists a regular extension of Γ. Recall that by definition of comb, every cell (of the handle) of a subcomb of Γ is connected with C by a θ-band. Therefore a subcomb of a regular comb is regular itself.
Remark 9.3. A regular comb is organized better than a random one because its history coincides with the history of the filling trapezium T p(C,C) having a sufficiently long base. Therefore this history is a subject of some restrictions imposed on trapezia by Proposition 5.17. Recall that by Lemma 5.10, the properties of trapezia reflect all the features of the computations executed by the machine M. In particular, the next lemma uses Property (xiv) based on the aperiodicity of the histories formulated in Lemma 4.29, which, in turn goes back to Lemmas 4.15 and 2.2(a).
Lemma 9.4. Let Γ be a one-Step regular comb, and the handle C of Γ active from the left k-or (k ′ ) −1 -band. Assume that Γ has neither t ±1 -nor (t ′ ) ±1 -bands and has no active from the left maximal k-or (k ′ ) −1 -bands except for C, and Γ admits no proper quasicomb Proof. Let C 1 , C 2 , . . . C s be the set of derivative subbands (connected with C by simple θ-bands). Since none of them is a t ±1 -or (t ′ ) ±1 -band, they must be k −1 -or k ′ -bands active from the right by (i). Moreover, since the derivative subcombs Γ 1 , . . . , Γ s has no k-or k ′ -cells active from the left, it is easy to see from Property (i) that Γ has no active k ±1 -or (k ′ ) ±1 -cells except for those belonging to C, C 1 , . . . , C s . By (vii)), every maximal a-band starting on C ends either on some C i or on z = z Γ . Besides, if T is a simple θ-band starting on C, then every maximal a-band starting on T ends either on one of the bands C, C 1 , . . . C s , or on z.
Assume that T is a simple θ-band of maximal length d among the simple θ-bands starting on C. Then the total number of cells in all simple θ-bands is at most dh.
Let T 1 and T 2 be top and bottom of T . Since no non-trivial a-band starts and ends on C, either no a-band A starting on T 1 (an having no cell from T ) ends on C or no a-band A starting on T 2 (and having no cells from T ) ends on C. We consider only the first variant.
If there are m maximal θ-bands above T , then at least d−1 maximal a-bands starting on T and m − 1 maximal a-bands starting on C end on at most m (q, θ)-cells of the derivative bands and on z. Therefore at least d − 2 of them end on z , and so |z| − |y| ≥ 2 + (d − 2)δ ′ by Lemma 5.20 (a). We set ∆ i = T p(C i , C) (i = 1, . . . , s; and d ≥ 2 if s > 0 since otherwise two neighbor k-or k ′ -cells of T form a non-reduced subdiagram). By Property ((xv)), Consider a regular extensionΓ of the comb Γ. LetC be a handle ofΓ and Π i = T p(C i ,C).
If the base of Π i is not aligned, and Γ i has an s ±1 j -band for some j, then it follows from Property (i) and Lemma 7.20 that Γ i satisfies the assumptions of Lemma 8.6, and we have a contradiction with the hypothesis of Lemma 9.4. Therefore Γ i has no s ±1 j -bands, and so, by Property (i), it has no maximal q-bands at all except for C i . Hence by Lemma 7.20 i | + 1) in standard notation, if the base of Π i is not aligned.
Assume that the base of Π i is aligned. It starts with k (or with (k ′ ) −1 ) and the second letter of base is not k −1 (not k ′ ) by Lemma 3.4. Therefore, by Property (i), the second letter is the copy of the first letter (or of the inverse of the last letter) of the standard base B of M 3 . Since the base of Π is aligned and its base width ≥ N > 2||B||, this base is large. Therefore if k i ≥ 3, then the w k i -part of Π has no odd θ-bands by ((xiv)), and so the number of maximal odd θ-bands is at most 1). Thus, in any case, the number L i of odd maximal θ-bands in Π i (and in Γ i ) is at most 3(d − 1). Using ). Since |y ′ i | = h i and |y| = h, the sum of these areas is at most 5(δ ′ ) −1 h(|z| − |y| + 3(d − 1)). Finally, and |z| − |y| ≥ 2 since y has no a-edges. Therefore and so by (9.21), Area(Γ) ≤ 16(δ ′ ) −2 [Γ], as required.
If Γ is a long quasicomb admitted by a minimal diagram ∆ with boundary path zz ′ (where z = z Γ ), then there exists a minimal diagram ∆ ′ with boundary label Lab(y −1 )Lab(z ′ ). It follows from Lemma 5.6 that if ∆ is a comb with handle C, and ∆ admits a proper quasicomb Γ, then ∆ ′ is also a comb with the same handle C but with fewer number of maximal q-bands than in ∆.
It is clear that Area(∆) ≤ Area(Γ) + Area(∆ ′ ) (or see Lemma 5.2). We also use notation ∆\Γ for such a 'compliment' ∆ ′ of Γ. Then all the statements of Lemma 7.3 hold if one replaces 'subcomb Γ' by 'admitted quasicomb Γ' in their formulations because the quasicomb Γ and the subcomb Γ 0 from the definition of admitted quasicomb have equal κ-, λ-, µ-, and ν-necklaces. Lemma 9.6. Let Γ be a one-Step regular comb of base width b ∈ [2N, 15N ]. Then Γ admits a long quasisubcomb ∆ such that Proof. For the beginning, we recall that every subcomb of a regular comb is regular. By Lemma 9.2 (and Lemma 7.5), one may assume that Γ has neither t-nor t ′ -cells. If Γ has a subcomb ∆ of base width ≥ N without active k ±1 -or (k ′ ) ±1 -cells, then one can apply Lemma 8.7 since c 1 ≥ 5(δ ′ ) −1 . Otherwise by (ii), there is a maximal, active from the left or from the right q-band C ′ corresponding to a k ±1 -or (k ′ ) ±1 -letter, such that the subcomb ∆ with handle C ′ has no other maximal active k ±1 -or (k ′ ) ±1 -bands and the base width of the filling trapezium T p(C ′ , C), is at least N since b ≥ 2N. If C ′ is active from the left, then the statement follows from Lemma 9.4. Otherwise C ′ is active from the right, and from the right of C ′ , there must be a maximal band C ′′ = C corresponding to k-or (k ′ ) −1 -letter which therefore is active from the left. (Recall that Γ has neither tnor t ′ -cells, and so such C ′′ exists by Property (i).) Lemma 9.4 is now applicable to the subcomb with handle C ′′ , and so Lemma 9.6 is proved in any case.
Lemma 9.7. Let Γ be a regular comb having history of type (1) or (3) and base width at most 15N. Assume that the handle C is a passive from the left k ±1 -or (k ′ ) ±1 -, or Proof. At first we will prove that either Γ admits a proper quasicomb ∆ such that By Lemma 9.2, we may assume that Γ has neither t ±1 -bands nor (t ′ ) ±1 -bands, and it also has neither k-bands nor (k ′ ) −1 -bands active from the left by Lemma 9.4. Therefore by Property (i), there are no active k ±1 -or (k ′ ) ±1 -cells except for those in C. Since the step history of Γ is (1) or (3), every other q-bands of Γ is passive by (ii) , and if there exist other q-bands, then we can find the desired subcomb ∆ by Lemma 7.18(b). If Γ has no maximal q-bands except for the handle C, then statement follows from Lemma 7.18(a).
To complete the proof, we will induct on the number of maximal q-bands in Γ, as in Lemma 9.2 (b). By the previous argument, we may assume that Γ admits a proper (quasi)subcomb ∆ satisfying (9.22), since otherwise there is nothing to prove. Now Γ is a union of ∆ and the 'compliment'∆ = Γ\∆ (see Remark 9.5) with the handle C. By the inductive hypothesis, Note that h∆ ≤ h. It follows that the sum of the first summands of (9.22) and (9.23) does not exceed c 1 h(|z ′ | − |y ′ | + 1). The sum of second summands of (9.22) and (9.23) does not exceed c 1 κ c 1,1 (Γ) by Lemma 7.3(c), and lemma is proved since Area ′ (Γ) = Area(∆) + Area ′ (∆).

Combs with incomplete sets of Steps
In this section, we analyze combs whose histories have no rules of one of the Steps (1) or (3), and the main goal is Lemma 10.6. Lemmas 10.5 and 10.6 utilize the λ-mixture, but unfortunately, this parameter can be negative for some other combs. Therefore first of all we have to bound it from below in terms of other 'quadratic' parameters of combs. Lemma 10.1. Let Γ be a comb whose handle C is either (a) a t ±1 -band or (b) a (t ′ ) ±1band. Respectively, let the history H of Γ, either (a) have rules (23) ±1 but no rules (12) ±1 or (b) have rules (12) ±1 but no rules (23) ±1 . Then Proof. We shall prove the variant (a) only. For this goal we consider the set T of maximal (23)-bands of Γ, which do not cross derivative bands of Γ, and so both their edges on y ′ Γ and on z Γ are labeled by the same θ-letter, and therefore they are non-special edges by the definition of λ c . (The set T may be empty.) Consider all (non-empty) maximal combs ∆ j (j = 1, . . . , r) in which Γ is separated by the bands of T. (The combs ∆ j -s do not contain the separating θ-bands from T.) Then because arbitrary two white beads which are not separated by a black one in z = z Γ or in y = y Γ belong to the boundary of some ∆ j since black beads are placed on q-edges and also on non-special θ-edges (and also, every bead of ∂∆ j is on z). Below we call an edge black (white) if its middle point is a black (white) bead. Therefore we will estimate λ c (∆ j ) for every j from below and then will use (10.24). Clearly, this number is at least −λ c (y(j)) (j = 1, . . . , r), where y(j) = y ∆ j . To give an upper bound for λ c (y(j)), we apply Lemma 6.2 (e) to y j and select an appropriate 'black' edge e j (if any exists) on y(j) such that y(j) = y 2 (j)e j y 1 (j) with m 1 (j) and m 2 (j) white beads on y 1 (j) and y 2 (j), respectively, and λ c (y(j)) ≤ 2m 1 (j)m 2 (j) (10.25) Since the path y has no q-edges, e j is a (23)-edge. Let T j be the maximal (23)-band of ∆ j containing the edge e j . By the choice of ∆ j , the θ-band T j crosses a derivative band C i(j) of Γ, and this derivative band is a k −1 -band by Properties (i) and (v). The Step history of C i(j) has no subwords (23) −1 (2)(23) by (viii) applied to the filling trapezium T p(C i(j) , C), and so the top or the bottom path of T j cuts the derivative band in two parts such that one of them is a k −1 -subband D j with Step history (2) (without the cell from T j ). We denote by d(j) the length of this subband. Every maximal θ-band crossing a derivative band, also crosses the handle of ∆ j , so we may assume that D j belongs to the union E j of the maximal θ-bands of Γ ending on the m 1 (j) white edges of z ∆ j , because one can interchange m 1 (j) and m 2 (j)) in (10.25), in particular, d(j) ≤ m 1 (j). We consider 3 cases.
(2) d(j) > m 1 (j)/2 and at least d(j)/2 maximal a-bands starting on D j end on derivative bands of Γ non-equal to C i(j) . Then j ∈ J 2 .
(3) d(j) > m 1 (j)/2 and less than d(j)/2 maximal a-bands starting on D j end on derivative bands non-equal to C i(j) . Then j ∈ J 3 .
Case (1). In this case, the end f of D j is a q-edge factorizing the path z = z ∆ j in a product z ′ f z ′′ , where z ′ has at least m 1 (j)/2 white θ-edges (the ends of maximal θ-bands from E j non-crossing D j ) and z ′′ has at least m 2 (j) white edges. Therefore m 2 (j)m 1 (j)/2 ≤ κ(z ∆ j ) = κ c (∆ j ). Hence by Inequality (10.25) and by Lemma 7.9 (a), Case (2). In this case, at least d(j)/2 a-bands connect C i(j) with a different derivative band. Therefore the number of a-bands connecting pairwise different derivative bands of Γ is at least 1 4 j∈J 2 d(j). On the other hand, the same number does not exceed h − = h Γ − by Lemma 7.7, whence j∈J 2 d(j) ≤ 4h − . Since m 1 (j) ≤ 2d(j), this inequality implies j∈J 2 m 1 (j) ≤ 8h − . Therefore by Lemma 7.7 and (10.25), we have Case (3). Since the Step history of the k −1 -band D j is (2), every cell of this band is active from the right by (ii), and so there are no a-bands starting and ending on the same D j by (vii). No a-band starting on D j can cross T j since there are no (θ, a)-cells between the intersection cells of T j with C j(i) and with C by (v). Thus in Case (3), more than d(j)/2 a-bands starting on D j end on ∂Γ. Therefore |z| a ≥ j∈J 3 d(j)/2 ≥ j∈J 3 m 1 (j)/4. Hence, by Lemma 7.10 (a),  Proof. Let ∆(i) be the H(i)-part of ∆, i = 1, 2, 3. We will abbreviate h(1) = h ∆ (1) , and so on. By (ii), the handle C is passive from the left, and so by Lemma 9.7, (2)) (10.29) and therefore the statement is true if l = 0 since c 2 > c 1 + 1. Further we assume that l ≥ 1.
Since the base widths of ∆ does not exceed 15N, we have by Lemma 7.13, Let x 12 be the common part of the boundaries of ∆(1) and ∆(2). By Lemma 7.13, We also have |z ′ (2)| ≤ |z ′ | + |x 12 | + |x 23 | ≤ |z ′ | + 2α + 120N l by (10.32). Therefore Lemma 7.10 (a). Using this estimate we deduce from (10.29) and Lemma 7.9(b) that In turn, this inequality and (10.34) show that 123N ). The lemma is proved. Also assume that in case (a), C is a t ±1 -band, and in case (b), C is a (t ′ ) ±1 -band. Then Proof. Case (b): We consider the system of derivative bands C 1 , . . . , C s . As usual, Γ i is the derivative subcomb with handle C i . If a derivative band is a (t ′ ) ∓1 -band, then it must have a one-step history since the base of a (12)-band cannot contain subwords (t ′ ) ∓1 (t ′ ) ±1 by (v). By Lemma 9.2 (2) , this would contradict our assumption on long subcombs. Therefore all the derivative bands are k ′ -bands by (i). Let they have histories H 1 , . . . , H s , respectively. Then H i (i = 1, . . . , s) has no subwords of type (12)(2)(12) −1 by (viii) applied to the filling trapezium T p(C i , C) (a similar argument was used in Lemma 10.1).
Step (2) and H i (2) is of Step (1), where some of the factors can be empty. The lengths of the histories are denoted by h i and h i (j), j = 1, 2, 3.
To complete the proof, we observe that by Lemma 10.1, since c 3 ≥ 9(δ ′ ) −1 c 2 , and c 0 ≥ 42. Case (a) of the lemma is completely analogous.
Proof. Let us consider the maximal q-bands C and C 0 of ∆ corresponding to the distinguished letters p 1 and s −1 0 , resp., in the base of T . By Property (ix) for the trapezium T p(C, C 0 ), the history H of C has no subhistories of the form (12)(2)(12) −1 , It follows that H has type (2)(1)(2) (or a subword of (2)(1) (2)), in particular, H has at most two rules (12) ±1 ), and by (ix), all p 1 -cells corresponding to the rules of Step 2 are active from both sides in the subcomb Γ with handle C as well. Below the usual notation h, y, z, y ′ , z ′ will be used for Γ.
We consider the system of derivative bands C 1 , . . . , C s of Γ. Let they have histories H 1 , . . . , H s , respectively. Then (2) and H i (2) is of type (1), and some of the factors can be empty. The lengths of the histories are denoted by h i and h i (j), j = 1, 2, 3. As usual, Γ i is the derivative subcomb with handle C i .
Assume that C i is a derivative p −1 1 -band. Then H i has neither rules (12) ±1 nor rules of Step 1 by (v). Hence the history H i is one-Step (of Step 2) and moreover all p ±1 1 -bands of Γ i are active from both sides and all other q-bands of Γ i are passive by (vi). Therefore one can apply Lemma 7.18 (b) to the subcomb whose handle is a left-most maximal qband of Γ i which contradicts the assumption of the lemma about long subcombs. Hence, by (i), all the derivative bands are s 0 -bands. By the same argument and by Lemma 9.7, derivative subcombs cannot have one-Step histories. (Indeed, since the s 0 -band is passive by (ii), we have  (2) of Γ crosses a derivative s 0 -band (H(2) can be empty) and the H(1)-part Γ(1) has no derivative bands. Similarly, we have H ′′ ≡ H(4)H (5).
Thus H ≡ H(1) . . . H(5). Let h(1), . . . , h(5) be corresponding lengths of the histories (some of them may be zero), Γ(i) (i = 1, . . . , 5) be the corresponding parts of Γ (some of them may be empty) with handles C(i), and z = z(5) . . . z(1), where z(i) is the common part of z and ∂Γ(i). Note that if the maximal (12)-band T separating Γ(3) and Γ (2) is not crossed by a derivative band, then by (v), T has no cells except for the intersection cell with the handle, and so the boundaries of Γ(3) and Γ(2) have no common edges except for that in C. Similar note is true for the combs Γ(3) and Γ (4).
Lemma 10.5. Let Γ be a regular comb of base width b ≤ 15N . Assume that it has no maximal t ±1 -, (t ′ ) ±1 -bands except for the handle C, and C is either (a) a (t ′ ) ±1 -band or (b) a t ±1 -band. Also assume that there are no special θ-edges in any derivative subcomb. Let Γ in case (a), have (23) ±1 -bands but have no (12) ±1 -bands, and in case (b), it has (12) ±1 -bands but has no (23) ±1 -bands. Then Proof. We will consider the case (b) only. Observe that the (12)-cells of the t ±1 -band C are special, and so λ(y) = 0. Let C 1 , . . . , C s be the system of derivative bands of Γ. It follows from (i) and the assumptions of the lemma that all of them must be k −1 -bands. First assume that a derivative band C i is of length Lemma 7.15. Since the statement of the lemma can by induction be assumed true for the comb Γ\Γ i , this implies that the statement is true for Γ since µ c (Γ) ≥ µ c (Γ\Γ i ) ≥ 0 and [Γ] = [Γ i ] + [Γ\Γ i ]. Thus we may assume further that h i > 1 for every i. Case 1. There is no derivative band whose length h i 0 is at least 0.8 s i=1 h i . Then Lemma 7.5. By Lemmas 7.13 and 7.10 (a), , and therefore by Lemma 7.9, (Here we assume that the total some of lengths of short derivatives h ′ is at least h i /3 because h i > 1 for every i.) Then, by (ii) and (vii), at least h ′ j /3 a-bands starting on C ′ j must end on z. Therefore by Lemmas 7.13 and 7.10 (a)" h i . Hence by Lemmas 7.13 and 7.6 , Thus, in any case By Lemmas 7.12,7.5,and 7.6, the number of cells in all simple bands of Γ does not exceed The two upper bounds (10.51) and ( Proof. Here we consider case (a) only. If Γ has a (t ′ ) ±1 -band, the statement follows from Lemma 10.3 provided this band crosses a maximal (12)-band, and it follows from Lemma 9.2 (2) otherwise since λ takes non-negative values on one-Step combs and every subcomb with (passive) (t ′ ) ±1 -handle is long. We may therefore assume that Γ has no such bands. Assume Γ has a left-most maximal t ±1 -band B. If B does not have (12)-cells, then again the statement follows from Lemma 9.2 (2). So we assume further that B has (12)-cells.
Let ∆ be the subcomb with the handle B. If there are no special θ-edges from the left of each derivative band of ∆, then the statement follows from Lemma 10.5 since c 3 > (δ ′ ) −2 . Therefore we may assume that ∆ has a maximal (12)-band T crossing a derivative band B i of B and having a special θ-edge from the left of B i .
Note that B i is a k −1 -band by the choice of B and by (i). Since only t-bands and k ±1 -bands can have special (12)-edges (and k −1 -band can have them from the right only), it follows that T has a k-cell from the left of B i . Since Γ has no (t ′ )-cells, the base of T is not aligned between the letter k and the next letter k −1 by (i). Moreover it has a subword p 1 p −1 1 s −1 0 between the k-and k −1 -letters by (v). So the statement of the lemma follows from Lemma 10.4. (Again, we take into account that λ is non-negative on one-Step combs.) Thus we may further assume that Γ has no t-cells.
By Lemma 9.6, one may assume that Γ has no one-Step subcombs of base width > 2N. Since b ≥ 3N, this implies the existence of a (12)-band T with base B 0 of length ≥ N. Since N > 2||B|| and B 0 has neither t-nor t ′ -letters, it must have at least two subwords of the form q ±1 q ∓1 for some base letter q (see (i)). But the existence of s −1 1 s 1 excludes the possibility of all other subwords q ±1 q ∓1 by (v), and also by (v), the existence of k −1 k implies the existence of at least one subword s 0 p 1 p −1 1 s −1 0 . Thus in any case B must have a subword p 1 p −1 1 s −1 0 , which finishes the proof as in the previous paragraph.

Combs with multi-Step histories
In this section, we allow all three Steps in comb histories. Although Lemma 11.8 gives no estimate of the area if the size of a comb is close, in a sense, to one of the numbers T i -s, this lemma (together with the lemmas of the next section) will imply that the Dehn functions of the groups M and G are almost quadratic because the set of T i -s has infinitely many very long gaps. Again, to obtain upper estimates of areas for various combs one should apply a skillful combination of a number of quadratic parameter. For example, Lemma 11.3 (and also Lemma 12.9 in the next Section) shows the use of the ν-mixture.
Let H be the history of a comb Γ. Consider a factorization H ≡ H(1) . . . H(m), where no two non-empty factors are separated by empty ones. We say that this factorization is firm if for every i = 1, . . . , m − 1, (a) for non-empty H i and H i+1 , the last letter of H i and the first letter of H i+1 must belong to different Steps; so one of these two letters is (12) (2)). Assume that the handle C of Γ is a t ±1 -or (t ′ ) ±1 -band, and the (1) − (2) transition band has no (θ, a)-cells between C and the derivative band crossing this transition band, and the H(2)-part (resp., the H(3)-part) of Γ has passive k-or k ′cells only in the (12)or in the (23)-bands. Then provided h (2) Proof. We will prove the lemma assuming that h(2) ≥ 3h (3) and h(2) ≥ 0.01h (> 0) since the proof of the second version of the lemma is similar.
Assume first that T belongs to the H(1)-part of Γ. Then one of the two ends of the derivative band C u+1 lies above T but there are at least 0.1h(2) θ-bands above this end since g ≤ 0.9h (2). Therefore by Lemma 6.2 (d), Then assume that T belongs to the H(2)H(3)-part of Γ. Then m 2 ≤ h(3) ≤ h(2)/3, since the one step history H(2) has no (12) ±1 -or (23) ±1 -rules. On the other hand, there is an (lower) end of the derivative C v+1 such that there are at least h(3) maximal θ-bands above it and at least 0.1h(2) below it since g ≤ 0.9h (2). Hence (2). This inequality and (11.55) (2), can be treated as the above subcase with g ≥ 0.9h (2), since now g = h(2).
We omit the proof of the following lemma since the argument would be just a simplified version of the proof given above for Lemma 11.1: instead of the inequalities h(3) ≥ 0.01h and h(3) ≥ 3h (2), below we have that h ′′ ≥ 0.7h (and so h ′′ ≥ 7 3 h ′ ) and H(1) is empty.
Lemma 11.2. . Let Γ be a comb of basic width b ≤ 15N with a t ±1 -or (t ′ ) ±1 -handle C, and let the history of Γ have a firm factorization H ≡ H ′ H ′′ , where h ′′ ≥ 0.7h and H ′′ is of Step (2). Let the derivative bands C i be all a k ±1 -or (k ′ ) ±1 -bands. Then Γ has a long subcomb ∆ with Area(∆) ≤ c 3 [∆] + c 2 µ c (∆). 11.56) Recall that ν c J (Γ) = ν J (z Γ ) by Lemma 7.2 (b). So we consider the two-colored string of beads responsible for the ν J -mixture of z Γ . Denote by o 1 and o 3 the black beads on the two ends of C and by o 2 , o ′ 2 the black beads on the two ends of C ′ . We have h ′ white beads between o 2 and o ′ 2 , a white beads between o 1 and o 2 and b white beads between o ′ 2 and o 3 for some a, b ≥ 0. Thus, a + h ′ + b = h. When we pass from z Γ to to z ∆ ′ , we delete at least two black beads o 2 , o ′ 2 . But the number of black beads between the vertices o 1 , o 3 is less than J. Hence we may apply Lemma 6.2,parts (d,c), and obtain that ν c This inequality and (11.60) complete the proof of the lemma since by the choice of c 3 , the definition of µ c (Γ), and by Lemma 7.2 (a).
Lemma 11.6. Let Γ be a regular comb of width b ≤ 15N whose handle is a t ±1 -band (or (t ′ ) ±1 -band) with firm factorization of the history H ≡ H(1) . . . H(5), where H (2) and H(4) are both of type (1) (or both of type (3), respectively), and h(2) + h(4) ≥ 0.9h. Assume that H(3) contains both (12) ±1 and (23) ±1 , and one of the derivative bands C i crosses all the maximal (12)-and (23)-bands of Γ. Then Γ has a long sumcomb ∆ with Proof. We will prove only the first version of the lemma. The history H i of C i contains H (3), and so it contains the rule (23) ±1 , and therefore the band C i cannot be a t ±1 -band; it is k −1 -band by (i). It follows from the assumption of the lemma that the derivative C i must cross H(2)-, H(3)-and H(4)-parts of the comb Γ, and therefore h i > 0.9h. Moreover the sum of lengths of H(2)-and H(4)-parts of C i is at least 0.9h, and so max(h(2), h(4)) ≥ 0.4h.
There are at most 0.1h maximal a-bands starting on C i and ending on other derivative bands. There are no a-bands starting on the H(2)-part and ending on the H(4)-part of C i by the condition on H (3), because an a-band cannot cross both (12)-and (23)-bands by (v). Besides both the H(2)-and the H(4)-part of C i are active from the right by (ii). Therefore we can apply Lemma 7.17 to Γ: (11.61) Note that at least 0.9h−4−0.1h = 0.8h−4 maximal a-bands end on z, and so |z|−|y|−2 = |z ′ | − |y ′ | ≥ (0.8h − 4)δ ′ by Lemma 7.10 (1), whence Hence by Lemma 6.2 (a) and Inequality (11.62), we get This inequality and (11.61) complete the proof as in Lemma 11.5 because Lemma 11.7. Let ∆ be a regular comb. Assume that history H ∆ has m ≤ 6 letters (12) ±1 and (23) ±1 , and max(4, 2m)N < b ≤ 15N for the base width b of ∆. Then either ∆ admits a long quasicomb ∆ ′ with Proof. If m ≤ 2 or the handle of ∆ does not contain either (12)-cells or (23)-cells, then the statement follows from Lemmas 9.6, 10.6, and 11.4 because λ c is non-negative for one Step (quasi)combs, the third summand in the above inequality is positive by Lemmas 7.2 (a) and 7.3 (d), and c 3 > c 2 > c 1 . Then we will induct on m assuming that 3 ≤ m ≤ 6 and that the history H ∆ of ∆ contains both rules (12) ±1 and (23) ±1 .
The comb ∆ has a regular subcomb ∆ 1 of base width b 1 > N (2m − 1) such that the base width of the filling trapezium T = T p(D 1 , D) is N + 1, where D 1 and D are the handles of ∆ 1 and ∆, respectively. If the history of ∆ 1 has m 1 letters (12) ±1 and (23) ±1 , and m 1 < m, then the statement of the lemma is a consequence of the inductive hypothesis since 2m 1 ≤ 2m − 1. Hence we may assume that m 1 = m. Similarly, ∆ 1 has a regular subcomb ∆ 2 of width b 2 > (2m − 2)N with handle D 2 and the filling trapezium T ′ = T p(D 2 , D 1 ) of width N + 1, and we may assume that m 2 = m 1 = m since otherwise 2m 2 ≤ 2m − 2 and one may apply the inductive conjecture to ∆ 2 .
Thus both D 1 and D 2 have (12)-and (23)-cells. Hence the base of T is normal by (xi), and so it contains a letter t ±1 and a letter (t ′ ) ±1 which are not the first letter in this base . The same is true for T ′ . Denote by C (C ′ ) a maximal t ±1 -band or (t ′ ) ±1 -band of ∆ crossing T (crossing T ′ ) and corresponding to this letter of the base. By Γ and Γ ′ , we denote the subcombs with handles C and C ′ , respectively. The histories of these handles are H and H ′ . We will assume that h ′ ≥ h/2 for their length, because otherwise one can apply Lemma 11.3 to Γ since c 1 < c 2 < c 3 .
Observe that there are derivative bands in both Γ and Γ ′ crossing all the θ-bands of Γ corresponding to the rules (12) ±1 and (23) ±1 . This follows from the equality of the numbers of (12)-and (23)-cells in D and D 2 . Hence such a derivative band is a k −1 or k ′ -band by (i) and (v), and there exist firm factorizations H = H (1) . . . H (m+1) and Besides one may assume that all other derivative bands of Γ and Γ ′ (if any) are also either k −1 -or k ′ -bands. Indeed, they do not cross (12)-and (23)-bands and so if a derivative band is t ± -or (t ′ ) −1 -band, one can apply Lemma 9.2 to a derivative diagram (2) /2. Hence Lemma 11.5 is applicable to Γ ′ , and the lemma is proved in Case 4.
The lemma is proved in any case.
Lemma 11.8. Let ∆ be a comb of base width b > 13N. Then either ∆ admits a long quasicomb Γ ′ with

Separation of a hub
In this section we consider minimal diagrams over the group G with cyclically reduced boundary paths. Thus in contrast to previous sections, we study diagrams with hubs.
For a clove Ψ = cl(π, B, B ′ ) in a diagram ∆, we denote by p(Ψ) the common subpath of ∂Ψ and ∂∆ starting with the q-edge of B and ending with the q-edge of B ′ . Lemma 12.2. Let Ψ = cl(π, B, B ′ ) be a clove in a solid diagram ∆. Then every maximal θ-band of Ψ crosses either B or B ′ ; the base width of any θ-band of Ψ is less than 2LN, and Area(Ψ) ≤ (2LN (h + h ′ ) + δ −1 |p(Ψ)|)(h + h ′ ), where h and h ′ are the lengths of the bands B and B ′ , respectively.
Proof. If the first claim were wrong, then one could find a rim θ-band which crosses neither B nor B ′ . Then by Lemma 12.1 (a), either first or the second condition in the definition of solid diagram would be violated, a contradiction. Thus the first statement of the lemma is proved, and Ψ has at most h + h ′ maximal θ-bands. Now we consider a maximal θ-band T in Ψ (T is not an annulus by Lemma 5.6). If its base width is at least 2LN , then there is a maximal q-band C intersecting T which does not start/end on the hub π because the number of spokes starting on the same hub cell is LN . Moreover, as in the proof of Lemma 12.1, one can select C so that C separates a comb of base width > (2LN − LN )/2 ≥ 15N from Ψ, contrary to the assumption that ∆ is solid. Thus, the base width of T is less than 2LN . Therefore the number of (θ, q)-cells in Ψ is at most 2LN × (h + h ′ ). Every (θ, q)-cell has at most two a-edges by (iii). Hence the number of maximal a-bands starting and ending on the (θ, q)-cells of Ψ (but not on ∂∆) is at most 2LN (h + h ′ ). Their lengths do not exceed h + h ′ by Lemma 5.6 since the number of maximal θ-bands in Ψ is at most h + h ′ . Thus the total area of these a-bands does not exceed 2LN (h + h ′ ) 2 . Arbitrary other maximal a-band and a maximal q-band of Ψ is also of length at most h + h ′ by the same reason, but it has at least one edge on p(Ψ). Therefore their total area is at most Lemma 5.20 (d). Since every cell of Ψ belongs to a θ-band, every (θ, a)-cell belongs to a-band and every maximal a-band starts and ends on a (θ, q)-cell or on ∂∆, the sum of these two inequalities gives the inequality from the lemma.
A clove cl(π, B, B ′ ) will be called a crescent if (1) it contains l ≥ L − 20 > L/2 consecutive t ±1 -spokes C 1 = B, C 2 , . . . C l = B ′ connecting ∂∆ and ∂π; (2) every maximal θ-band of this clove crosses either C 1 or C l ; moreover, either all maximal θ-bands of Ψ cross C 1 , or all of them cross C l , or there exists i, 2 ≤ i ≤ l − 2 such that the θ-bands crossing C l but not C 1 , do not cross C i , and the θ-bands crossing C 1 but not C l , do not cross C i+1 ; (3) every maximal (12)or (23)-band of Ψ crossing C 1 ( crossing C l ) also crosses C 2 (crosses C l−1 ), and every spoke of the clove is crossed by at most 3 (12)-or (23)-bands. Lemma 12.4. Assume a solid diagram ∆ has a hub. Then it contains a crescent Ψ = cl(π, C 1 , C l ) such that the cloves cl(π, C 2 , C l ) and cl(π, C 1 , C l−1 ) are also crescents.
(a) If a (12)-or (23)-band crosses B u but not B u+2 (B v but not B v−2 ), then we set . (b) Notice that either all maximal θ-bands of Ψ(0) cross B u or all of them cross B v , or there exists i (u ≤ i < v) such that the θ-bands crossing B v but not B u , do not cross B i , and the θ-bands crossing B u but not B v , do not cross B i+1 . If in the latter case i ≥ v − 2, then we set After a transition (a) or (b), we obtain a clove Ψ(1) = cl(π, B u ′ , B v ′ ) with v ′ − u ′ ≥ L − k ′ , where k ′ = k + 2. Let us start with u = 2 and v = L − 4 (i.e., k = 6) and apply a maximal series of transitions of type (a). Since every transition of type (a) removes a maximal (12)or (23)-band and the number of such bands in Ψ(0) is at most 6, the Without loss of generality, we will assume further that h 1 ≥ h l for Ψ. Under this assumption, we will use the following special surgery for ∆. Denote by e j the common t-edge of ∂C j and ∂π. Consider the reduced subpath e 2l−L−1 u ′ e l of s. Denote by Γ the subdiagram without hubs bounded by bot(C 2l−L−1 ) −1 (v)top(C l )(u ′ ) −1 , where v is a subpath of ∂∆. We have p(Ψ) = p = p 1 vf for some p 1 , where f is the common edge of ∂C l end ∂∆.
There is a reduced path e −1 1ū e −1 l , where (ū) −1 is a subpath of ∂π. Then the paths w 1 = top(C l )(u ′ ) −1 is obtained from w = bot(C l )ū −1 by a t i -reflection since C l is a t i -band for some i (see definitions in Remark 5.3). Therefore the following surgery is possible.
(3) Insert Π in the hole of ∆ obtained after step (1). (4) Cut up the obtained disc diagram along top(C 1 )r, and obtain two diagrams ∆ 1 and ∆ 2 , where ∆ 1 is a minimal diagram with the same boundary label as the union of Ψ, π and Γ 1 , and ∆ 2 is a union of Ψ ′ and Γ 2 .
(5) Let H 0 be the history of the maximal trapezium bounded by C 1 and C 2l−L−1 in Ψ (it is the filling trapezium T p(C 2l−L−1 , C 1 ) if every maximal θ-band crossing C 2l−L−1 also crosses C 1 ), and so H 0 is a suffix of both H 1 and H 2l−L−1 . Therefore 2h 0 = 2||H 0 || letters can be canceled in the product Lab(top(C 1 ))Lab(r). And so we shorten the corresponding part of the boundary of ∆ 2 by 2h 0 edges and replace the obtained diagram by a minimal diagram ∆ ′ .
Thus the boundary of ∆ ′ is p 3 p 2 , where p 3 = xv ′ , v ′ is obtained by the t i -reflection of v, and |x| = |x| θ = h 1 + h 2l−L−1 − 2h 0 . Since the path p 1 has at least (h 1 − h 0 ) + (h 2l−L+1 − h 0 ) θ-edges (the ends of maximal θ-bands which cross C 1 but do not cross C 2l−L−1 , and vice versa) and also has q-edges, we have |x| = |x| θ ≤ |p 1 | θ ≤ |p 1 | − 1 (12.69) Moreover using the maximal θ-bands crossing C 1 and C l in the crescent Ψ, one can for every θ-edges of x, find a θ-edge of p 1 corresponding to the same rule θ ±1 , and the obtaining mapping from the set of (non-oriented) edges of x to the set of edges of p 1 is injective.
The notation of this subsection will also be used in the next section.

Almost quadratic upper bound
We denote by g(n) the minimal function such that the height of any M 4 -accepting trapezium is at most g(n) if the a-length of its bottom label does not exceed n. (Such upper bounds exist for every n by Properties (xvii) and (xviii).) Since g(n) is non-decreasing, the auxiliary function f (n) = n(8g(δ −1 n 2 ) 2 + δ −1 n 3 ) used in this section is also nondecreasing. For the beginning of this section, we need a crude upper bound for areas of diagrams.
Step 2. In any case, the number of hubs n hub in ∆ is at most 2n/LN by Lemma 5.19. To complete the proof of the lemma, it suffices to assume that n hub ≥ 1 and to prove by induction on n hub that Area(∆) ≤ n hub (4LN g(δ −1 n 2 ) 2 + 6δ −1 n 3 ) + δ −1 n 3 /3 There are a hub π and a clove Ψ = cl(π, B, B ′ ) given by Lemma 5.18. Let Λ be the subdiagram of Ψ formed by the θ-bands of Ψ crossing both t-bands B = B 1 and B ′ = B L−3 . Let the remaining part Λ ′ = Ψ\Λ be separated from Λ by a path p(Λ).
Proof. By lemma 5.20, |∂∆| = n ≤ r ≤ δ −1 n. Recall also that by Lemma 6.1 (a) and the definition of µ-and ν J -mixtures, µ(∆) ≤ (c 0 + 1)r 2 , ν J (∆) ≤ Jr 2 , and also n Q ≤ n. Now the statement of the lemma follows with a constant C ≥ 2δ −1 c 7 from Lemma 13.2 and from the definitions of the function f. Proof. We consider only the Dehn function d(r) of the group G since a simpler proof works for M. (One considers only diagrams having no hubs in the later case.) Assume that an integer m satisfies the hypothesis of (xvii) and m is large enough, say m > max(T 1 , C 20 (log m) 40 ), where C is provided by Lemma 13.3. There is a maximal i such that T i−1 ≤ m. Since T i−1 is the height of a standard trapezium with some bottom W and any rule corresponding to this trapezium can decrease the length of the input sector at most by 1, we have |W | a ≤ T i−1 ≤ m, and so by (xvii) and the choice of i, we get exp T i−1 < m < T i , (13.87) It follows from (13.87) and the choice of m that CT 2 i−1 < m 1/20 . (13.88) Now, on the one hand, inequality n < m/7 implies g(n) ≤ 4 7 m + 3 log m < m < T i (13.89) by (xvii). On the other hand, by Property (xix), any value g(n) of the function g either belongs to some interval (T j , 9T j ) or g(n) ≤ 6n. By (13.89), we have j < i in the former case. Therefore if n < m/7, then in any case g(n) ≤ max(9T i−1 , 6n) ≤ max(9 log m, 6n) (13.90) Hence there is a constant D such that for every integer r such that r > 9 log m and Dr 5 ≤ m, we have Cr(g(Cr 2 ) 2 + Cr 3 ) < Dr 5 ≤ m < T i (13.91) Now by Inequalities (13.91), (13.87), (13.90), (13.88), and by Lemma 13.3, we have d(r) ≤ C(r 2 + rT i−1 g(CT 2 i−1 ) 2 + T 4 i−1 ) ≤ C(r 2 + r(log m)g(CT 2 i−1 ) 2 + T 4 i−1 ) ≤ C(r 2 + r(log m)(max(9 log m, 6m 1/20 )) 2 + (log m) 4 ) ≤ 2Cr 2 if Dr 5 ≤ m, and r > m 1/6 . Since the set of integers m satisfying the hypothesis of (xvii), is infinite by (xviii), we can find for almost every such m, an integer r satisfying inequalities Dr 5 ≤ m < r 6 , and so the inequality d(r) ≤ 2Cr 2 holds on an infinite set of integers r.
End of proofs of Theorems 1.1 and 1.3. Using the notation of Lemma 4.45, we consider a word V ≡ W (M ) for an arbitrary admissible input word W of the machine M 4 . Assume that V = 1 in the group G. Then there is a minimal diagram ∆ whose boundary path is labeled by V. Since every state letter from the vector of start states of M occurs in V exactly once, every maximal q-band of ∆ must end on a hub, and ∆ has m ≥ 1 hubs. On the other hand, m ≤ 1 by Lemma 5.19, since |V | q = LN by the definition of the standard base for the machine M. Thus ∆ has exactly one hub Π, and so every maximal q-band of ∆ connects the boundaries of Π and ∆. Since V has no θ-edges, by Lemma 5.6, every non-hub cell of ∆ belongs to a θ-annulus surrounding the hub Π. (The set of these annuli is not empty since V has no state letters of the hub relation.) Hence one can remove Π, make a radial cut, and construct a trapezium with base (4.6). By Lemma 5.10 (1), the computation of M corresponding to this trapezium accepts the word V, and therefore V ∈ X 5 by Lemma 4.45.
conclude that every maximal θ-band of ∆ is an annulus, and so, as at the "End of proofs" above, the boundary label of ∆ is of the form V ≡ W (M ) for some admissible input word of the machine M 4 . Therefore it suffices (by Lemma 5.10) to find an exponential upper bound for the accepting computations of M 4 with respect to the length ||W || of an input admissible word W . Such an upper bound (even a linear bound) is given by Lemma 4.38 if the length of the reduced computation of W does not belong to any interval (T i , 9T i ). The argument of that lemma works in other cases if the computation does not contain the standard computation of length T i , (i.e., the computation of n i in our situation). However the proof of Lemma 4.38 also shows that ||W || ≥ n i in the remaining cases. Therefore the length of the computation has the exponential upper bound 9T i ≤ 9 exp(c ′′ ||W ||), and the proof is complete since C >> c ′′ .
Remark 13.6. One can replace the exponential function by a multiexponential one or by many other functions with at least exponential growth in the formulation and in the proof of Theorem 13.5.
14 Appendix: A very sparse immune set By M.V.Sapir Let X be a recursively enumerable (r.e.) language in the binary alphabet recognized by a Turing machine M . If x ∈ X then the time of x (denoted time(x) or time M (x)) is, by definition, the minimal time of an accepting computation of M with input x. For any increasing function h : N → N, a real number m is called h-good for M if for every w ∈ X, ||w|| < m implies h(time(w)) < m. For every number n, the number of digits in n is denoted by ||n|| 2 . This number is roughly log 2 n. Since we are not using any other logarithms in Appendix, we shall omit 2 in log 2 . Similarly, we shall write exp x for 2 x .
The proof of the following theorem uses an idea communicated to the author by S.Yu. Podzorov. For every α > 0, let h α (n) = exp exp(αn). Theorem 14.1. There exists a Turing machine M 0 recognizing a r.e. non-recursive set X such that the set of all h α -good numbers for M 0 is infinite for all α > 0.
Proof. We use a recursive enumeration of all Turing machines from [8]. By Matiyasevich's solution of the 10th Hilbert problem [10], there exists a polynomial F (a, b, x 1 , ..., x s ) with integer coefficients such that a is recognized by the Turing machine number b if and only if F (a, b, x 1 , ..., x s ) = 0 for some natural numbers x 1 , ..., x s . We are going to use Gödel numeration of s-tuples of natural numbers. For every natural m let g(m) be the s-tuple having Gödel number m. Note that all coordinates of this tuple do not exceed m and the time to compute g(m) is linear in ||m|| 2 .
Note also that if ||a|| 2 , ||b|| 2 , ||x i || 2 ≤ n (i = 1, ..., s) then the time needed to compute F (a, b, x 1 , ..., x s ) in bounded by a polynomial in n depending only on F . Also the time to compute binary value of the exponent exp n (given n written in binary) is linear in n (and exponential in ||n|| 2 ).
The algorithm of enumerating elements in X involves auxiliary formulas for functions f m : {1, 2, ...} → {1, 2, ...}, and two sequences of numbers b(m), x(m), m = 0, 1, 2, .... polynomial in ||n|| 2 + ||b(n − 1)|| 2 . In addition of computing values of F , we also have to compute the numbers b(n ′ ) and the formulas for f n ′ (at most n times). The time of computing b(n ′ ) and f n ′ does not exceed the time of computing b(n − 1) and f n−1 . And those times can be bounded by a polynomial in ||b(n − 1)|| 2 . Recall that the time of recognizing r by M 0 is bounded by a constant times the time of counting r into X by M . Thus the total time of accepting r by the machine M 0 is bounded by cn c ||b(n − 1)|| c 2 + c for some constant c. Note that exp exp(cn c ||b(n − 1)|| c 2 + c) < exp exp exp(||b(n − 1)|| 2 ) < log b(n) (14.94) for almost all n. Also notice that since n is appropriate, by the definition of f n , there are no numbers r ′ ∈ X between r + 1 and b(n). Hence if r ∈ X and ||r|| 2 < log b(n) then exp exp(αtime(r)) < log b(n) by (14.94) (for all but finitely many n and some α).
Hence log b(n) is an h α -good number of M 0 for almost all n. Therefore the set of h α -good numbers for M 0 is infinite. Step history of a band 40 Step history of a computation 31 Step