Primitive Programing Algebra of Computable Functions at Records




Fullness of calculable functions, Fullness problem in PPA, Complete system, Pairs of natural numbers, Pr-functions, Pr-predicates


Background. The research is conducted in the context of compositional approach to programming. Problematic of the research is development of scientific foundations of programmer’s problems solution genesis. Its basis is concept of composition.

Objective. The objective of the research is general method development for function classes’ algebraic characteristics obtaining and application of the method for description of pragmatically important class of partially recursive functions on records.

Methods. Creations made in the paper are based on software analysis algebraic methods and compositional programming methodic. Problems of computable functions’ characteristics obtaining, problems of generative sets and bases finding, which are one of the most important questions in programmer’s problematic, are strictly stated and solved in the context of so called “program algebras”.

Results. In the paper method of mentioned problems solution was proposed in context of primitive program algebras (PPA) on different classes of computable functions. Received results are stated as sequence of original statements, lemmas, and theorems. They can be used for different classes of computable functions algebraic characteristics exploration in problems of programming languages semantics formalization.

Conclusions. Received results are foundations of adaptive programming environments development. Next steps in this direction will be connected with exploration of general concept of composition and development of related reduction methods of function exploration as environments of pragmatic depended programmer’s problems decomposition.

Author Biographies

Тарас Леонідович Захарченко, NTUU "KPI"

Taras L. Zakharchenko,

postgraduate student at the Department of Design of Electronic Digital Equipment of the Faculty of Electronics

Дмитро Ігорович Редько, Taras Shevchenko National University of Kyiv

Dmitry I. Redko,

student at the Department of theory and technology of programming of the Faculty of Cybernetics

Ігор Володимирович Редько, NTUU "KPI"

Igor V. Redko

doctor of physics and mathematics, professor at the Department of Design of Electronic Digital Equipment of the Faculty of Electronics

Петро Олексійович Яганов, NTUU "KPI"

Petro O. Yaganov,

candidate of sciences (engineering), associate professor at the Department of Design of Electronic Digital Equipment of the Faculty of Electronics


E. Hehner, A Practical Theory of Programming.New York: Springer, 2012, 247 p.

B.E. Panchenko and V.N. Gajdabrus, “A relational framework and case shells of a new type”, Cybernetica i Sistemnyj Analiz, vol. 49, no. 3, pp. 475–486, 2013 (in Ukrainian).

D.J. Armstrong, “The quarks of object-oriented development”, Communications of the ACM, vol. 49, no. 2, pp. 123–128, 2006.

A.M. Grubiy, “Automaton implementations of the process of generating a Collatz sequence”, Cybernetica i Sistemnyj Analiz, vol. 48, no. 1, pp. 108–116, 2012, (in Ukrainian).

E. Dijkstra, A Discipline of Programming. Moscow, Russia: Mir, 1978, 275 p. (in Russian).

B. Stroustrup, Programming: Principles and Practice Using C++, 2nd ed. Moscow, Russia: Williams, 2011, p. 1248 (in Russian).

A. Tang et al., “What makes software design effective?”, Design Studies, vol. 31, no. 6, pp. 614–640, 2010.

D. Batory et al., “Dark knowledge and graph grammars in automated software design”, in Proc. 6th Int. Conf. Software Language Eng., Indianapolis, Oct. 26–28, 2013, vol. 8225, pp. 1–18.

N.S. Kovalenko et al., “Asynchronous distributed computations with a limited number of copies of a structured program resource”, Cybernetica i Sistemnyj Analiz, vol. 48, no. 1, pp. 86–98, 2012 (in Ukrainian).

F.P.Brooks, The Design of Design: Essays from a Computer Scientist. Moscow, Russia: Williams, 2012, 464 p. (in Russian).

I.A. Basarab et al., Compositional Databases. Kyiv, Ukraine: Lybid, 1992, 192 p. (in Russian).

V.N. Redko and I.V. Redko, “Existential foundations of the composition paradigm”, Cybernetica i Sistemnyj Analiz, vol. 44, no. 2, pp. 153–160, 2008 (in Russian).

D.B. Bui and I.V. Redko, “Primitive program algebras of functions, which preserve denotates”, Doklad AN USSR, no. 9, pp. 66–68, 1988 (in Russian).

Y.O. Bogatyryova, “Computability on finite sets and multi-sets”, Visnyk KNU im. Tarasa Shevchenka, no. 4, pp. 88–96, 2010 (in Ukrainian).

Y.O. Bogatyryova, “Concept of multi-set. Structure of multi-sets family”, in Proc 13th Academician M. Kravchuk Int. Sci. Conf, Kyiv, Ukraine, May 13–15, 2010, p. 60 (in Ukrainian).

A.I. Maltsev, Algorithms and Recursive Functions.Moscow,Russia: Nauka, 1965, 391 p. (in Russian).

A.I. Maltsev, Algorythmic Systems. Moscow, Russia: Nauka, 1970, 392 p. (in Russian).

A.I. Maltsev, “Constructive algebras. 1”, Uspekhi Mat. Nauk, no. 3, vol. 16, pp. 3–60, 1961 (in Russian).

A.V. Gorielov et al., “Compositional foundations of programming activity”, Visnyk KNUTD, no. 4, pp. 25–34, 2014 (in Russian).