The sunphficaUon and equivalence problems are examined for several classes of straightline programs.It is shown that the problems are unsolvable for all nontrivlal classes.For example, it is proved that there is no algorithm to determine if an arbRrary program using only the constructs x ,,--1, r ,-x + y, x ,,--x/y, where x/y ~s integer diwsion with truncation, computes the ftinction which has value l for all integer inputs.The result holds even if one considers only programs with three input variables which compute total 0/l-functions.Thus, under any criteria of smaplification, no algorithm exists for simphfymg such programs When x ,--x + y is replaced by x ~--x -y, the number of input variables can be reduced to two This ~s the best possible, since equivalence Is decidable for {x ~-1, x ~ x + y, x ,,-x --y, x ~ x *y, x ~--x/y}-programs wtth one input variable All the results translate directly to simdar results concermng arithmetic expressions.

Let $\mathbb{C}$ be the set of all straight-line programs with one input variable, x, using the following instruction set: $y \leftarrow 0$, $y \leftarrow 1$, $y \leftarrow y + w$, $y \leftarrow y - w$, $y \leftarrow y * w$, and $y \leftarrow \lfloor y/w \rfloor $. We show that two programs in $\mathbb{C}$ are equivalent over integer inputs if and only if they are equivalent on all inputs x such that $|x| \leqq 2^{2^{\lambda r^2 } } $ ($\lambda $ is a fixed positive constant and r is the maximum of the lengths of the programs). In contrast, we prove that the zero-equivalence problem (deciding whether a program outputs 0 for all inputs) is undecidable for programs with two input variables. An interesting corollary is the following: Let $\mathbb{N}$ be the set of natural numbers and f be any total one-to-one function from $\mathbb{N}$ onto $\mathbb{N} \times \mathbb{N}$ (f is called a pair generator. Such functions are useful in recursive function theory and computability theory.) Then f cannot be computed by any program in $\mathbb{C}$.

We consider a simple class of loop-free programs whose instruction repertoire consists of $x \leftarrow 0$, $x \leftarrow c$, $x \leftarrow cx$, $x \leftarrow x/c$, $x \leftarrow x + y$, $x \leftarrow x - y$, $\textbf{skip } l$, $\textbf{if } p(x,y)$$\textbf{then skip }l$, and $\textbf{halt}$. (x and y are integer variables, c is a positive integer, $x/c$ is integer division, l is a nonnegative integer, and $p(x,y)$ is a predicate of the form $x > y$, $x \geqq y$, $x = y$, $x \ne y$, $x \leqq y$, or $x < y$; $\textbf{skip }l$ causes the $(l + 1)$st instruction following the current instruction to be executed next.) We show that the equivalence problem for this class is decidable in $2^{\lambda N^2 } $ time ($N = $ sum of the sizes of the programs and $\lambda $ is a fixed positive constant). The bound cannot be reduced to a polynomial in N unless ${\text{P}} = {\text{NP}}$. In fact, we have the following rather surprising result: The equivalence problem for programs with one input variable (which also serves as the output variable) and one auxiliary variable using only instructions $x \leftarrow 2x$, $x\leftarrow x/2$, and $x \leftarrow x + y$ is NP-hard.

Let $\mathcal{F}$ be the smallest class of functions on the natural numbers containing the functions $U_i^n (x_1 , \cdots ,x_n ) = x_i $, $S(x) = x + 1$, $A(x,y) = x + y$, $D(x,y) = x \dot{-} y$, $C(x,y) = (1 \dot{-} y)x$, $T_k (x) = \lfloor x/k \rfloor $ and losed under composition. It is shown that $\mathcal{F}$ is exactly the class of functions definable by Presburger formulas. Moreover, for Presburger functions with finite output range, $A(x,y)$ and $C(x,y)$ can be deleted from the list of initial functions. Characterizations of $\mathcal{F}$ and its subclasses in terms of simple programs are also given. An example is the following: A function is in $\mathcal{F}$ if and only if it is computable by a program which contains only instructions of the form $x \leftarrow x + 1$, $x \leftarrow x \dot{-} 1$, $x \leftarrow y$, and $\textbf{do } x \cdots \textbf{ end}$, where $\textbf{do}$’s cannot be nested.

We look at several classes of straight-line programs and show that the equivalence problem is either undecidable or computationally intractable for all but the trivial classes. For example, there is no algorithm to determine if an arbitrary program (with positive, negative, or zero integer inputs) using only constructs x ← 1, x ← x + y, x ← x/y (integer division) outputs 0 for all inputs. The result holds even if we consider only programs which compute total 0/1 - functions. For programs using constructs x ← 0, x ← c, x ← cx, x ← x/c, x ← x + y, x ← x − y, skip l, if p(x) then skip l, and halt,1 the equivalence problem is decidable in [equation] time (λ is a fixed positive constant and N is the maximum of the sizes of the programs). The bound cannot be reduced to a polynomial in N unless P = NP. In fact, we prove the following rather surprising result: The equivalence problem for programs with one input/output variable and one intermediate variable using only constructs x ← x + y and x ← x/2 is NP-hard. We also show the decidability of the equivalence problem for a certain class of programs and use this result to prove the following: Let IN be the set of natural numbers and f be any total one-to-one function from IN onto IN × IN. (f is called a pair generator. Such functions are useful in recursive function and computability theory.) Then f cannot be computed by any program using only constructs x ← 0, x ← c, x ← x + y, x ← x − y, x ← x * y, x ← x/y, skip l, if p(x) then skip l, and halt.