Logspace computability and regressive machines Stefano Mazzanti Dipartimento di Culture del Progetto Università Iuav di Venezia Fondamenta delle Terese 2206, 30123 Venezia, Italy email: mazzanti@iuav.it Abstract. We consider the function class E generated by the constant functions, the projection functions, the predecessor function, the substi- tution operator, and the recursion on notation operator. Furthermore, we introduce regressive machines, i.e. register machines which have the division by 2 and the predecessor as basic operations. We show that E is the class of functions computable by regressive machines and that the sharply bounded functions of E coincide with the sharply bounded logspace computable functions. Keywords: recursion on notation, logspace computable functions. 1 Introduction One of the main features of logspace-algorithms is their incapacity to copy the whole input due to memory shortage, thus forcing them to read the data "on the fly", every time they are needed. This feature has been exploited in [3] where the set L of logspace computable predicates has been shown to be the set of predicates recognized by read-only while programs and in [4] where the closure with respect to substitution and simultaneous recursion on notation of the constant functions and the projection functions has been shown to contain the characteristic functions of the predicates in L. In this paper, we consider the class E of number theoretic functions defined as the closure with respect to substitution and (unbounded) recursion on notation of the predecessor function, the constant functions and the projection functions. We show that E is a subset of the logspace computable functions which contains all the sharply bounded logspace functions. Moreover, we show that E is the set of functions computable by regressive machines, a kind of register machines which have the division by 2 and the predecessor as basic operations on registers. Therefore, the present work can be considered an improvement of the char- acterization of L given in [4] because we use recursion on notation instead of simultaneous recursion and we characterize not only the {0, 1}-valued logspace functions, but also the sharply bounded logspace computable functions. 285 S.Mazzanti. Logspace computability and regressive machines 2 Preliminaries In this paper, we will only consider functions with finite arity on the set N = {0, 1, . . .} of natural numbers. From now on, we agree that x, y, z, i, j, n range over N, that a, b, c, k range over N − {0}, that x, y, z range over sequences (of fixed length) of natural numbers, that p, q range over integer polynomials with nonnegative coefficients and that f, g, h range over functions. A function f is a polynomial growth function iff there is a polynomial p such that |f (x)| ≤ p(|x|) for any x, where |x1 , . . . , xn | = |x1 |, . . . , |xn | and |x| = dlog2 (x + 1)e is the number of bits of the binary representation of x.1 Moreover, f is sharply bounded iff there is a polynomial p such that f (x) ≤ p(|x|) for any x, and f is regressive iff there is some constant k such that f (x) ≤ max(x, k) for any x, see [2]. We will use the following unary functions: the binary successor functions s0 : x 7→ 2x and s1 : x 7→ 2x + 1 ; the constant functions Cn : x 7→ n for any n ∈ N; the division by two function div2 : x 7→ bx/2c ; the remainder function rem2 : x 7→ x − 2bx/2c ; the length function len : x 7→ |x|. We will also use the following functions: the modified subtraction function sub : x, y 7→ x−̇y = max(x − y, 0); the predecessor function P : x 7→ x−̇1 = max(x − 1, 0); the bit function bit : x, y 7→ rem2 (bx/2y c); the smash function smash : x, y 7→ x#y = 2|x|·|y| ; the most significant part function MSP : x, y 7→ bx/2y c. Recall that bit(x, y) is the y-th bit of x and that M SP (x, y) is the number represented in binary by the |x|−̇y leftmost bits of x. Finally, we will use the substitution operator SUBST (g1 , . . . , gb , h) transforming functions g1 , . . . , gb : Na → N and function h : Nb → N into the function f : Na → N such that f (x) = h(g1 (x), . . . , gb (x)) and the recursion on notation operator RN (g, h0 , h1 ) transforming function g : Na → N and functions h0 : Na+2 → N and h1 : Na+2 → N into the function f : Na+1 → N such that f (0, y) = g(y) , f (si (x), y) = hi (x, y, f (x, y)) where i ∈ {0, 1}. Let E be the closure under substitution and recursion on nota- tion of the set comprehending the predecessor function P , the constant functions Cn for any n and the projection functions I a [i] : x1 , . . . , xa 7→ xi (1 ≤ i ≤ a) with any arity a. 3 Regressive machines Now, we introduce regressive machines, a kind of random access machines which have the division by 2 and the predecessor as basic operations. 1 Here, the notation |x1 , . . . , xn | is just an abbreviation for the sequence |x1 |, . . . , |xn |. However, |x1 , . . . , xn | is also interpreted as |x1 | + . . . + |xn |. 286 S.Mazzanti. Logspace computability and regressive machines A regressive machine operates on a finite number of variables (the registers) X1 , . . . , Xb and its program is built up according to the following rules:2 P ::= Xi := e|pred(Xi )|half(Xi )|P1 ; P2 |loop Xi do P end where instruction Xi := e sets the value of register Xi to the value of expression e, and e can be any natural number constant, any register, or the least signif- icant bit lsb(Xj ) of register Xj . Moreover, instructions pred(Xi ) and half(Xi ) compute the predecessor and (the quotient of) the division by 2 of Xi , respec- tively. Finally, the program loop Xi do P end executes |x| times program P, where x is the value held by Xi . From now on, we adopt the notation of [4], so that registers and programs are denoted by capital letters and we will write programs with the typewriter font. For any program P with b registers, a memory state of P is a sequence x = x1 , . . . , xb where xi is the value of Xi . Consider the function mP : Nb → Nb such that mP (x) is the state of P after the computation of P starting from state x. The following lemma states that regressive machines compute regressive functions and that they operate in polynomial time as long as instructions are executed sequentially and each operation is executed in constant time. Lemma 1. For any program P with b registers there is a constant c such that I b [i](mP (x)) ≤ max(x, c) for any 1 ≤ i ≤ b and there is a polynomial p such that the running time of P starting from memory state x is bounded by p(|x|). A program P with b registers computes a function f : Na → N with respect to input registers X1 , . . . , Xa and output register Xj iff for any x1 , . . . , xa the value f (x1 , . . . , xa ) is returned in register Xj when P is executed with Xi having initial value xi for 1 ≤ i ≤ a and all the other variables are initialized to zero. 4 Main results Let SB be the set of sharply bounded functions, let RM be the set of func- tions computable by regressive machines and let FL be the set of logspace computable functions. The following statement summarizes the relationships be- tween logspace functions, class E and regressive machines. Theorem 1. FL ∩ SB ⊆ E ⊆ RM ⊆ FL ∩ E. 2 The loop predecessor machines of [2] do not have either the assignment X:=lsb(Y) or the division instruction, and use the LOOP X DO P construct, which iterates x many times P, where x is the value held by X. In [3], counter machines with only decrement instructions have been considered, but the registers’ contents are bounded by the length of the input. 287 S.Mazzanti. Logspace computability and regressive machines Proof (Sketch). We first show that class E contains sharply bounded versions of the arithmetic operations (e.g. addp (x, y, z) = y + z for y, z ≤ p(|x|)) and is closed with respect to the sharply bounded maximization operator MAXp (g) transforming function g : Na+1 → N into the function f : Na → N such that f (x) = max{i ≤ p(|x|)|g(x, i) 6= 0} if {i ≤ p(|x|)|g(x, i) 6= 0} 6= ∅, otherwise f (x) = 0. Then, we set bitf (x, i) = bit(f (x), i) and show that bitf ∈ E for any f ∈ FL. The proof is carried out by induction on the characterization of FL given by Clote and Takeuti [1] which defines FL as the least function class closed with respect to substitution, concatenation recursion on notation and sharply bounded recursion on notation of the set comprehending the projection functions, the binary successor functions, the bit, the length and the smash functions. Then, the first inclusion of the theorem is true because for any g ∈ FL such that g(x) ≤ p(|x|) for some polynomial p, we have g(x) = max{y ≤ p(|x|)|∀i<|p(|x|)| bit(y, i) = bitg (x, i)} and the characteristic function of the predicate ∀i<|p(|x|)| bit(y, i) = bitg (x, i) is in E. The second inclusion can be easily obtained by showing (by induction on E) that for any function f ∈ E there is a regressive machine computing f . To show the third inclusion, we introduce counter machines and show that they simulate regressive machines using only a logarithmic amount of memory space. Then, counter machines can be easily simulated by functions in FL∩E and we obtain that RM ⊆ FL ∩ E. A counter machine operates on a finite number of read-only input registers and a finite number of read/write registers called counters. Input registers are denoted as Y1 , . . . , Ya and counters are denoted as Z1 , . . . , Zb for some a and b. Let y = y1 , . . . , ya be the input values and let z = z1 , . . . , zb be the values of the counters. A counter machine program is defined according to the following rules: Q ::= Zi := e|succ(Zi )|half(Zi )|Q1 ; Q2 |if (e1 = n) then Q1 else Q2 |loop Ei do Q1 end where e is any constant, any counter or lsb(Ej ), expression e1 can be Zi , bit(YZi , Zj ) or lsb(Zi ), and Ei is an expression whose value is ( zi+2 if zi = 0, ei (y, z) = (1 ≤ i ≤ b − 2). M SP (yzi , zi+1 )−̇zi+2 otherwise Furthermore, we define the function MQ : Na+b → Na such that (y, MQ (y, z)) is the memory state returned after the computation of a counter machine pro- gram Q starting from the state (y, z). Then, every regressive machine program P with b registers is simulated by a counter machine program Q with 3b registers. This means that for any x ∈ Nb , y ∈ Na and z ∈ N3b , if I b [i](x) = e3i−2 (y, z) for any 1 ≤ i ≤ b, then I b [i](mP (x)) = e3i−2 (y, MQ (y, z)) for any 1 ≤ i ≤ b. In other words, the value of register Xi of program P is represented by coun- ters Z3i−2 , Z3i−1 , Z3i of program Q so that e3i−2 (y, z) = xi . If Xi has been set 288 S.Mazzanti. Logspace computability and regressive machines to a constant value, then z3i−2 = 0 and z3i is the value of Xi . Otherwise, an input value has been assigned (or copied) to Xi and decrement or divi- sion instructions have been performed on it. In that case, the value of Xi is MSP (yz3i−2 , z3i−1 )−̇z3i (z3i−2 is the index of the input value, z3i−1 is the num- ber of divisions and z3i is less than or equal to the number of decrements). Then, pred(Xi ) is simulated by succ(Z3i ) (if Xi is positive) whereas half(Xi ) is sim- ulated by succ(Z3i−1 ); half(Z3i ) (Z3i could also be increased according to its parity and the value of bit(yz3i−2 , z3i−1 )). So, for any function f : Na → N computed by a regressive machine program P with b registers, there is a counter machine Q with 3b counters such that f (x) = e3j−2 (x, MQ (x, 1, 0, 0, . . . , a, 0, 0, . . . , 0)) where j is the index of the output register of P. Moreover, by Lemma 1 there is a polynomial p such that p(|x|) bounds all the counters at any step of the computation of Q. Therefore, we encode the counters with a single number cp (x, z) = z1 p(|x|)(3b−1) +. . .+z3b−1 p(|x|)+z3b < p(|x|)3b and we define functions ẽp,i , M̃p,Q : Na+1 → N belonging to FL ∩ E such that ẽp,i (x, cp (x, z)) = ei (x, z), M̃p,Q (x, cp (x, z)) = cp (MQ (x, z)) and f (x) = ẽp,3j−2 (x, M̃p,Q (x, cp (x, 1, 0, 0, . . . , a, 0, 0, . . . , 0))). Since cp ∈ FL ∩ E, we obtain that f ∈ FL ∩ E. From Theorem 1 we obtain immediately that E is a subset of logspace com- putable functions and coincides with the class of functions computable by re- gressive machines. Corollary 1. E = RM ⊆ FL. Moreover, by Theorem 1, we are also able to state that the sharply bounded logspace functions coincide with the sharply bounded functions in E. Corollary 2. FL ∩ SB = E ∩ SB. Finally, from the corollary above we obtain the following new characterization of L. Corollary 3. The characteristic functions of logspace predicates coincide with the {0, 1}-valued functions in E. References 1. P. Clote and G. Takeuti, First order bounded arithmetic and small boolean circuit complexity classes, in Feasible Mathematics II, Birkhäuser Boston, 1995. 2. P. C. Fischer, J. C. Warkentin, Predecessor Machines, J. Comput. System Sci. 8 (1974) 190-219. 3. N. D. Jones, LOGSPACE and PTIME characterized as programming languages, Theoret. Comput. Sci. 228 (1999) 151-174. 4. L. Kristiansen, Neat algebraic characterizations of LOGSPACE and LINSPACE, Comput. Complexity 14 (2005) 72–88. 289