Microsoft Word - 10_Zaslavski.doc


Mathematical Problems of Computer Science 39, 81--87, 2013. 

 
81 

 

 
 
 

On the Comparative Complexity of Primitive Recursive 

Arithmetical and String Functions1 
 

Igor D. Zaslavsky and Mikayel H. Khachatryan 

 
Institute for Informatics and Automation Problems of NAS RA 

e-mail: zaslav@ipia.sci.am, mikayel.khachatur@gmail.com 
 
 

Abstract 
 

Formal languages LA and LW are introduced as in [1] for the representation of 
primitive recursive arithmetical and string functions. Shannon functions SHAW and SHWA 
describing the relations between the complexities of functions representations in these 
languages are defined as in [1]. A new proof of the upper bounds for SHAW  is presented; 
it is based on a new method giving in some cases new  possibilities for applications in 
comparison with the methods considered in [1]. 

                  Keywords:  string function, arithmetical function, term, alphabetic enumeration, Shannon 
function, primitive recursive function. 
 

Investigations described in this paper may be considered as the continuation of those 
presented in [1]. Let us recall definitions of some notions given in [1]. We suppose that an 
alphabet 1 2{ , ,..., },pA a a a  where 1,p   is fixed. The set of all strings in this alphabet (including 
the empty string  ) is denoted by A*; the set of all k-tuples 1 2( , ,..., ),kQ Q Q  where 

*
iQ A  for 

1 ,i k   will be denoted by *( ) .kA  The set of all non-negative integers {0, 1, 2, ... } will be 
denoted by N; the set of all k-tuples 1 2( , ,..., ),kx x x  where ix N  for 1 ,i k   will be denoted by 

.kN  k-dimensional string function in A is defined ( [1], [2] )  as a mapping of *( )kA into A*; k-
dimensional arithmetical function is defined as a mapping of ( )kN  into N. Primitive recursive 
string functions in A as well as primitive recursive arithmetical functions are defined in a usual 
way as in [1] and [2]. The alphabetic enumeration of the set A* is defined as in [1] and [2]; let us 
recall that this enumeration defines a one-to-one correspondence between the sets A* and N. The 
non-negative integer, corresponding to a string Q in the alphabetic enumeration is denoted by 

( ).Q  The string in A* corresponding to the number n in this enumeration is denoted by ( )p n  or 
.n  The length of a string Q is denoted by .Q  All these notations are used in [1].  

The alphabetic enumeration of strings gives also a one-to-one correspondence between n-
dimensional string functions in A, and n-dimensional arithmetical functions. 
                                                
1 This work is supported by the grant 11-1b 189 of the Government of the Republic of Armenia. 



On the Comparative Complexity of Primitive Recursive Arithmetical and String Functions  
 

82 

Namely, we say ( [1], [2] )  that an n-dimensional arithmetical function f represents an n-
dimensional string function F, if  

1 2 1 2( , , ... , ) ( , , ... , )n nF x x x f x x x            
for all 1 2, ,..., nx x x  in N. In this case we say also that F and  f correspond to one another. 
 The mentioned correspondence gives also a one-to-one correspondence between primitive 
recursive string functions in A and primitive recursive arithmetical functions ( [1], [2] ). 

In [1] the formal languages LA and LW are introduced for the representation of primitive 
recursive arithmetical functions and primitive recursive string functions. The formal expressions 
in these languages are said to be terms; by t LA  and r LW  we denote the statements “t is a 
term in LA”, “r is a term in LW”. In the definition of LA the symbols S and R are used for the 
operators of superposition and primitive recursion of arithmetical functions; in the definition of 
LW the symbols S and R are used for the operators of superposition and alphabetic primitive 
recursion of string functions ( [1], [2] ). Special notations for some modifications of the 
mentioned operators ( Sbl, Sbr, Sel, Ser, Sb, Se in LA; Sbl, Sbr, Sel, Ser, Sb, Se in LW) are also 
included in LA and LW ([1]). We shall consider below special cases of the implementation of the 
modifications Sb and  Se of the operator S (see [1]); these cases are described in the following 
points (1), (2), (3). Let us note that all the terms considered in (1), (2), (3) are terms in the 
language LW. 

