Algorithms, equivalence of

A binary relation connecting algorithms of a fixed type and expressing the fact that any two algorithms thus connected yield the same results if fed with the same given type of inputs (and may also yield some additional information as regards the computations thus performed — the so-called history of the computation). A few typical examples of this connection are given below.

a) Consider all possible recursive schemes — i.e. systems of equations which define $n$-place partial recursive functions. Two schemes which define functions $\phi$ and $\psi$ are called functionally equivalent if for any natural numbers $x_1,\dots,x_n$ the conditional equality

$$\phi(x_1,\dots,x_n)\simeq\psi(x_1,\dots,x_n)$$

is true (it is considered to be true if both its sides are meaningful at the same time and, if meaningful, assume the same value). It was shown by S.C. Kleene (see, for example, [1]) that for any everywhere-defined computable operator $\mathfrak R$ over recursive schemes it is possible to find a scheme $S$ such that $S$ and $\mathfrak R(S)$ are functionally equivalent (the so-called fixed-point theorem). The consequence of this is, in particular, the Uspenskii–Rice theorem on the unsolvability of any property of recursive schemes which is invariant with respect to functional equivalence if there exist schemes $S_1$ and $S_2$ such that $S_1$ has this property, while scheme $S_2$ does not have it. The unsolvability of the relation of functional equivalence itself follows from this theorem.

b) Consider normal algorithms (cf. Normal algorithm) over a fixed alphabet $A$. Two such algorithms $\mathfrak A$ and $\mathfrak B$ are called equivalent with respect to $A$ [2] if for any word $P$ in $A$ the following condition is satisfied: If one of these algorithms converts $P$ to some word $Q$ which is also contained in the alphabet $A$, then the second algorithm also converts $P$ to $Q$. These algorithms are called completely equivalent with respect to $A$ if for any $P$ in $A$ the conditional equality

$$\mathfrak A(P)\simeq\mathfrak B(P)$$

is true. Both these relations are unsolvable.

c) Consider logical schemes of algorithms (Yanov schemes, [3]). The realization of such a scheme is a sequence of operators involved in its execution, from beginning to end. Two schemes are called equivalent if the sets of their realizations coincide. The equivalence relation of Yanov schemes proved to be solvable, and a complete system of equivalent transformations has been constructed for it [3], [4].

A detailed study of the relations of algorithmic equivalence is of major importance in the context of a number of tasks of current interest (especially in the theory of programming schemes), which can only be solved by advanced techniques of equivalent transformations of algorithms. Such problems include the translation of algorithms from one language to another and their optimization (transformations aimed at improving their "working characteristics"). Special attention is given in this connection [5] to finding solvable relations of algorithmic equivalence which would permit complete systems of equivalent transformations that are convenient with regard to their applications. The concept outlined in [3] to a large extent determined the general approach to the study of algorithmic equivalence.

References

[1]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[2]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[3]	Yu.I. Yanov, "On logical schemes of algorithms" Problemy Kibernet. , 1 (1958) pp. 75–127 (In Russian)
[4]	A.P. Ershov, "Operator algorithms III. (On Yanov operator schemes)" Problemy Kibernet. , 20 (1968) pp. 181–200 (In Russian)
[5]	A.P. Ershov, "The contemporary state of the theory of programming schemes" Problemy Kibernet. , 27 (1973) pp. 87–110 (In Russian)