Algorithms, combinations of

The name of several methods for constructing new algorithms (cf. Algorithm) from given algorithms.

As applied to normal algorithms (cf. Normal algorithm), the following combinations (compositions) are best known: normal composition ( $ \mathfrak B \circ \mathfrak A $) of two normal algorithms $ \mathfrak A $ and $ \mathfrak B $, normal union ( $ \mathfrak A \wedge \mathfrak B $) of two normal algorithms $ \mathfrak A $ and $ \mathfrak B $, normal branching ( $ \mathfrak A \mathbf Y \mathfrak B \mid \mathfrak C $) of two normal algorithms $ \mathfrak A $ and $ \mathfrak B $ controlled by a normal algorithm $ \mathfrak C $, and normal repetition $ \mathfrak A \rightarrow \mathfrak C $ of a normal algorithm $ \mathfrak A $ controlled by a normal algorithm $ \mathfrak C $. If $ \mathfrak A , \mathfrak B $ and $ \mathfrak C $ are normal algorithms in some alphabet $ A $, the above combinations are normal algorithms in a certain given extension of $ A $ and satisfy the following conditions: a) for any word $ P $ in $ A $, $ ( \mathfrak B \circ \mathfrak A) \lfloor P \rfloor \simeq \mathfrak B \lfloor \mathfrak A \lfloor P \rfloor \rfloor $ is true (the composition theorem); b) for any word $ P $ in $ A $, $ ( \mathfrak A \wedge \mathfrak B ) \lfloor P \rfloor \simeq \mathfrak A \lfloor P \rfloor \mathfrak B \lfloor P \rfloor $ is true (the union theorem); c) for any word $ P $ in $ A $

$$ ( \mathfrak A \mathbf Y \mathfrak B \mid \mathfrak C ) \lfloor P \rfloor \simeq \ \left \{ \ \begin{array}{ll} \mathfrak A \lfloor P \rfloor & \textrm{ if } \mathfrak C \lfloor P \rfloor = F , \\ \mathfrak B \lfloor P \rfloor & \textrm{ if } \mathfrak C \lfloor P \rfloor \neq F , \\ \end{array} \right .$$

moreover, if $ ( \mathfrak A \mathbf Y \mathfrak B \mid \mathfrak C ) \lfloor P \rfloor $ has been defined, then $ \mathfrak C \lfloor P \rfloor $ is defined as well (the branching theorem); d) for any words $ P $ and $ Q $ in $ A $, the graphic equality $ ( \mathfrak A {\stackrel{\circ}{=}} \mathfrak C ) \lfloor P \rfloor = Q $ is true if and only if it is possible to indicate a sequence of words $ P _ {0} \dots P _ {k} $( $ k \geq 1 $) over the alphabet $ A $ such that

$$ P _ {0} {\stackrel{\circ}{=}} P ,\ \ P _ {k} {\stackrel{\circ}{=}} Q , $$

$$ P _ {i} {\stackrel{\circ}{=}} \mathfrak A \lfloor P _ {i-1} \rfloor \ ( i = 1 \dots k ) , $$

$$ \mathfrak C \lfloor P _ {k} \rfloor {\stackrel{\circ}{\not=}} F \ ( i = 1 \dots k - 1 ) , $$

$$ \mathfrak C \lfloor P _ {k} \rfloor {\stackrel{\circ}{=}} F $$

(the repetition theorem). Similar theorems may also be obtained for Turing machines (cf. Turing machine). In the theory of recursive functions (cf. Recursive function), the combinations of these functions which are most frequently employed are those supplied by the substitution operator, the primitive recursion operator and the $ \mu $- operator.

Theorems on combinations of algorithms reveal an important feature of the existing formalizations of the general concept of an algorithm — to wit, their "closure" under the natural ways of combination of algorithms. This fact is one of the principal arguments in favour of the basic assumption about algorithms (the Church thesis). Theorems on compositions of algorithms are an important part of the general theory of algorithms. Having been demonstrated once, they make it possible to determine the realizability of complicated and cumbersome algorithms, without actually writing down their schemes.

Of major interest in the general theory of algorithms is the problem of synthesizing an arbitrary algorithm within some class of interest, using a pre-determined set of composition operators.

References

[1]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[3]	V.A. [V.A. Uspenskii] Ouspenski, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[4]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)

Comments

The standard terminology for the above composition operators is in the West: "sequential composition of algorithmssequential composition" , "non-deterministic choice of algorithmsnon-deterministic choice" , "if-then-else algorithmif-then-else" and the "while-loop algorithmwhile loop" , in order of appearance. A representative result of the type indicated is the characterization of the power of structured programming: Every flowchart can be expressed as a flowchart obtained by sequential composition, if-then-else and while, from simple assignment statements [a1].

References

[a1]	C. Böhm, G. Jacopini, "Flow diagrams, Turing machines and languages with only two formation rules" Comm. ACM , 9 (1966) pp. 366–371