(1) If f  and g  are terms expressing correspondingly a v  dimensional 
function f (where 2v  ) and a one-dimensional function g, then the term ( , )f g Se  expresses the 
v  dimensional function h such that 

1 2 1 2 1( , ,..., ) ( , ,..., , ( ))v v vh Q Q Q f Q Q Q g Q   
for all values of the variables 1 2, , ... , .vQ Q Q    

(2) If f  and g  are terms expressing correspondingly a 2-dimensional function f  and a 
k-dimensional function g (where 1k  ), then the term ( , )f g Sb   expresses the (k+1)-
dimensional function h such that 

1 2 1 1 2 1( , ,..., ) ( ( , ,..., ), )k k kh Q Q Q f g Q Q Q Q    
for all values of the variables 1 2 1, , ... , .kQ Q Q     

(3) If 1 2, ,f g g     are terms expressing correspondingly a v  dimensional 
function f (where 2v  ) and one-dimensional functions 1g  and 2 ,g  then the term 1 2( , , )f g g  Sb   
expresses the ( 1)v   dimensional function h such that 

1 2 1 1 1 2 1 2 1( , ,..., ) ( ( ), ( ), ,..., )v vh Q Q Q f g Q g Q Q Q      
for all values of the variables 1 2 1, , ... , .vQ Q Q     
 As it will be seen below, it is convenient to represent the list of variables for the function 
h in the following form: 3 4, , ,... , .vR Q Q Q    Using this list, we can write the expression for h as 
follows: 

3 4 1 2 3 4( , , ,... , ) ( ( ), ( ), , ,..., ).v vh R Q Q Q f g R g R Q Q Q        
 In [1] Shannon functions  ( )AWSH n  and ( )WASH n  are introduced; these functions 
describe the relations between the lengths of terms expressing arithmetical functions (in LA)  and 
string functions (in LW) when the considered functions correspond to one another. Namely, if 
t LW , then by ( )LA t  we denote the set of all terms in LA expressing the arithmetical function 
corresponding to the string function expressed by t. Similarly, if r LA , then by ( )LW r   we 
denote the set of all terms in LW expressing the string function corresponding to the arithmetical 
function expressed by r. Now we can give (see [1]) the definitions of ( )AWSH n  and ( )WASH n  as 
follows: 



I. Zaslavski and M. Khachatryan 83 

 ( )( )&( )( ) max minWA r LA tt LW t nSH n r  ; 
 ( )( )&( )( ) max min .AW t LW rr LA r nSH n t   

In [1] the following statement is established (see the main theorem in [1]): there are upper 
and lower bounss for  ( )AWSH n  and ( )WASH n  such that each of  them has the form ,cn d  
where c and d are some constants. 

We shall consider the function ( ).AWSH n  There are some defects in the proof of the upper 
bouns for this function in [1]; their removal requires essential changes in the proof. Below we 
give another proof of the mentioned bouns based on a method which is different from those used 
in [1]. Namely, we shall give a new proof of the following theorem. 

Theorem. There are constants c and d such that for any non-negative integer n  
  .AWSH n cn d   

We shall use three Lemmas in the proof given in [1] (similar statements are proved also in 

[2]). By ( )n  we denote the function such that (0) ,    1 1 1( ) ...
n

n a a a 
 times 

 for any positive integer n.  
Lemma 1. There are constants c  and d such that for any term t LA  expressing a 

function 1 2( , ,..., ),mx x x   a term LW  expressing some function 1 2( , ,..., )mQ Q Q  can be 
constructed such that the following conditions are satisfied: 

1. 1 2 1 2( ( ), ( ),..., ( )) ( ( , ,..., )),m mx x x x x x        for any 1 2, ,..., mx x x  in N. 
2.  ' '.c t d    
Lemma 2. There is a primitive recursive string function G such that   G m m   for any 
.m N  

Lemma 3. The one-dimensional string function  ( ) ( )Q Q    is primitive recursive. 
Proof of Theorem. Let t be any term in LA expressing some function  1 2( , , ... , ).mx x x      As 

it is proved in [1], the following inequality holds: .m t  
The string function corresponding to   let us denote by 1 2( , , ... , ).mQ Q Q      We shall 

