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

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...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Yahanov, P.O., Redko, D.I., Redko, I.V., Zakharchenko, T.L.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2015
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Математичні методи, моделі, проблеми і технології дослідження складних систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/123561
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Primitive programing algebra: general approfch to a problem of functional completeness / P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko // Системні дослідження та інформаційні технології. — 2015. — № 4. — С. 83-96. — Бібліогр.: 21 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-123561
record_format	dspace
spelling	irk-123456789-1235612017-09-07T03:03:42Z Primitive programing algebra: general approfch to a problem of functional completeness Yahanov, P.O. Redko, D.I. Redko, I.V. Zakharchenko, T.L. Математичні методи, моделі, проблеми і технології дослідження складних систем 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. Основним напрямком дослідження є розробка наукових засад генезису рішень програмістських задач. Проведено побудови, що базуються на алгебраїчних методах дослідження програм та методах композиційного програмування. В основі останніх лежать програмні алгебри з функціями спеціального класу у якості носія, і композиціями, які представляють абстракції інструментів програмного синтезу, у якості операцій. У рамках так званих програмних алгебр строго поставлено та вирішено проблеми отримання характеристик репрезентативних класів обчислюваних функцій, проблеми знаходження породжуючих сукупностей та базисів, що займають одне з чільних місць у програмістській проблематиці. Запропоновано загальний метод вирішення згаданих проблем у примітивних програмних алгебрах (ППА) над різними класами обчислюваних функцій. Отримані результати викладено у вигляді низки оригінальних тверджень, лем та теорем. Вони можуть бути використані у ході дослідження алгебраїчних характеристик різних класів обчислюваних функцій в задачах формалізації семантик мов програмування. Основным направлением исследования есть разработка научных основ генезиса решений программистских задач. Проведены построения, которые базируются на алгебраических методах исследования программ и методах композиционного программирования. В основе последних лежат программные алгебры с функциями специального класса в качестве носителя, и композициями, которые представляют абстракции инструментов программного синтеза, в качестве операций. В рамках так называемых программных алгебр строго поставлены и решены проблемы получения характеристик репрезентативных классов вычислимых функций, проблемы нахождения порождающих совокупностей и базисов, которые занимают одно из главных мест в программистской проблематике. Предложен общий метод решения упомянутых проблем в примитивных программных алгебрах (ППА) над разными классами вычислимых функций. Полученные результаты изложены в виде ряда оригинальных утверждений, лемм и теорем. Они могут быть использованы при исследовании алгебраических характеристик разных классов вычислимых функций в задачах формализации семантик языков программирования. 2015 Article Primitive programing algebra: general approfch to a problem of functional completeness / P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko // Системні дослідження та інформаційні технології. — 2015. — № 4. — С. 83-96. — Бібліогр.: 21 назв. — англ. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/123561 519.683.8 en Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
topic	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем
spellingShingle	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем Yahanov, P.O. Redko, D.I. Redko, I.V. Zakharchenko, T.L. Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології
description	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.
format	Article
author	Yahanov, P.O. Redko, D.I. Redko, I.V. Zakharchenko, T.L.
author_facet	Yahanov, P.O. Redko, D.I. Redko, I.V. Zakharchenko, T.L.
author_sort	Yahanov, P.O.
title	Primitive programing algebra: general approfch to a problem of functional completeness
title_short	Primitive programing algebra: general approfch to a problem of functional completeness
title_full	Primitive programing algebra: general approfch to a problem of functional completeness
title_fullStr	Primitive programing algebra: general approfch to a problem of functional completeness
title_full_unstemmed	Primitive programing algebra: general approfch to a problem of functional completeness
title_sort	primitive programing algebra: general approfch to a problem of functional completeness
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2015
topic_facet	Математичні методи, моделі, проблеми і технології дослідження складних систем
url	http://dspace.nbuv.gov.ua/handle/123456789/123561
citation_txt	Primitive programing algebra: general approfch to a problem of functional completeness / P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko // Системні дослідження та інформаційні технології. — 2015. — № 4. — С. 83-96. — Бібліогр.: 21 назв. — англ.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT yahanovpo primitiveprogramingalgebrageneralapprofchtoaproblemoffunctionalcompleteness AT redkodi primitiveprogramingalgebrageneralapprofchtoaproblemoffunctionalcompleteness AT redkoiv primitiveprogramingalgebrageneralapprofchtoaproblemoffunctionalcompleteness AT zakharchenkotl primitiveprogramingalgebrageneralapprofchtoaproblemoffunctionalcompleteness
first_indexed	2025-07-08T23:52:48Z
last_indexed	2025-07-08T23:52:48Z
_version_	1837124832751255552
fulltext	 P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko, 2015 Системні дослідження та інформаційні технології, 2015, № 4 83 UDC 519.683.8 PRIMITIVE PROGRAMING ALGEBRA: GENERAL APPROFCH TO A PROBLEM OF FUNCTIONAL COMPLETENESS P.O. YAHANOV, D.I. REDKO, I.V. REDKO, T.L. ZAKHARCHENKO The goal of the research is development of scientific foundations of programming problems solutions genesis. Investigations carried out are based on algebraic re- search 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 opera- tions. 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 charac- teristics research of different computable functions classes in problems of program- ming language semantics formalization INTRODUCTION Today’s posture in IT field and, particularly, in programming, considerably de- fined by process of more and more vast it’s penetration in all aspects of human’s life. Naturally, with every step taken in that direction, requirements made to qual- ity of product produced and effectiveness of its production are constantly increas- ing. Despite of impressive and speaking for theirselves results achieved with pro- gramming activity (PA) today, it becomes more obvious that the results in majority are extensive, so sustainment of this tendency becomes more problem- atic and impossible in foreseeable future. The reason is typical for nowadays un- derstanding of PA, particularly, programming, its excessive simplicity, which is not corresponding level of complexity of problematic indicated. As for programming, simplicity of its understanding led to the fact, that, mainly, attention paid to results of programming without consideration of proc- esses, which made that results possible. It makes process of programming prob- lems solution too subjective, regarding intuitive principles of paramount impor- tance. These facts are not allowing us seriously discuss problems of software quality management, effectiveness of its production and preservation of invest- ments. An avalanche-like increase of number of such facts stimulated discussions about development of crisis in programming, depression in IT industry etc [1–3]. Now, not a crisis of the field should be discussed itself, but crisis of its ways of development! Statements, made above, one more time demonstrate that contem- porary programming, and the overall field can not effectively develop now exclu- sively on objectively-intuitive basis, which is the source of different concepts of PA. Long ago, problems of the field became so significant and so complex, that intuitive considerations must be objectified adequately and supplemented with precise researches and developments as far as possible. The matter is in the main P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 84 intuition carrier of PA — programming as process of software creation. Questions connected with revelation of programming languages semantic play here vital role. That is why research of following problematic is objective of the paper. Paramount role here plays compositional paradigm [4–8], as methodological con- sideration basis of whole diversity of general as well as particular software crea- tion methods. Namely that methods, to be more precise, their explications in the form of different classes of compositions build up the object of the research. The subject of the research is problem of computable functions characteristics classes creation. The functions are on different carriers in primitive programming alge- bras (PPAs) [9–11]. The main attention is paid to search of such algebra’s genera- tive sets and bases. In process of research, along with general results, description of computable functions class on records also received. It supplements analogical results for natural numbers tuples, graph transformers and multi-sets [10–15]. All undefined generic mathematical conceptions and designations are inter- preted in sense [16], and concepts of numerations theory and theory of algorithms interpreted as in [17, 18]. GENERAL STATEMENTS The carrier of PPA are n-ary functions and n-ary predicates (or simply functions and predicates) .),2,1( n The signature of PPA (denoted as  ) consists of superposition, branch, loop operations, which are represent adequate specifica- tions of the main methods of software or computational hardware design, which are peculiar to majority of high-level programming languages [1, 4–7, 9]. Let us make formal definitions of the operations. Termal, rather then operator notation of functions will be preferred for convenience and compactness [18]. Usage of spe- cific notation form in every individual case conditioned by the fact that different notations present fundamentally different viewpoints on the entity they describe. In other words, operator notation used in cases when it is important to reveal genesis of entity described, termal notation is important for description of result genesis. Although, those forms are interchangeable like texts in certain senses, those keypoints arrangement is important because it presents completely natural dominant of genesis relatively to its result. Let m functions mff ,...,1 of the same arity (for example, k ) of type BAk  be defined on certain set A with values from set B (it is no need to pre- serve  BA , moreover  BA is acceptable case too). Also, let m -ary function f with values in certain set C be defined on set B . Consider k -ary function CAg k : with value ),,...,((),...,( 111  kk aaffaag ))),...,(, 1  km aaf on argument  kaa ,...,1 . In this case function g is the result of a )1( m -ary superposition application, denoted as 1mS , to m -tuple of functions  mfff ,...,, 1 , i.e. ),...,,( 1 1   m m fffSg . Hereinafter in this document the designation “ ” means the generalized equality [19]. Now, additionally let function h of type BAk  and m -valued function },...,2,1{: mB  be defined. k -ary function BAg k : is built from func- Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології, 2015, № 4 85 tions mffh ,,, 1  by (m+1)-ary parametric branch operation 1m  if for any ar- gument k k Aaa  ,...,1 the value of function ),...,( 1  kaag defined as: ),...,(),...,( 11  krk aafaag , if ,)),...,(( 1 raah k  ( mr 1 ). Note, that described parametric branch operation represents adequate speci- fication of well-known method of software design — ._ ofcase Ternary branch operation  , which puts in correspondence to two functions 2,1 ,:  iBAf k i and one predicate },{: FTAp k  a k -ary function ),,( 21  ffpg with values defined on any argument k k Aaa  ,...,1 as:       Faapaaf Taapaaf aag kk kk k ),...,(),,...,( ),...,(),,...,( ),...,( 112 111 1 may be useful partial case. Finally, let us complete our list of definitions with k -ary predicate },{: FTAp k  . Consider k -ary function BAg k : with value ),...,( 1  kaag on arbitrary argument k k Aaa  ,...,1 equal to the first compo- nent of the first tuple from sequence of tuples ,...2,1,01 ],...,[  i i k i aa , where ,0 jj aa  kj ,...,2,1 and kjaafa i k i j i j ,...,2,1),,...,( 1 1  , for which (denote it as  s k s aa ,...,1 , for example) Faap s k s  ),...,( 1 in case if for all sr  , if such argument exists, value of Taap r k r  ),...,( 1 . Function g built by applica- tion of )1( m -loop operation to functions of )1( m -tuple  mffp ,,, 1  , i.e. ),,,( 1 1   m m ffpg  . Thus, according to statements made before, s k aaag 11 ),...,(  . Note, previously, in order to denote introduced operations, we used exclu- sively operator notation. By using termal notation of operations from PPA signa- ture, we will evidently denote only variables with considerably used values. For instance, for loop operation notation like     ,),,(*,, 1 1 1 11 1 1 m kyy m zzfxxp  ),,(, 1 k km k m zzf  will be used with those variables denoted, on which functions and predicate considerably depend. At the same time, function ),,( 1 j jm j j zzf  changes variable jy , kj ,...,2,1 and variable 1y considered as an “output”. Operator notation can be easily reconstructed from this notation. Let us declare certain countable set D and for any natural number 0k consider classes k of partial k -ary functions and predicates of types: DDk  and },{ FTDk  accordingly, and ...,3,2,1,  k k k of partial multiplace functions and predicates on set D . Further, functions and predicates on D will be denoted as D -functions ( D -predicates) and will belong to set  . Computability P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 86 on D is defined as numeric computability [17, 20]. PPA with carrier formed from partial recoursive functions (computable functions, pr-functions) and partial recoursive predicates (computable predicates, pr-predicates on D will be denoted as pr DA . Generative set of pr DA will be defined as its comlete system (CS). Complete system of PPA will be its n mI -basis, if any system produced by exclusion of any elements from the CS, except selective function, will not be complete. Some terms, designations, properties and associated results, showed below, may be useful during study of PPA complete systems [10]. Property 1. n -ary function f preserves set ,DL  L , if LLLf n  )(   . Here  nn n aaaafLLf ,...,\|),...,({)( 11  }  n LL  . Now, let D be set of composite objects (composed from certain compo- nents). Assume that universal set of such components is countable. Denote it as B . Lets declare surjective map BD 2:  , where B2 is set of all finite subsets of set B . Hence, for any Dd  Bd 2)(  is set of elements from ,B which d composed of. Those elements are called denotates of d . Property 2. n -ary function f  -preserves denotates, if finite set BB f  exists and for any fddd n dom,...,1  expression  )),...,(( 1 nddf fi n i Bd  )( 1=  is correct. Note that described properties of D -functions are preserved in signature  [10]. This allows to form several simple and essential conditions of completeness of pr DA CS [10]. Statement 1. Any complete system of pr DA contains at least one D -function that does not preserve set L for any non-empty set ) ,(  LDLL . Statement 2. Any complete system of pr DA contains at least one D -function, which does not  -preserve denotates. THE CONCEPT OF COMPLETENESS IN CLASSES OF PR-FUNCTIONS AND PR-PREDICATES Consider general method for PPA of D -functions and D -predicates complete systems finding. It will be represented by series of interconnected results, intro- duced as proved lemmas and theorems. First, let us define some notions, useful conventions and denotations. Let two countable sets 1D and 2D be defined. Assume that for every of those sets exists effective numeration 11 : DN  and 22 : DN  . Also, PPAs Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології, 2015, № 4 87 pr 1DA and pr 2DA are defined. Elements of sets 1D and 2D designated with lower- case letters: ,..., 11 ba and ,..., 22 ba , may be with subscript. Let complete system 1D of PPA pr 1DA is defined and injective constructive mappings 12: DD  and 21: DD  are given. Sets }\|)({)( 22 DddD   and  )( 1D }\|)({ 1Ddd  are recursive [18]. Consider approach to solution of complete- ness problem for algebraic structure pr 2DA . To designate 1D - and 2D -functions, lowercase ( ,..., gf ) and uppercase ( ,...,GF ) letters accordingly will be used. Letters ,...,rp and ...,, RP are used for designation of 1D - and 2D - predicates accordingly. When using termal notation, variables for 1D -functions and 1D -predicates are designated with lowercase ro- man letters ,...,, zyx , and 2D -function and 2D -predicates — with lowercase Greek letters ...,,,  , subscripts and superscripts may be used in both cases. Definition 1. )( 2D -function ),...,( 1 nxxf is 1D -image of 2D -function ),...,( 1 nF  , if for any 2 22 1 ...,, Daa n  expression ))(,...),(( 22 1 naaf  ))...,,(( 22 1 naaF is true. Definition 2. )( 2D -predicate ),...,( 1 nxxp is 1D -image of 2D -predicate ),...,( 1 nP  , if for any 2 22 1 ...,, Daa n  expression ))(...,),(( 22 1 naap  )...,,( 22 1 naaP is true. Lets show that relations «to be an image of function» and «to be an image of predicate», declared with definitions listed, preserve property of partial recursive- ness. In other words, listed theorem below is true. Theorem 1. 1D -image of 2D -pr-function ( 2D -pr-predicate) is 1D -pr- function ( 1D -pr-predicate). Indeed, it is easy to check that  , as mapping of numerated set  22 ,D to numerated set ))(()(,...2,1:)(:,),( 222222 kkkDND   is pr-equivalence ([21], p. 150–160), because of constructiveness of mapping  and effectiveness of numerations 1 and 2 . Hereinafter in this document the designation  2 means standard multiplication of functions 2 and  : )(dom)(dom 22   , )(ran)(ran 2   and for any )(dom 2  d value of this function )).(()( 22 dd   After application of theorem 2.1.5 [17], lemma 1 will be true. Lemma 1. 1D -image of 2D -pr-function ( 2D -pr-predicate) is )( 2D -pr- function ( )( 2D - pr-predicate). Hence, recursiveness of set )( 2D results. Lemma 2. Any )( 2D -pr-function is 1D -pr-function. The same for )( 2D - pr-predicates. This lemma results truth of theorem 1. P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 88 Definition 3. 2D -function ),...,( 1 nF  is 2D -model of 1D -function ),...,( 1 nxxf , if expression ))...,,(())(...,),(( 11 1 11 1 nn aafaaF  holds for any 1 11 1 ...,, Daa n  . 2D -model of 1D -predicate defined in the same way. Let  ( gf  is standard function multiplication, i.e. such function for which )(dom)(dom fgf  , )(ran)(ran ggf  and which any )(dom gfd  maps to value )),(()( dfgdgf  if )(dom)( gdf  ). Obvi- ously, that 2222 ))(()),((: DDDD   — bijection. Thus, it is possible to assume that mapping, which inverse mapping to  , exists. Some mapping ex- tension 22 1 ))((: DD   will be designated as 22: DD  . In other words, 2D -functions ψ and χ are playing roles of coding and decoding functions accord- ingly. Let 2D is designator for set of 2D -functions and 2D -predicates for which, firstly, 2D -model of 1D -function ( 1D -predicate) from CS 1D may be built from 2D -functions and 2D -predicates of set 2D by finite number of application of operations from signature  and, secondly, 2D -functions ψ and χ may be built from 2D -functions and 2D -predicates of 2D in analogical manner. Definition 4. Sextuple   ,,,,, 2121 DDDD is called allowable system (AS) and tuple  1 ,1 DD  is its basis. Obviously, that in context of coding and decoding function lemma 3 true. Lemma 3. Let ),...,( 1 nF  is D2-pr-function, and ),...,( 1 nH  is 2D -model of 1D -image of function ),...,( 1 nF  , then )...,,( 22 1 naaF )))(...,),((( 22 1 naaH  is true for any 2 22 1 ...,, Daa n  . Lemma 4. Let ),...,( 1 nP  be D2-pr-predicate, and ),...,( 1 nR  be 2D -model of 1D -image of predicate ),...,( 1 nP  , then )...,,( 22 1 naaP ))(...,),(( 22 1 naaR  is true for any 2 22 1 ...,, Daa n  . Hence, theorem 2 is true. Theorem 2. 2D is CS of PPA pr 2DA . Considered, that there are few as general as possible requirements to sets 21, DD and to its elements the nature of our constructions are maximally general. This allows to formulate simple, but effective condition of completeness of func- tions system in PPA. So, if  ,,,,, 2121 DDDD are objects, mentioned above, then theorem 3 is true. Theorem 3. If  ,,,,, 2121 DDDD is AS, then 2D is CS of PPA pr 2DA . Results gained are giving complete enough idea about building method of complete systems for PPA of partially recursive functions and predicates on countable sets. This method will be applied below in order to solve problem of PPA completeness in class of pr-functions and pr-predicates on pragmatically significant in programming data type — set of records. Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології, 2015, № 4 89 PPA OF PR-FUNCTIONS AND PR-PREDICATES ON SET OF RECORDS Number of different intuitive interpretations of term «record» exists in informa- tion technologies and programming. Despite the fact that some interpretations of «record» significantly differ one from another, all of them tend to use adequately a concept of named structures to describe complex aggregated entities. Often, those interpretations burdened with minor partial details, blurring significance of naming mechanisms. However, as experience shows, named structures form «common denominator», through which all other aspects of problems solved should be considered. Namely, this tendency is basis for all following construc- tions. Let V and W are non-empty countable sets of elements, interpreted as sets of names and values (denotates) accordingly. In general case it is allowed, that some names may play role of values and vice versa, i.e. it is possible that WV . We need to define some denotations, introduce main and auxiliary defini- tions in order to go further. Some of definitions will be given now, others — later, as may be necessary. All undefined terms and designations are given in [7]. One of the main concepts of this section is record. Set of all records on sets of names V and values W designated as ),( WVZ . Now, introduce definition of record. Definition 5. Record on sets of names V and values W (or simply record, it is clear from context what do V and W mean) is finite functional binary relation between set of names V and set of values W . To designate record uppercase letters ,...,, KJI will be used. Lowercase let- ters ,...,, wvu are used to designate names of record elements, letters ,...,,, dcba are their values and letters ,...,,  are elements of records. In all cases sub- scripts may be used. Left subscripts and (or) superscripts may be used to desig- nate names and (or) values of elements of record may be used. For example, let ),( av . Then such designations jf this element of record as v , a and va may be used, Hereinafter in the article so called «schemes», which represent name tem- plates of correspondent records, may be used along with records. Definition 6. The scheme of record K is finite set of names },...,{ 1 nvv , which represent projection of the record by the first component, i.e. )(pr},...,{ 11 Kvv n  , where ipr is function of projection by i -th component of m -ary relation ( mi 1 ) [7]. Scheme of the record I is designated as },...,{)( 1 nvvIsh  , and record itself named for compactness as )(Ish -record or record of )(Ish type. In case when type of record I must be defined explicitly, designation )(IshI will be used. Set of all records of },...,{ 1 nvv type designated as }],...,[{ 1 nvvZ . Couple particular cases of those notations take place: I and }{][  IZ . As follows from above, it is obvious that  VV WV VZZ 2 ),( ][   . P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 90 In unfolded notation record is designates as )}.,(),...,,{( 11 },...,{ 1 nn vv dvdvI n  For correct usage of numeric computability on set of records, it is required to prove existence of effective numeration of set ),( WVZ . Given the countability of sets ,, WV as well as the fact that in this case is not so much important form of presentation names and values, how important their fundamentally different role, without limitation of subsequent constructions generality, we can assume that .NWV  It can be deduced from a context which of the roles meant in every single case. Therefore, any further formal constructions will be carried out on set ,),( NNZ which is special case of .),( WVZ Few steps need to be done to construct the numeration. Firstly, we need to take in account that for any non-empty record )},(),...,,{( 11 mm dvdvI  its num- ber concur with number of finite set },...,{ 1 mI nnM  , where in is number of named element of record ),( ii dv (effective numeration of set 2N defined in [12]). Number (unique identifier) for set IM itself defined, for example, as   1 1 11 ...32 21     mjjj n m nn I pM , where mjjj nnn  ... 21 , ,Mn sj  ms ,...,1 , and ip , ...,2,1,0i is i -th prime number 2( 0 p , 31 p , 52 p , …). Than numeration ),( NNZ  of set ),( NNZ defined through piecewise scheme         ,else),( ,,1 ),( K Z M Iif KNN   where K is certain record. Namely, 1)( ),(),(  NNNN ZZ  . Now, consider to find of complete system of PPA pr ),( NNZ A itself. From the results gained above, conclusion followed that the solution of this problem re- duces to the corresponding AS construction. Refer to concept of multi-set, men- tioned in [14, 15]. Let U be some finite, may be empty, set. Definition 7. Multi-set  with U basis is finitely defined function of  NU: type, where ,...}3,2,1{}0{\  NN . If designation of  basis is necessary, notation U will be used. It would not be a great loss of generality, if we would assume that .NU  Collection of all multi-sets with basis U designated as UM . Then, obvious, that  NU UMM 2  is set of all multi-sets (on N ). Elements of set M are designated with lowercase Greek letters ,...,,  , may be with subscripts and superscripts. Element of multi-set will be designated as tuple  da, , every component of which may be with subscript and super- script. Here a as the first component of tuple, its argument, the second is d — value (denotate, multiplicity). Two terms are related to multi-sets for convenient: characteristics  and full image ][f . The first one is parametric function ND : with values defined with piecewise scheme: Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології, 2015, № 4 91      ,else,0 ,dom),( )(   aifa a for all Na . The second one is creates multi-set )(][ Uff  from multi-set U and given func- tion NNf : , where )(Uf is full image of set U relatively to function ,f and characteristics of arbitrary argument a of this multi-set defined as:       )(1 )( )( afa f aaUf   . Here )(1 af  is full image of element a relatively to function f . In case of empty set of summarands, sum assumed to be 0. Now consider PPA pr MA of M -pr-functions and M -pr-predicates. Follow- ing collection M of M -pr-functions and M -pr-predicates is of interest for us. It includes predicate of equality   : ))()(( aaNaa    ; function of unification All , which from two multi-sets  and  produces such multi-set  All , that for any argument a its characteristics equals to ))(),(max( aa   , i.e. ))(),((max)( aaa All    ; function of direct junction  , which from two arbitrary multi-sets U and U produces new multi-set   UUUU  )( , characteristics of arguments  21,aa defined as: Naaaaaa UU  212121 ,),()(),(    ; functions of addition  and subtraction  , defined with expressions ][   and   ][    accordingly (here «   » — truncated distinction [18, 19]); constant functions )}(1{ 1  and )(m , which produce multi-sets }1,1{  and  m accordingly; function of multiplicity  which produces from two multi-sets }1,{  n and }1,{  r multi-set },{  rn ; and selection functions n mI . The sig- nificance of collection M described above is in the truth of. Theorem (about multi-set PPA completeness). Collection M ,...3.,2,1 ,...,1 1 },,},1{,,,,{   n nm n mmAll I is complete system of PPA чр MA [14, 15]. The choice of multi-sets caused by relative simplicity of injective mappings MZ NN ),(: and ),(: NNZM  nature and obvious recursiveness of sets )( ),( NNZ and )(M . These facts are creating reliable basis for solution com- pleteness problem of PPA чр Z NNA ),( . Injective mapping of set of records to multi- sets MZ WV ),(: is defined as           . if , ,)},(),...,,{( if },1,,...1,,1,{ )( ),( 11 2211 K ZdvdvK dvdvdv K NN mm mm   Inverse mapping ),(: NNZM  is defined analogically P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 92          . if , ,},,...,,{ if )},1,),...(1,(),1,{( )( 11 2211   Mdada dadada mm mm Lemma 5. M -image of ),( NNZ -pr-function ( ),( NNZ -pr-predicate) is )( ),( NNZ -pr-function )(( ),( NNZ -pr-predicate). From the lemma 5 it can be concluded that any )( ),( NNZ -pr-function is M -pr-function. Analogical conclusion may be done for )( ),( NNZ -pr-predicates. Thus consequence 1 is true. Consequence 1. M -image of ),( NNZ -pr-function ( ),( NNZ -pr-predicate) is M -function ( M -predicate). Consider following ),( NNZ -pr-functions and ),( NNZ -pr-predicates with simple, but representative examples for some of them. Beforehand let us define auxiliary parametric operation of record projection },...,{ 1 kii vvpr , which maps any record ),( NNZI  to new record )},...,({)( 11 },...,{ NvvIIpr kkii iivv  . So, predicate of equality Z is analogical to predicate of equality for multi-sets; dele- tion by example Z : )(pr )(pr\)(pr 11 IJI JI Z  , particularly if  )(pr)(pr 11 JI  , then IJI Z  , for example:  (3,7)}(2,5),{(1,1),(5,7)}(2,10),{(1,3), Z {(5,7)} ; {(5,7)}(3,7)}{(6,5),{(5,7)} Z and {(6,5),(3,7)}{(6,5), Z 7)}(3, ; records overlapping  : for any ),(, NNZJI  JI )(pr )(pr\)(pr 11 IJ JI , particularly,   IJIIII ; , and in case if  )(pr)(pr 11 JI IJIJJI  , for example, {(1,1),(5,7)}{(1,3),  (5,7)}(3,7),(2,5),{(1,1),(3,7)}(2,5),  ; append to record  U :         ,)},0,0{( ,)},0,1))(({(max )( 1 IIif IIifIprI IU  for any .),( NNZI  For example, for (2,10)}{(1,3),I and  IJ , function will result   )(IU (3,0)}(2,10),{(1,3), and {(0,0)})(   JU accordingly; selection by maximal name max : )()(max ))(pr(max 1 IprI I ,   II )(max ; zeroing of values }0{ : JI )}(0{ , where }0{)(pr&)(pr)(pr 211  JIJ . For example, 2,0)}({(1,0), (2,10)})1,3),({ {0}(  ; increment  : maps any non-empty record ),( NNZI  to record )(I , }),()1,{()( IavavI  . decrement  : maps any non-empty record ),( NNZI  to record )(I , which               0,0 ,0,1 :&),(:),()( a aa bbIavvbvI . In case if  II ,   III )()( . Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології, 2015, № 4 93 Designate set of ),( NNZ -pr-functions and ),( NNZ -pr-predicates described as ...,2,1 ...,,1,,,},0{max,,,,,),(           n nm n m Z ZZ IUWV . Analogically to previous section, consider ),( NNZ -functions  and  — coding and decoding functions, accordingly.  and  is certain extension of mapping 1 . Therefore lemma 6 takes place. Lemma 6. ),( NNZ -model of M -function ( M -predicate) from set M may be created from functions of ),( NNZ  set with PPA operations. It is easy to build ),( NNZ -models for M -pr-predicate of equality and M - pr-functions ,},1{,, 1 mAll  . Let us build model of function for multi-sets addition  . Now, introduce few auxiliary ),( NNZ -functions and ),( NNZ - predicates. Namely identically false and identically true predicates Fal and :Tru )),(,,( 1 2 1 3 IUSISFal   and ),,( 11 3 IISTru  ; predicate of inequality Neq : ),),,,(( 21 3 TruFalIISNeq  ; constant empty record Z : ),,( 11 IIS ZZ  ; selection by pattern Sel : )),,(,,(),( 21 3 1 3 21 IISISIISel ZZ  ; for example, )}2,2{()})5,4(),3,2{()},2,2(),1,1({( Sel — function «selects» from record 1I those components, names of which are in record 2I , i.e. 2I is a kind of pattern for selection from 1I ; maximal addition max of pair of records with same schemes: )),(),,()),},0({,(( 2 2 22 1 22 2 22 2 33max ISISISINeqS  . For example, for records )}2,2(),1,1{(1 I and )}5,2(),3,1{(2 I we will get  ),( 21 max II )}7,2(),6,1{()}52,2(),51,1{(  . Note, that operation of maximal addition in general case is non-commutative, i.e. ),(),( 12 max 21 max IIII  . Commutative property preserved only for records of special type, for example, for same-scheme single-element records. For instance, if )}2,2{(1 I and )}5,2{(2 I , then )}7,2{(),(),( 12 max 21 max  IIII . Now we can get down directly to building of ),( NNZ -pr-function Z — model of M -function  . Assume that records )},(),...,,{( 111 1 1 11 11 nn dvdvI  and )},(),...,,{( 222 1 2 12 22 nn dvdvI  are given and },...,{)()( 121 srr vvIshIsh  . Z operation «breaks» records 1I and 2I to «segments», designated as 11 I , 21I , 12I and 22I with schemes },...,{\)()( 11 11 srr vvIshIsh  , },...,{)( 121 srr vvIsh  , )( 12Ish },...,{\)( 12 srr vvIsh and },...,{)( 122 srr vvIsh  . Thus, resulting record may be represented as: 2211 21213 IIIII Z . Note, )()( 22 21 IshIsh  . As for first two items 11I and 12I , they are easily created with earlier defined function Z . Namely, 2111 III  and 1221 III  . As for 22 21 II Z , 21I and P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 94 22I are easily defined with usage of function Sel : ),( 2112 IISelI  and ),( 1222 IISelI  . Now model ),( NNZ -function Z for same-scheme records 21I and 22I . It is easy to convince that Z may be represented as: ))(max,)))(max,(()((max,)),(( 21 2 2 2 2 2 2 2 1 max2 2 2 1 2 2 2 1 4      f Z fp Z IIIISelIIIINeq  . Obviously, in case when  )()( 21 IshIsh , record 22 21 II Z is empty too, i.e.  22 21 II Z and, consequently, the result is 11 21213 IIIII Z  . Taking in account that  )()( 11 21 IshIsh , the result may be expressed as 11 2121213 IIIIIII Z  . Lemma 7. Functions  and  may be built from functions of set ),( NNZ  by finite number of applications of PPA. Correctness of the result is obvious, because of noted similarity of records and multi-sets, simplicity of coding and decoding mappings ( and  ), and ad- duced earlier statements. Hence, lemma 8 is correct. Lemma 8.   ,,,,, ),( ),( NNZM NNZM — AS with basis M . So, theorem 4 is true. Theorem 4. ...,2,1 ...,,1,,,},0{max,,,,,),(           n nm n m Z ZZ IUNN — genera- tive system of PPA чр Z NNA ),( . Considering given above statements 1, 2 certain conclusions respectively to possible reducability of ),( NNZ  may be made. Equality predicate cannot be ex- cluded from ),( NNZ  because it is sole predicate in CS. Z ( )(IU  ,  , max , }0{ ) — the only function in CS that does not preserve set }{\),( IZ NN ( )}}0,0{{(\),( NNZ , }][{iZ Ni   , }]1,[{   iiZ Ni  , Ni iiZ  )}}0,{{(\}][{ ). Moreover, )(IU  does not  -preserve denotations with given such estimation NNNZ 2: ),(  that  )(I and ,,...,{)}),(),...,,({( 111 nnn vvdvdv  },,...,1 ndd ,...3,2,1n As for increment  and decrement  functions, they are in ),( NNZ  simultaneously for convenience and symmetry, however they are not independent. For example, decrement may be easily produced by PPA operations from rest of the functions and predicate of ),( NNZ  ( )),,(},0{),),,(),,(),,,((( 1 1 1 1 3 3 3 2 3 1 3 3 3 2 344 IISIIISIINeqSS  ). The fact that  as well as  does not preserve denotations with given estimation : for which  )(I and ,...3,2,1},,...,{)}),(),...,,({( 111  ndddvdv nnn directly results truthfulness of theorem 5. Primitive programing algebra: general approfch to a problem of functional completeness Системні дослідження та інформаційні технології, 2015, № 4 95 Theroem 5. ...,2,1 ...,,1,,},0{max,,,,,),(           n nm n m Z Z I Z IU n m NN — n mI -basis of PPA pr Z NNA ),( . CONCLUSIONS Modern IT problematic needs direct consideration of not only programming prob- lems solutions, but processes, which lead to them. That is why researches of such processes organization structures are of paramount importance today. A special place in those researches takes problematic, connected with building of algebraic characteristics of pragmatically conditioned function classes, particularly, with solutions of completeness problems in corresponding algebras. In the paper these questions discussed on basis of primitive program algebras. Method of generative sets finding in PPA presented here, and applied to research of class of partially- recursive functions on records, which is of theoretical and applied importance. Using concepts of complete and allowable systems, and results received, espe- cially criteria of completeness, universality of proposed method in classes of computable functions on different carriers proved. Results received form foundations for development of adaptive program- ming environments. Next steps in this direction will be related with investigation of general concept of composition and development of functions exploring reduc- tion methods connected with it as means of pragmatically driven decomposition of programming problems. REFERENCES 1. Dijkstra E. A Discipline of Programming. — Prentice Hall, Inc., 1978. — 275 p. 2. Brooks F.P. The Design of Design: Essays from a Computer Scientist. — Addison- Wesley, 2010. — 448 p. 3. Brooks F.P. The Mythical Man-Month: Essays on Software Engineering. — Addi- son-Wesley, 1995. — 304 с. 4. Redko V.N. Fundamentals of compositional programming // Cybernetics and System Analysis. — 1979. — № 3. — P. 3–13. 5. Redko V.N. Semantical structures of software // Cybernetics and System Analysis. — 1981. — № 1. — P. 3–19. 6. Redko V.N. Universal program logics and their application // Proc. of 4th soviet-wide symp. — Kishenev, 1983. — P. 310–326. 7. Basarab I.A., Nikitchenko N.S., Redko V.N. Compositional databases. — K.: Lybid, 1992. — 92 p. 8. Redko I.V., Redko V.N. Existential basis of compositional paradigm // Programming and Computer Softtware. — 2008. — № 2. — P. 3–12. 9. Bui D.B., Redko V.N. Primitive program algebras І, ІІ // Cybernetics. – 1985. — № 1. — P. 28–33. 10. Bui D.B., Redko I.V. Primitive program algebras of computable functions // Cyber- netics. — 1987. — № 3. — P. 68–74. 11. Bui D.B., Redko I.V. Primitive program algebras of functions, which preserve deno- tates // Report of Ukrainian AS. — 1988. — № 9. — P. 66–68. 12. Yershov U.L. Theory of numerations. — M.: Nauka, 1977. — 416 p. P.O. Yahanov, D.I. Redko, I.V. Redko, T.L. Zakharchenko ISSN 1681–6048 System Research & Information Technologies, 2015, № 4 96 13. Redko I.V., Snigur N.M. Primitive program algebra of computable functions on graph // Naukovi Visti NTUU “KPI”. — 2011. — № 4. — P. 75–80. 14. 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. 15. 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. 16. Maltsev A.I. Algorythmic systems. — M.: Nauka. — 1970. — 392 p. 17. Maltsev A.I. Constructive algebras. 1 // Uspekhi matematicheskih nauk. — 1961. — 6. — № 3. — P. 3–60. 18. Maltsev A.I. Algorithms and recursive functions // Groningen: Wolters-Noordhoff, 1970. — 391 p. 19. Cutland N. Computability. An introduction in recursive function. — M.: Mir, 1983. — 256 p. 20. Yershov A.P. Computability in arbitrary fields and bases // Semiotics and Infor- matics. — 1982. — № 19. — P. 3–58. 21. Maltsev A.I. Selected works // Mathematical logic and general theory of algebraic systems. — 1976. — 2. — M.: Nauka, 1976. — 388 p. Received 13.05.2015 From the Editorial Board: the article corresponds completely to submitted manuscript.

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

Institution

Ähnliche Einträge