D:\User\sbornik_38_pdf\32.DVI


Mathematical Problems of Computer Science 38, 76, 2012.

On T ur ing Completeness of One M inimal Set of

B uilt-in Functions for Functional P r ogr amming

Languages

G. A . Ma r t ir o s ya n

Chair of Programming and Information Technologies, YSU

E-mail: gevorg.martirosyan@gmail.com

Ma n y fu n c t io n a l p r o g r a m m in g la n g u a g e s o p e r a t e o n S-expressions. Th e s e t s o f b u ilt -
in fu n c t io n s o f t h o s e la n g u a g e s c o n t a in car; cdr; cons; atom; eq; if then else fu n c t io n s .
It is s h o wn t h a t Tu r in g c o m p u t a b le fu n c t io n s d e ¯ n e d o n S-expressions c a n b e p r e s e n t e d
in s u c h fu n c t io n a l p r o g r a m m in g la n g u a g e s wh ic h h a ve car; cdr; cons; atom; eq;
if then else b u ilt -in fu n c t io n s . In o t h e r wo r d s , if t h e s e t o f b u ilt -in c o n s t a n t s o f a fu n c t io n a l
p r o g r a m m in g la n g u a g e c o n t a in s a ll t h e s e fu n c t io n s , t h e n t h a t la n g u a g e is Tu r in g c o m p le t e .
Th e fo llo win g t wo r e s u lt s a r e o b t a in e d fo r t h e m in im a lit y o f t h e s e t o f b u ilt -in fu n c t io n s
© =fcar; cdr; cons; atom; eq; if then elseg.

1 . © is m in im a l fo r fu n c t io n a l p r o g r a m m in g la n g u a g e s wh ic h u s e m o r e t h a n t wo a t o m s .

2 . Th e fu n c t io n eq is r e p r e s e n t a b le in a fu n c t io n a l p r o g r a m m in g la n g u a g e wh ic h u s e s o n ly
t wo a t o m s a n d t h e s e t ©n feqg o f b u ilt -in fu n c t io n s ; t h e s e t o f b u ilt -in fu n c t io n s ©n
feqg is m in im a l fo r fu n c t io n a l p r o g r a m m in g la n g u a g e s wh ic h u s e o n ly t wo a t o m s a n d
it is t h e o n ly p r o p e r s u b s e t o f t h e s e t ©, wh ic h is m in im a l fo r s u c h la n g u a g e s .

R eferences

1 . S .A . N ig iya n , " Fu n c t io n a l L a n g u a g e s " , P rogramming and Computer Software, V o l. 1 7 .
p p . 2 9 0 -2 9 7 , 1 9 9 2 .

2 . S .A . N ig iya n , " On in t e r p r e t a t io n o f fu n c t io n a l p r o g r a m m in g la n g u a g e s " , P rogramming
and Computer Software, V o l. 1 9 . p p . 7 1 -7 8 , 1 9 9 3 .

3 . L .E . B u d a g h ya 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 o f c o m p le t e n e s s o f c o m p u t a t io n
r u le fo r s t r o n g ly t yp e d fu n c t io n a l p r o g r a m s " , P r o c e e d in g s o f t h e Co n fe r e n c e o n Co m -
p u t e r S c ie n c e a n d In fo r m a t io n Te c h n o lo g ie s ( CS IT-2 0 0 5 ) , Y e r e va n , 2 0 0 5 , p . 1 6 -1 9

7 6