View source for Algorithms, combinations of

<!--
a0118901.png
$#A+1 = 40 n = 0
$#C+1 = 40 : ~/encyclopedia/old_files/data/A011/A.0101890 Algorithms, combinations of
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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

As applied to normal algorithms (cf. [[Normal algorithm|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|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|Turing machine]]). In the theory of recursive functions (cf. [[Recursive function|Recursive function]]), the combinations of these functions which are most frequently employed are those supplied by the substitution operator, the primitive [[Recursion|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|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====
<table><TR><TD valign="top">[1]</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">[2]</TD> <TD valign="top">  S.C. Kleene,   "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.A. [V.A. Uspenskii] Ouspenski,   "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.I. Mal'tsev,   "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR></table>

====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 [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Böhm,   G. Jacopini,   "Flow diagrams, Turing machines and languages with only two formation rules"  ''Comm. ACM'' , '''9'''  (1966)  pp. 366–371</TD></TR></table>