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

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.

Основним напрямком дослідження є розробка наукових засад генезису рішень програмістських задач. Проведено побудови, що базуються на алгебраїчних методах дослідження програм та методах композиційного програмування. В основі останніх лежать програмні алгебри з функціями спеціального класу у якості носія, і композиціями, які представляють абстракції інструментів програмного синтезу, у якості операцій. У рамках так званих програмних алгебр строго поставлено та вирішено проблеми отримання характеристик репрезентативних класів обчислюваних функцій, проблеми знаходження породжуючих сукупностей та базисів, що займають одне з чільних місць у програмістській проблематиці. Запропоновано загальний метод вирішення згаданих проблем у примітивних програмних алгебрах (ППА) над різними класами обчислюваних функцій. Отримані результати викладено у вигляді низки оригінальних тверджень, лем та теорем. Вони можуть бути використані у ході дослідження алгебраїчних характеристик різних класів обчислюваних функцій в задачах формалізації семантик мов програмування.

Основным направлением исследования есть разработка научных основ генезиса решений программистских задач. Проведены построения, которые базируются на алгебраических методах исследования программ и методах композиционного программирования. В основе последних лежат программные алгебры с функциями специального класса в качестве носителя, и композициями, которые представляют абстракции инструментов программного синтеза, в качестве операций. В рамках так называемых программных алгебр строго поставлены и решены проблемы получения характеристик репрезентативных классов вычислимых функций, проблемы нахождения порождающих совокупностей и базисов, которые занимают одно из главных мест в программистской проблематике. Предложен общий метод решения упомянутых проблем в примитивных программных алгебрах (ППА) над разными классами вычислимых функций. Полученные результаты изложены в виде ряда оригинальных утверждений, лемм и теорем. Они могут быть использованы при исследовании алгебраических характеристик разных классов вычислимых функций в задачах формализации семантик языков программирования.