An analysis of the existing, intuitive computation models is presented, that is the virtual
machines of Turing, Post, Kolmogorov, Schönhage, Aho-Ullman-Hopcroft as well as the
algorithms of Markov and Krinitski, and the recursive functions. The need for tools of precise,
mathematical formulation and possible transformation of the algorithms is indicated.
Consequently, an algebra of algorithms is defined using the axiomatic method. The algebra is
based on the operations of sequencing, elimination, paralleling and inverting as well as cyclic
sequencing, cyclic elimination and cyclic paralleling, all of them performed on the so-called
uniterms.
1. Turing A. M.: On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of London Mathematical Society, series 2, vol. 42 (1936-1937), pp. 230-265; correction,
ibidem, vol. 43, pp. 544-546. Reprinted in [13 Davis M., pp. 155-222] and available online at
http://www.abelard.org/turpap2/tp2-ie.asp. 2. Kleene S.C.: Turing’s analysis of computability, and major
applications of it. In Rolf Herken, Editor, The universal Turing machine: A half-century story, Oxford
University Press, 1988, pp. 17-54. 3. Post E. L.: Finite Combinatory Processes — Formulation 1. Journal of
Symbolic Logic, 1, pp. 103-105, 1936. Reprinted in The Undecidable, pp. 289ff. 4. De Mol L.: Closing the
circle: an analysis of Emil Post’s early work. The Bulletin of Symbolic Logic, Vol. 12, Issue 02, June 2006,
pp. 267 — 289. 5. Kolmogorov A.N.: On the concept of algorithm (in Russian). Uspekhi Mat. Nauk 8:4
(1953), pp. 175-176; translated into English in Uspensky V.A., Semenov A.L.: Algorithms: Main Ideas and
Applications, Kluwer, 1993. 6. Kolmogorov A. N., Uspensky V.A.: On the definition of algorithm (in
Russian). Uspekhi Mat. Nauk 13:4 (1958), pp. 3-28; translated into English in AMS Translations 29
(1963), pp. 217-245. 7. Gurevich Y.: Kolmogorov machines and related issues. In G. Rozenberg and A.
Salomaa, Editors, Current Trends in Theoretical Computer Science, World Scientific, 1993, pp. 225-234;
originally in Bull. EATCS 35 (1988). 8. Schönhage A.: Universelle Turing Speicherung. In J. Dörr and G.
Hotz, Editors, Automatentheorie und Formale Sprachen, Bibliogr. Institut, Mannheim, 1970, pp. 369-383.
9. Schönhage A.: Storage modification machines. SIAM Journal on Computing, 9 (1980), pp. 490-508. 10.
Markov A.A.: Theory of algorithms (in Russian). Editions of Academy of Sciences of the USSR, vol. 38,
1951, pp. 176-189; translated into English in American Mathematical Society Translations, 1960, series 2,
15, pp. 1-14. 11. Markov A.A., Nagorny N.M.: The Theory of Algorithms (Mathematics and its
Applications). Springer, 2001. 12. Church A.: An unsolvable problem of elementary number theory.
American Journal of Mathematics, vol. 58 (1936), pp. 345-363. 13. Constable R.L., Smith S.F..
Computational foundations of basic recursive function theory. Theoretical Computer Science, 121, pp. 89-
112, Dec. 1993. 14. Sieg W. Step by recursive step: Church’s analysis of effective calculability. The
Bulletin of Symbolic Logic, 3:2 (1997), pp. 154-180. 15. Kleene S.C.: Origins of recursive function theory.
Annals of the History of Computing, 3:1 (January 1981), pp. 52-67. 16. Aho A.V, Hopcroft J.E, Ullman
J.D.: The design and analysis of computer algorithms. Addison-Wesley Publishing Company, 1974. 17.
Krinitski N.A.: Algorithms around us (in Russian). Mir, Moscow, 1988; also translated to Spanish
(Algoritmos a nuestro alrededor). 18. Uspensky V.A., Semenov A.L.: Algorithms: Main Ideas and
Applications. Kluwer, 1993. 19. Owsiak V., Owsiak A., Owsiak J.: Theory of Abstract Algorithms and
Mathematical Modelling of information systems (in Polish). Opole University of Technology Press, Opole,
Poland, 2005. 20. Ovsyak V.: Algebra of Algorithms. Modern problems in radio engineering,
telecommunications and computer science. Proceedings of the International Conference TCSET’2006.
February 28 — March 4, 2006. L’viv — Slavske, Ukraine. Pp. 66-67. 21. van den Dries L., Moschovakis
Y.N.: Is the Euclidean algorithm optimal among its peers? The Bulletin of Symbolic Logic, Vol. 10, No. 3
(Sep. 2004), pp. 390-418.