construct a term   in LW having the length mentioned in Theorem and expressing the function  
.   

Using Lemma 1 we construct a term Φ in LA such that ,c t d     where c  and d  are 
constants (fixed in Lemma 1), and Φ expresses a function   satisfying the condition  

1 2 1 2( ( ), ( ),..., ( )) ( ( , ,..., ))m mx x x x x x       
 for  any 1 2, ,..., mx x x  in N. 
 Using Lemmas 1 and 2 we obtain the following equalities  

  
       

  

1 2 1 2

1 2

1 2

1 2

( , ... ) ( ( ), ( )... ( ))

( ( ), ( )... ( ))

( ) , ( ) ... ( )

( ), ( )... ( ) ,

m m

m

m

m

Q Q Q Q Q Q

G Q Q Q

G Q Q Q

G Q Q Q

    

    

      

   

 

 

 



 

By G  and   we denote the terms in LW expressing the functions G and .  
Let us consider the well-known primitive recursive arithmetical functions c, l, r, defining 

a one-to-one correspondence between 2N  and N. Such functions we define by the following 
equalities: 



On the Comparative Complexity of Primitive Recursive Arithmetical and String Functions  
 

84 

( )( 1)
( , ) ,

2
x y x y

c x y x
  

   

( ( ), ( )) ,  
( ( , )) ,  ( ( , )) .

c l z r z z
l c x y x r c x y y


 

 

We consider also the following functions (where 2,  2n k n    ): 

1 2 1 2 3

( 1)  times

( 1)  times

1
( )  times

( , ,..., ) (... ( ( , ), ),..., );

( ) ( (... ( )...));   

( ) ( ( (... ( )...))).

n
n n

n

n

n
n k

nk

c x x x c c c x x x x

c z l l l z

c z r l l l z


















 

Obviously, for any 1 2, ,..., ,nx x x z  in N and for 1 ,k n   the following equalities hold:  

1 2

1 2

( ( ), ( ),..., ( )) ;

( ( , ,..., )) .

n
n n nn

n
nk n k

c c z c z c z z

c c x x x x




 

Using Lemma 1 we construct string functions ,  ,     , such that for any x, y, z in N 
( ( ), ( )) ( ( , ));
( ( )) ( ( ));
( ( )) ( ( )).

x y c x y
z l z
z r z

   
  
  





 

Let us note a peculiarity of these functions. 
If some strings 1 2,  ,  Q Q Q  in A do not contain other letters except 1.a  then the following 

equalities hold: 1 2 1 1 2 2( ( ), ( )) ,  ( ( , )) ,  ( ( , )) .Q Q Q Q Q Q Q Q Q          However, in general 
such equalities are not valid. 

Let us consider also the following string functions (where  2,  2n k n    ) 

1 2 1 2 3
( 1)  times

1
( )  times

( , ,..., ) (... ( ( , ), ),..., );

( ) ( (... ( )...));

( ) ( ( (... ( )...))).

n
n n

n

n
n k

nk

Q Q Q Q Q Q Q

Q Q

Q Q

   

   

    














 

The terms in LW expressing the functions 1,  ,  ,  ,  ,  
n

n nk       (where   

2,  2n k n   ) we denote, correspondingly, by  1,  ,  ,  ,  ,  .
n

n nk           
If some strings 1 2,  ,  ... , nQ Q Q Q  in A do not contain other letters except 1.a  then the 

following equalities hold (where   2,  2n k n   ): 

1 2

1 1 2 1

1 2

( ( ), ( ),..., ( )) ,

( ( , ,..., )) ;
( ( , ,..., )) .

n
n n nn
n

n n
n

nk n k

Q Q Q Q
Q Q Q Q
Q Q Q Q

   

 

 







 

In general such equalities are not valid. 
Now in the case, when 2m  , let us construct the term m  as follows: 

( 1)  times ( 2)  times

( ( ,..., ( ( , ) , ))..., )) , ).
m m

m      
 


 

     Se Sb Se Sb  



I. Zaslavski and M. Khachatryan 85 

