Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 43, 42--46, 2015. 42 On Generalized Primitive Recursive String Functions 1 Mikayel H. Khachatryan Institute for Informatics and Automation Problems of NAS RA e-mail: mikayel.khachatur@gmail.com Abstract The notion of generalized primitive recursive string function is introduced and relations between such functions and primitive recursive string functions in the usual sense ([1], [2]) are investigated. It is proved that any generalized primitive recursive string function is everywhere defined if and only if it is a primitive recursive string function in the usual sense. Keywords:String function, Primitive recursive string function, Superposition, Alphabetic primitive recursion. 1. Introduction The notion of primitive recursive string function ([1], [2]) is generalized in the following sense: string functions are considered which are defined similar to the definition of primitive recursive string functions, however, such functions are in general not everywhere defined. Namely, the definition of generalized primitive recursive string function is obtained from the definition of primitive recursive string function in the usual sense by adding the everywhere undefined one- dimensional string function to the set of basic functions. It is proved that any generalized primitive recursive string function is everywhere defined if and only if it is a primitive recursive string function in the usual sense. Similar problems concerning arithmetical functions are considered in [3]. 2. Generalized Primitive Recursive String Functions The notion of many-dimensional primitive recursive string function is given in [1], [2]. For the convenience of the reader let us recall the corresponding definitions. Let A be an alphabet, i.e. a list of different symbols, { } ( ) By we denote the set of all words in A (including the empty word ). The symbols 1 This work was supported by State Committee of Science, MESRA, in frame of the research project № SCS 13- 1B321. M. Khachatryan 43 we call letters in A. The length of a word is the number k (the length of the empty word  is 0).  We say that the function F is an n-dimensional string function ( ) in the alphabet A if for any n-tuple ( ) where all are words in A, the value ( ) is either undefined, or is a word in A. By ( ) we denote the statement: the value ( ) is defined. Below we consider only the string functions in the fixed alphabet A. Basic string functions are defined as functions of the following kinds. 1. One-dimensional function ( )such that ( )  for any word P in A. 2. One-dimensional function ( ) where such that ( ) for any word P in A. 3. n-dimensional functions ( ) where such that ( ) for any n-tuple ( ) of words in A. The operator S of superposition is defined as follows. If G is an n-dimensional string function, are m-dimensional string functions, then the m-dimensional string function ( ) is defined by the following equality: ( ) ( ( ) ( ) ( )) where are any words in A. The operator R of alphabetic primitive recursion is defined as follows. If G is an n- dimensional string function, are (n+2)-dimensional string functions, then the (n+1)-dimensional string function ( ) is defined by the following equalities: ( ) ( )   ( ) ( ( )) where and are any words in A. We say that a string function is a primitive recursive string function (PRSF), if it can be obtained from basic functions by the operators of superposition and alphabetic primitive recursion. The notion of generalized primitive recursive string function (GPRSF) is defined similar to the notion of PRSF with the only difference: one-dimensional everywhere undefined U(P) function is added to the set of basic functions. Below the statements “F is a primitive recursive string function in the usual sense”, “F is a generalized primitive recursive string function”, will be denoted correspondingly by and As it is known ([1]. [2]) every function is everywhere defined. Clearly, any primitive recursive string function in the usual sense is a generalized primitive recursive string function, and, on the other side, the set of generalized primitive recursive string functions is wider than one of primitive recursive string functions in the usual sense. However, the following theorem (which will be proved below) takes place. Theorem 1: Any everywhere defined string function is a generalized primitive recursive string function iff it is a primitive recursive string function in the usual sense. On Generalized Primitive Recursive String Functions 44 The proof of Theorem is based on Lemma 1 which will be considered below. We will use primitive recursive string functions which are defined by the following equalities (where are any words in A). 1. The function ̇ is defined as follows:  ̇  ̇  ̇  (where ). 2. The function ( ) is defined as follows: ()  ( ) (where ). 3. The function ̅̅ ̅̅ ( ) is defined as follows: ̅̅̅̅ ()   ̅̅̅̅ ( ) (where ). 4. The functions k( )for are defined as follows: 2(   2( ) (where ), 3(   3( ) 2( )(where ), m+1( (where ),  m+1( ) m( ) (where ), It is easily seen that k( )  when one of the words is equal to the empty word  otherwise k( ) A generalized primitive recursive string function ( )(“Branching function”) is defined by the following conditions: (1) ( P:(2) ( ) is undefined when  . Such a function is obtained by the operator of alphabetic primitive recursion using the everywhere undefined basic function U(P): ( P, ( ) ( ( ( )))(where ). Now let us introduce the notion of standard image (or S-image) of string function F in A. Namely for any n-dimensional string function F in A its S-image is defined as a function F* such that for any words in A: ( ) { ( ( )) ( ) (let us recall that ( ) for any word Qin A). Obviously, for any string function F in A the function F* is an everywhere defined string function. Lemma 1: Any string function F in A is a generalized primitive recursive string function if and only if its S-image F* is a primitive recursive string function in the usual sense. M. Khachatryan 45 Proof: Let F be an n-dimensional generalized primitive recursive string function. We will prove that its S-image F* is a primitive recursive string function in the usual sense. The proof will be implemented using the induction on the process of constructing F from the basic functions by the operators of substitution and alphabetic primitive recursion. If F is a basic function then it has one of the forms ( ) ( ), (where ), ( )(where ), ( ) which is everywhere undefined. It is easily seen that in these cases F* has correspondingly the following forms ( ) ( ) ( ) ( ) ( ) So F* is a primitive recursive string function in the usual sense. Now if a function is obtained by the operator S of superposition from functions and the functions are primitive recursive string functions in the usual sense, then the S-image F* of the function F satisfies the following equation: ( ) k+1( ( ( ) ̇ ( ) ̇  ( ) ̇ ) ( ) ̇ ( ) ̇  ( ) ̇ )) where k+1 is the function described above. It is easily seen that Finally, if a function is obtained by the operator R of alphabetic primitive recursion from functions and the functions are primitive recursive string functions in the usual sense, then the S-image F* of the function F satisfies the following equalities: ( ) ( )  ( ) ( ( ))  ( ) ( ( )) where for any i such that ( ) 2( ( ̇ ) ) and are S-images correspondingly, of the function is defined above. It is easily seen that So, it is proved that S-image of any generalized primitive recursive string function is a primitive recursive string function in the usual sense. Now let us suppose that the S-image F* of some n-dimensional string function F is a primitive recursive string function in the usual sense. Clearly, Then the function F satisfies the following equality: ( ) ( ( ) ̇ ̅̅̅̅ ( ( ))) were BR is the function defined above. This completes the proof of Lemma. The proof of Theorem 1 is obtained now as follows. If F is an n-dimensional everywhere defined string function such that then and ( ) ( ) ̇ for any words in A. Hence, On the other side, if then clearly F is an everywhere defined string function such that This completes the proof of Theorem. On Generalized Primitive Recursive String Functions 46 References [1] A. I. Malcev, Algorithms and Recursive Functions, 2 nd edition, Moscow, “Nauka”, (in Russian), 1986. [2] M. H.Khachatryan, “On the representation of arithmetical and string functions in formal languages”, Transactions of the IIAP of NAS of RA, Mathematical problems of computer science, vol. 27, pp. 37-53, 2006. [3] I.D. Zaslavsky, “On some generalizations of the primitive recursive arithmetic”, Theoretical Computer Science, vol. 322, pp. 221-230, 2004. Submitted 10.12.2014, accepted 16. 02. 2015. Ընդհանրացված պարզագույն կարգընթաց բառային ֆունկցիաների մասին Մ. Խաչատրյան Ամփոփում Սահմանվում է ընդհանրացված պարզագույն կարգընթաց բառային ֆունկցիայի հասկացությունը, ինչպես նաև հետազոտվում են այդպիսի ֆունկցիաների փոխառնչությունները սովորական ձևով սահմանված ([1], [2]) պարզագույն կարգընթաց բառային ֆունկցիաների հետֈ Ապացուցվում է, որ ցանկացած ընդհանրացված պարզագույն կարգընթաց բառային ֆունկցիա ամենուրեք որոշված է այն և միայն այն դեպքում, երբ այն սովորական իմաստով պարզագույն կարգընթաց բառային ֆունկցիա էֈ Об обобщенных примитивно рекурсивных словарных функциях М. Хачатрян Аннотация Определяется понятие обобщенной примитивно рекурсивной словарной функции и исследуются взаимоотношения таких функций с примитивно рекурсивными словарными функциями ([1], [2]) в обычном смысле этого понятия. Доказывается, что обобщенная примитивно рекурсивная словарная функция всюду определена тогда и только тогда, когда она является примитивно рекурсивной словарной функцией в обычном смысле этого понятия.