D:\sbornik\...\article_eng.DVI


Mathematical Problems of Computer Science 34, 2010.

An Appr oach to Gener al For m Recur sive E quation

Solutions

H r a n t B . Ma r a n d jia n

Institute for Informatics and Automation Problems of NAS RA

e-mail: hrant marandjian@sci.am

R e s e a r c h in ¯ n d in g s o lu t io n s o f fu n c t io n a l e qu a t io n s h a ve a lo n g h is t o r y. In 1 7 9 1 A .
L e g e n d r e [4 ] p o s e d t h e p r o b le m o f ¯ n d in g t h e c o n t in u o u s s o lu t io n s o f t h e e qu a t io n

f ( x + y ) = f ( x ) + f ( y ) ( 1 )

It wa s d e a lt wit h a s L e g e n d r e a n d Ga u s s , b u t it s s o lu t io n , a s we ll a s o t h e r s im ila r e qu a t io n s ,
b u t m a n a g e d t o g e t b y A . Ca u c h y [1 ]. L a t e r t h e fu n c t io n a l e qu a t io n s we r e in ve s t ig a t e d b y
m a n y a u t h o r s .

Th e p r e s e n t a u t h o r b e g a n r e s e a r c h in s e a r c h o f c o m p u t a b le s o lu t io n s t o g e n e r a l fo r m
r e c u r s ive e qu a t io n s ( GFR E ) ( s e e [5 ], [6 ]) :

F1[f1; f2; : : : ; fn]( x1; x2; : : : ; xm ) ' G1[f1; f2; : : : ; fn]( x1; x2; : : : ; xm ) ;
F2[f1; f2; : : : ; fn]( x1; x2; : : : ; xm ) ' G2[f1; f2; : : : ; fn]( x1; x2; : : : ; xm ) ;

; ( 2 )

Fk[f1; f2; : : : ; fn]( x1; x2; : : : ; xm ) ' Gk[f1; f2; : : : ; fn]( x1; x2; : : : ; xm ) ;

wh e r e xi a r e n u m e r ic va r ia b le s ,fi- a r e va r ia b le s d e n o t in g t h e d e s ir e d fu n c t io n s , Fi, Gi -
r e c u r s ive ( c o m p u t a b le ) fu n c t io n a ls . In [5 ] it wa s s h o wn t h a t t h e p r o b le m o f t h e e xis t e n c e o f
c e r t a in s o lu t io n s t o t h e s ys t e m s o f t h e t yp e ( 2 ) is §03¡ c o m p le t e if lo o kin g fo r p a r t ia l s o lu t io n s
a n d is §11¡ c o m p le t e if lo o kin g fo r t o t a l s o lu t io n s . It is e vid e n t , t h a t a n y s ys t e m o f d i®e r e n t ia l,
in t e g r a l o r e ve n m ixe d t yp e o f im p lic it e qu a t io n s , r e wr it t e n in a fo r m s u it a b le fo r n u m e r ic a l
c o m p u t a t io n , b r in g s t o fo r m o f a GFR E . H e n c e it is n a t u r a l t o fa c e t o p r o b le m s c o n c e r n in g
t h e s e a r c h fo r s o lu t io n s t o t h e s e e qu a t io n s . P . Co llin s a n d D . B a u m a n [2 ] e xa m in e d s e a r c h
fo r c o m p u t a b le s o lu t io n s t o o r d in a r y d i®e r e n t ia l e qu a t io n s . Th e a u t h o r s h u m o r o u s ly c a lle d
t h e m e t h o d , t h e y h a ve d e ve lo p e d , a m e t h o d " b y a t h o u s a n d m o n ke ys ." N e ve r t h e le s s , t o
s o lve im p o r t a n t s c ie n t i¯ c o r t e c h n ic a l p r o b le m , we n e e d s o lve s u c h s ys t e m s o f e qu a t io n s .
In t h is p a p e r , we wo u ld like t o illu s t r a t e a n a p p r o a c h t h a t s o m e t im e s c a n h e lp t o ¯ n d
s o lu t io n ( s ) . A t it s h e a r t a r e t h e d e t a ils o f t h e p r o o f o f t h e t h e o r e m o n n e c e s s a r y a n d s u ± c ie n t
c o n d it io n s fo r c o m p u t a b le s o lu t io n e xis t e n c e t o e qu a t io n s o f t h is t yp e ( [5 ], [6 ]) . Th e p r o p o s e d
m e t h o d c o n s is t s o f t h e s e le c t io n o f r e p la c e m e n t s o f o c c u r r e n c e s o f t h e u n kn o wn fu n c t io n s in
e xp r e s s io n s wit h p r o p e r ly m a t c h e d fu n c t io n a ls a n d t h e n a p p lyin g t h e t h e o r e m o n t h e jo in t
¯ xe d p o in t . Fo r s im p lic it y we will r e s t r ic t o u r s e lve s wit h a s im p le c a s e t h a t s h o ws t h e n e e d e d

