=Paper=
{{Paper
|id=Vol-1231/short8
|storemode=property
|title=Logspace computability and regressive machines
|pdfUrl=https://ceur-ws.org/Vol-1231/short8.pdf
|volume=Vol-1231
|dblpUrl=https://dblp.org/rec/conf/ictcs/Mazzanti14
}}
==Logspace computability and regressive machines==
https://ceur-ws.org/Vol-1231/short8.pdf
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