Here the group of symbols ( ( ,Se Sb  is repeated (m-1) times; after this the group )  is repeated 
once; after this the group , ))  is repeated (m-2)  times; finally, the group , )  is repeated once. It 
is easily seen that the length of the term m  does not exceed 10 10 ,c m d  where 10c  and 10d  are 
some constants. Let us consider some subterms of the term m  as well as functions expressed by 
them. It is easily seen that the following statements are valid. 

The term ( , ) Sb  expresses the function  1 2( ), .Q Q   
The term  2 ( ( , ), )     Se Sb  expresses the function  1 2( ), ( ) ,Q Q    that is, the 

function  2 1 2( ), ( ) .Q Q    
The term ( , ( ( , ), ))     Sb Se Sb  expresses the function   1 2 3( ), ( ) , .Q Q Q     
The term  3 ( ( , ( ( , ), )), )         Se Sb Se Sb  expresses the function 
  1 2 3( ), ( ) , ( ) ,Q Q Q      that is, the function  3 1 2 3( ), ( ), ( ) .Q Q Q     
Using similar considerations, we conclude that the term m  expresses the function  

1 2 3(... ( ( ( ), ( )), ( )),..., ( )),mQ Q Q Q        
that is, the function 

1 2 3( ( ), ( ), ( ),..., ( )).
m

mQ Q Q Q      
 Further, let us construct the term m  (where   1m  ) as follows: 

( 1)  times( 1)  times

( ( ( , , ), , )..., , ).

mm

m      



  

    Sb ...Sb Sb  

It is easily seen that the length of the term m  does not exceed 11 11,c m d    where 11c  and 

11d  are some constants. Using the inequalities c t d     and m t  we conclude that the 

length m  does not exceed 12 12 ,c t d  where 12c  and 12d  are some constants. Let us consider 

some subterms of the term m , as well as functions expressed by them. It is easily seen that the 
following statements are valid. 

As it is said above, the term   expresses the function   depending on m variables. The 
function   we denote also by 0 .  The term 

1  is defined as the term which is equal to .  

The term 2 ( , , )     Sb  expresses some function 1  depending on ( 1)m   variables; the 
list of variables for this function we denote by 1 3, ,..., .mR Q Q  Using such notations we can 
represent the equality describing the function 1 1 3( , ,..., )mR Q Q  as follows: 

1 1 3 1 1 3( , ,..., ) ( ( ), ( ), ,..., ),m mR Q Q R R Q Q     
that is 

1 1 3 21 1 22 1 3( , ,..., ) ( ( ), ( ), ,..., ).m mR Q Q R R Q Q     
The term 3 ( ( , , ), , )        Sb Sb  expresses the function 2 2 4 5( , , ,..., )mR Q Q Q  

depending on ( 2)m   variables; the equality describing this function can be represented as 
follows:  

2 2 4 5 2 2 2 4 5( , , ,..., ) ( ( ( )), ( ( )), ( ), , ,..., ),m mR Q Q Q R R R Q Q Q        
that is   

2 2 4 5 31 2 32 2 33 2 4 5( , , ,..., ) ( ( ), ( ), ( ), , ,..., ).m mR Q Q Q R R R Q Q Q      



On the Comparative Complexity of Primitive Recursive Arithmetical and String Functions  
 

86 

The term 4 ( ( ( , , ), , ), , )            Sb Sb Sb  expresses the function 3 3 5 6( , , ,..., )mR Q Q Q  
depending on ( 3)m   variables; the equality describing this function can be represented as 
follows:  

3 3 5 6 3 3 3 3 5 6( , , ,..., ) ( ( ( ( ))), ( ( ( ))), ( ( )), ( ), , ,..., ),m mR Q Q Q R R R R Q Q Q            
that is   

3 3 5 6 41 2 42 2 43 2 44 2 5 6( , , ,..., ) ( ( ), ( ), ( ), ( ), , ,..., ).m mR Q Q Q R R R R Q Q Q       
Using similar considerations, we conclude that the term m  expresses the function 

( 1)m   depending on one variable (we shall denote this variable by ( 1)mR  ).  The equality 
describing this function can be represented as follows:  

 ( 1) ( 1) ( 1) ( 1) ( 1)
( 1) ( 2)( 1) ( 2)

