Primitive programing algebra: general approach to a problem of functional completeness

Authors

  • P. O. Yahanov доцент кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Україна, Київ, Ukraine
  • D. I. Redko студент кафедри теорії та технології програмування Київського національного університету імені Тараса Шевченка, Україна, Київ, Ukraine
  • I. V. Redko професор кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Україна, Київ, Ukraine
  • T. L. Zakharchenko Захарченко Тарас Леонідович, аспірант кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Київ,

Abstract

The goal of the research is development of scientific foundations of programming problems solutions genesis. Investigations carried out are based on algebraic research methods of programs and compositional programming methods. Basis of the last ones consists of program algebras with special classes of functions as carriers, and compositions that represent abstractions from program synthesis tools as operations. Problems of completeness in classes of computable functions that took one of the most important places in programming problems are well defined and solved in the context of program algebras. Universal method for the problem of completeness solution in primitive program algebras (PPA) on different classes of computable functions proposed in the article. Results achieved are presented as series of original statements, lemmas and theorems. The results can be applied in algebraic characteristics research of different computable functions classes in problems of programming language semantics formalization.

Author Biographies

P. O. Yahanov, доцент кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Україна, Київ

Яганов Петро Олексійович,доцент, кандидат технічних наук, доцент кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Україна, Київ

D. I. Redko, студент кафедри теорії та технології програмування Київського національного університету імені Тараса Шевченка, Україна, Київ

Редько Дмитро Ігорович,

студент кафедри теорії та технології програмування Київського національного університету імені Тараса Шевченка, Україна, Київ

I. V. Redko, професор кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Україна, Київ

Редько Ігор Володимирович, професор, доктор фізико-математичних наук, професор кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Україна, Київ

T. L. Zakharchenko, Захарченко Тарас Леонідович, аспірант кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Київ

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

аспірант кафедри конструювання електронно-обчислювальної апаратури Національного технічного університету України "КПІ", Київ

References

Dijkstra E. A Discipline of Programming. — Prentice Hall, Inc., 1978. — 275 p.

Brooks F.P. The Design of Design: Essays from a Computer Scientist. — Addison-Wesley, 2010. — 448 p.

Brooks F.P. The Mythical Man-Month: Essays on Software Engineering. — Addison-Wesley, 1995. — 304 с.

Redko V.N. Fundamentals of compositional programming // Cybernetics and System Analysis. — 1979. — № 3. — P. 3–13.

Redko V.N. Semantical structures of software // Cybernetics and System Analysis. — 1981. — № 1. — P. 3–19.

Redko V.N. Universal program logics and their application // Proc. of 4th soviet-wide symp. — Kishenev, 1983. — P. 310–326.

Basarab I.A., Nikitchenko N.S., Redko V.N. Compositional databases. — K.: Lybid, 1992. — 92 p.

Redko I.V., Redko V.N. Existential basis of compositional paradigm // Programming and Computer Softtware. — 2008. — № 2. — P. 3–12.

Bui D.B., Redko V.N. Primitive program algebras І, ІІ // Cybernetics. – 1985. — № 1. — P. 28–33.

Bui D.B., Redko I.V. Primitive program algebras of computable functions // Cybernetics. — 1987. — № 3. — P. 68–74.

Bui D.B., Redko I.V. Primitive program algebras of functions, which preserve denotates // Report of Ukrainian AS. — 1988. — № 9. — P. 66–68.

Yershov U.L. Theory of numerations. — M.: Nauka, 1977. — 416 p.

Redko I.V., Snigur N.M. Primitive program algebra of computable functions on graph // Naukovi Visti NTUU "KPI". — 2011. — № 4. — P. 75–80.

Bogatyryova Y.O. Computability on finite sets and multi-sets // Taras Shevchenko Kiev Nation University bulletin. Ser.: phys.-math. Scienses. — 2010. — № 4. — P. 88–96.

Bogatyryova Y.O. Concept of multi-set. Structure of multi-sets family // Academitian M. Kravtchuk 13th international scientific conference, proceedings of (Kyiv, may 13–15, 2010). — K.: NTUU "KPI", 2009. — 60 p.

Maltsev A.I. Algorythmic systems. — M.: Nauka. — 1970. — 392 p.

Maltsev A.I. Constructive algebras. 1 // Uspekhi matematicheskih nauk. — 1961. — 6. — № 3. — P. 3–60.

Maltsev A.I. Algorithms and recursive functions // Groningen: Wolters-Noordhoff, 1970. — 391 p.

Cutland N. Computability. An introduction in recursive function. — M.: Mir, 1983. — 256 p.

Yershov A.P. Computability in arbitrary fields and bases // Semiotics and Informatics. — 1982. — № 19. — P. 3–58.

Maltsev A.I. Selected works // Mathematical logic and general theory of algebraic systems. — 1976. — 2. — M.: Nauka, 1976. — 388 p.

Downloads

Published

2015-12-15

Issue

Section

Mathematical methods, models, problems and technologies for complex systems research