2 6



2 7

s t e p s .
E xample. S u p p o s e we a r e g ive n t h e fo llo win g t r a n s c e n d e n t a l e qu a t io n :

[f ( n) =2 ] + ( f ( n ) ) 2f (n¡1) ' ( 2 f ( n ¡ 2 ) ) f (n+1) + f ( n ¡ 2 ) : ( 3 )

E a s y t o s e e t h a t t h e m a in o b s t a c le s a r e t h e p r e s e n c e o f t h e " In t e g e r p a r t " a n d s u m m a t io n
fu n c t io n s . To e lim in a t e t h e s e p a r t s , W e d e ¯ n e a n a u xilia r y fu n c t io n a l H a s fo llo ws :

H[g]( n) ) ' 2 g ( n ¡ 2 ) : ( 4 )

R e p la c in g in ( 3 ) t h e o c c u r r e n c e o f f ( n ) wit h t h e d e ¯ n it io n o f H[f]( n ) a n d m a kin g c a n c e lla -
t io n , we g e t :

( 2 f ( n ¡ 2 ) 2f (n¡1) ' ( 2 f ( n ¡ 2 ) ) f (n+1): ( 5 )
A t t h e n e xt s t e p we r e p la c e in ( 5 ) f ( n + 1 ) wit h H[f]( n + 1 ) a n d o b t a in

( 2 f ( n ¡ 2 ) 2f (n¡1) ' ( 2 f ( n ¡ 2 ) ) 2f (n¡1): ( 6 )

t h a t is it is a n id e n t it y. E a s y t o s e e t h a t t h e S .C. K le e n e 's [3 ] ¯ xe d p o in t s o f t h e e qu a t io n
( 4 ) a r e t h e fu n c t io n s s a t is fyin g t h e c o n d it io n

f ( n) ' 2 f ( n ¡ 2 ) : ( 7 )

Co n s e qu e n t ly, a s a s o lu t io n t o ( 3 ) we c a n t a ke a n y fu n c t io n s a t is fyin g t h e d e ¯ n it io n ( 7 )
( a d d in g in it ia l va lu e s ) .

Refer ences

[1 ] Ca u c h y A .-L .,Cours d'analyse de l' ¶E cole R oyale P olytechnique, P r e m iµ e r e P a r t ie , A n a lys e
a lg ¶ e b r iqu e , P a r is , 1 8 2 1 [Oe u vr e s ( 2 ) 3 , P a r is , 1 8 9 7 ].

[2 ] Co llin s P ., Gr a »c a D . S .: E ®ective Computability of Solutions of Ordinary D i®erential
E quations. The Thousand M onkeys Approach,E le c t r o n ic N o t e s in Th e o r e t ic a l Co m p u t e r
S c ie n c e 2 2 1 , 2 0 0 8 , p p .1 0 3 -1 1 4 .

[3 ] K le e n e S . C., Introduction to M etamathematics. D . V a n N o s t r a n d Co ., In c ., N e w Y o r k,
To r o n t o , 1 9 5 2 .

[4 ] L e g e n d r e A . M., E l¶ements de g¶eometrie. P a r is , 1 7 9 1 . N o t e II.

[5 ] Ma r a n d jia n H .B ., Selected Topics in R ecursive F unction Theory in Computer Science,
D TH , L yn g b y, 1 9 9 0 . p p 3 1 -4 7 .

[6 ] Ma r a n d jia n , H .B ., General F orm R ecursive E quations I, in : Co m p u t e r S c ie n c e L o g ic . S e -
le c t e d P a p e r s , L e c t u r e N o t e s in Co m p u t e r S c ie n c e , vo l. 9 3 3 , S p r in g e r , B e r lin , H e id e lb e r g ,
1 9 9 5 , p p . 5 0 1 -5 1 1 .