( ) ( ( (... ( )...)) , ( ( (... ( )...))),..., ( )),m m m m m
m mm m

R R R R             
  

    

that is   
( 1) ( 1) 1 ( 1) 2 ( 1) ( 1)( ) ( ( ), ( ),..., ( )).m m m m m m mm mR R R R          

 Now let us construct the term  
( , ).m m S  

 This term  expresses the function 
1 1 2 2 1 2

1 2

( ( ( ( ), ( ),..., ( ))), ( ( ( ), ( ),..., ( ))),...

                                                              ..., ( ( ( ), ( ),..., ( )))).

m m
m m m m

m
mm m

Q Q Q Q Q Q

Q Q Q

          

    
 

But the strings 1 2( ), ( ),..., ( )mQ Q Q    do not contain other letters except 1.a  So, we can 
conclude that the function expressed by ( , ),m m S  is equal to  

1 2( ( ), ( ),..., ( )).mQ Q Q     
Hence the term  

( , ( , ))m mG   S S  
expresses the function 

1 2( ( ( ), ( ),..., ( ))),mG Q Q Q     
that is, the function  

1 2( , ,..., ).mQ Q Q   
Clearly, 

13 13 ,c t d    
where 13c  and  13d  are some constants. So, the statement of Theorem is proved for 2.m   
The cases 1m   and 0m   are considered in a similar way. This completes the proof of 
Theorem. 
 Note. Applying usual methods of the recursive functions theory, we can obtain essentially 
more simple and more natural expressions for the term   than those considered above, for 
example  

1 2( , ( , ( , ), ( , ),..., , ( , ))),
m m m

mG I I I    S S S S S       
where any term mkI  for 1 k m   expresses the function  

1 2( , ,..., ) .
m
k m kI Q Q Q Q  

However, such expressions do not give the required bounds of .  For this aim special methods 
should be used. One of such methods is implemented above. 
  
  



I. Zaslavski and M. Khachatryan 87 

References 
 

[1] M. H.  Khachatryan. “On the Representation of Arithmetical and String Functions in Formal 
Languages,” Transactions of  IIAP of NAS of RA, Mathematical Problems of Computer Science, vol. 
27, pp. 37-53, 2006. 

[2] A. I. Maltsev. Algorithms and Recursive Functions. 2nd Edition, Moskow,  Nauka , 1986 (in Russian). 
 

Submitted 28.11.2012, accepted 30.01.2013. 
 

Պարզագույն անդրադրարձ (ռեկուրսիվ) թվաբանական և բառային 
ֆունկցիաների համեմատական բարդության մասին 

 
Ի.   Զասլավսկի և Մ.   Խաչատրյան 

 
Ամփոփում 

 
Դիտարկվում են [1]-ում սահմանված պարզագույն անդրադարձ (ռեկուրսիվ)  
թվաբանական և բառային ֆունկցիաների ներկայացման LA և LW ձևային լեզուները։ 
Շենոնի  AWSH  և WASH  ֆունկցիաները, որոնք բնութագրում են թվաբանական և 
բառային ֆունկցիաների ներկայացումների բարդությունների միջև եղած կապերը 
նշված լեզուներում, սահմանվում են, ինչպես [1]-ում։ Մի նոր մեթոդով տրվում է AWSH  
ֆունկցիայի վերին գնահատականի ապացույցը։ Այդ մեթոդը որոշ դեպքերում 
ապահովում է կիրառությունների ավելի լայն հնարավորություններ, քան` [1]-ում 
դիտարկվող մեթոդները։ 
 
 
 

О сравнительной сложности примитивно рекурсивных  
арифметических и словарных функций 

 
И. Д Заславский и  М.  Хачатрян 

 
Аннотация 

 
Рассматриваются формальные языки LA и LW, введенные в [1] для представления 
примитивно рекурсивных арифметических и словарных функций. Функции Шеннона 

AWSH  и WASH , выражающие соотношения между сложностями представления 
арифметических и словарных функций в этих языках, определяются так же, как в [1]. 
Дается новое доказательство верхней оценки для AWSH , основанное на методе, дающем 
в ряде случаев новые возможности для приложений по сравнению с методами, 
рассматриваемыми в [1].