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 () of two normal algorithms
and
, normal union (
) of two normal algorithms
and
, normal branching (
) of two normal algorithms
and
controlled by a normal algorithm
, and normal repetition
of a normal algorithm
controlled by a normal algorithm
. If
and
are normal algorithms in some alphabet
, the above combinations are normal algorithms in a certain given extension of
and satisfy the following conditions: a) for any word
in
,
is true (the composition theorem); b) for any word
in
,
is true (the union theorem); c) for any word
in
![]() |
moreover, if has been defined, then
is defined as well (the branching theorem); d) for any words
and
in
, the graphic equality
is true if and only if it is possible to indicate a sequence of words
(
) over the alphabet
such that
![]() |
![]() |
![]() |
![]() |
(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 -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 |
Algorithms, combinations of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Algorithms,_combinations_of&oldid=45080