View source for Algorithms, equivalence of

A [[Binary relation|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119001.png" />-place partial recursive functions. Two schemes which define functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119002.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119003.png" /> are called functionally equivalent if for any natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119004.png" /> the conditional equality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119005.png" /></td> </tr></table>

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, [[#References|[1]]]) that for any everywhere-defined computable operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119006.png" /> over recursive schemes it is possible to find a scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119007.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119008.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a0119009.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190011.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190012.png" /> has this property, while scheme <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190013.png" /> does not have it. The unsolvability of the relation of functional equivalence itself follows from this theorem.

b) Consider normal algorithms (cf. [[Normal algorithm|Normal algorithm]]) over a fixed alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190014.png" />. Two such algorithms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190016.png" /> are called equivalent with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190017.png" /> [[#References|[2]]] if for any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190018.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190019.png" /> the following condition is satisfied: If one of these algorithms converts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190020.png" /> to some word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190021.png" /> which is also contained in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190022.png" />, then the second algorithm also converts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190023.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190024.png" />. These algorithms are called completely equivalent with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190025.png" /> if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190026.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190027.png" /> the conditional equality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011900/a01190028.png" /></td> </tr></table>

is true. Both these relations are unsolvable.

c) Consider logical schemes of algorithms (Yanov schemes, [[#References|[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 [[#References|[3]]], [[#References|[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 [[#References|[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 [[#References|[3]]] to a large extent determined the general approach to the study of algorithmic equivalence.

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