Дискретная математика. Кулабухов С.Ю. - 144 стр.

gLAWA   VII.   oSNOWY TEORII ALGORITMOW

   lEGKO PONQTX, ^TO EGO HARAKTERISTI^ESKAQ FUNKCIQ ESTX
                                                                      
                                                                                   1
 ESLI x > 0
            A (x) = Sg jx ; a1 j  Sg jx ; a2j  : : :  Sg jx ; an j
 GDE Sg(x) = 0
 ESLI x = 0.

dEJSTWITELXNO, ESLI x 2 A, TO x = ak , GDE ak 2 A. sLEDOWATELXNO, Sg jx ; ak j = 0, A PO\TOMU
I A (x) = 0. eSLI VE x 2= A, TO Sg jx ; ai j = 1 DLQ WSEH i = 1
 : : :
 n. zNA^IT, W \TOM SLU^AE,
 A (x) = 1.
    pOKAVEM, ^TO A (x) QWLQETSQ PRIMITIWNO REKURSIWNOJ, A ZNA^IT I REKURSIWNOJ. wIDNO, ^TO
FUNKCIQ A (x) POLU^ENA PRI POMO]I SUPERPOZICIJ IZ FUNKCIJ xy, Sg(x) I jx ; yj. pOKAVEM
TEPERX, ^TO KAVDAQ IZ \TIH FUNKCIJ QWLQETSQ PRIMITIWNO REKURSIWNOJ.
    A) fORMULY
                                    x  0 = 0 = o(x)
                                    x(y + 1) = xy + x = I13 (x
 y
 xy) + xy
POKAZYWA@T, ^TO FUNKCIQ xy POLU^ENA PRI POMO]I OPERATORA PRIMITIWNOJ REKURSII IZ PRIMI-
TIWNO REKURSIWNYH FUNKCIJ (FUNKCIQ x+y QWLQETSQ PRIMITIWNO REKURSIWNOJ, SM. PRIMER 1.5.1),
A ZNA^IT QWLQETSQ PRIMITIWNO REKURSIWNOJ.
    B) fORMULY
                                           Sg(0) = 0 = o(x)
                                           Sg(x + 1) = 1 = s(o(x))
POKAZYWA@T, ^TO FUNKCIQ Sg(x) POLU^ENA PRI POMO]I OPERATORA PRIMITIWNOJ REKURSII IZ PRI-
MITIWNO REKURSIWNYH FUNKCIJ, :A ZNA^IT :QWLQETSQ PRIMITIWNO REKURSIWNOJ.
    W) zAMETIM, ^TO jx ; yj = (x ; y) + (y ; x), GDE FUNKCIQ
                                  x ;: y = x0
; y
 ESLI       xy
                                          

                                                       ESLI x < y
NAZYWAETSQ USE^ENNOJ RAZNOSTX@.
   fORMULY
                         x ;: 0 = x = I11 (x)
                         x ;: (y + 1) = (x ;: y) ;: 1 = I33 (x
 y
 x ;: y) ;: 1
POKAZYWA@T, ^TO FUNKCIQ x ;: y POLU^ENA PRI POMO]I OPERATORA PRIMITIWNOJ REKURSII IZ PRI-
MITIWNO REKURSIWNYH FUNKCIJ (DOKAVITE SAMOSTOQTELXNO, ^TO FUNKCIQ x ;: 1 QWLQETSQ PRIMI-
TIWNO REKURSIWNOJ), A ZNA^IT QWLQETSQ PRIMITIWNO REKURSIWNOJ.
   pROBLEMOJ WHOVDENIQ DLQ ^ISLOWOGO MNOVESTWA A NAZYWAETSQ ZADA^A OTYSKANIQ ALGORITMA,
KOTORYJ PO STANDARTNOJ ZAPISI (NAPRIMER, DESQTI^NOJ) PROIZWOLXNOGO NATURALXNOGO ^ISLA a
POZWOLQET UZNATX, PRINADLEVIT LI ^ISLO a MNOVESTWU A ILI NET, TO ESTX POZWOLQET WY^ISLQTX
ZNA^ENIQ HARAKTERISTI^ESKOJ FUNKCII MNOVESTWA A. w SILU TEZISA ~ER^A SU]ESTWOWANIE TAKOGO
ALGORITMA RAWNOSILXNO REKURSIWNOSTI HARAKTERISTI^ESKOJ FUNKCII. pO\TOMU MOVNO SKAZATX,
^TO REKURSIWNYE MNOVESTWA | \TO MNOVESTWA S ALGORITMI^ESKI RAZREIMOJ PROBLEMOJ WHOV-
DENIQ.
   nAKONEC OTMETIM, ^TO PONQTIE REKURSIWNOGO MNOVESTWA MOVNO RASPROSTRANITX I NA MNOVES-
TWA, NE QWLQ@]IESQ ^ISLOWYMI. dLQ \TOGO MOVNO, NAPRIMER, PERENUMEROWATX \LEMENTY PROIZ-
WOLXNOGO NE BOLEE ^EM S^ETNOGO MNOVESTWA M I RASSMATRIWATX ^ISLOWYE MNOVESTWA INDEKSOW
\LEMENTOW M.
   4.4. oB]EZNA^IMYE FORMULY ALGEBRY PREDIKATOW. dLQ FORMUL ALGEBRY WYSKAZY-
WANIJ SU]ESTWUET ALGORITM, POZWOLQ@]IJ OPREDELITX QWLQETSQ DANNAQ FORMULA TAWTOLOGIEJ
ILI NET. tAKIM ALGORITMOM QWLQETSQ POSTROENIE TABLICY ISTINNOSTI. oDNAKO, \TOT ALGORITM
NE PRIMENIM DLQ FORMUL ALGEBRY PREDIKATOW, TAK KAK TAKIE FORMULY RASSMATRIWA@TSQ I NA
BESKONE^NYH MNOVESTWAH, DLQ KOTORYH PROCESS POSTROENIQ TABLIC ISTINNOSTI QWLQETSQ BESKO-
NE^NYM. wOZNIKAET WOPROS: SU]ESTWUET LI ALGORITM, POZWOLQ@]IJ DLQ PROIZWOLXNOJ FORMULY
ALGEBRY PREDIKATOW USTANOWITX ZA KONE^NOE ^ISLO AGOW QWLQETSQ DANNAQ FORMULA OB]EZNA^IMOJ
ILI NET? oTRICATELXNYJ OTWET NA \TOT WOPROS DAET TEOREMA, POLU^ENNAQ ~ER^EM W 1936 GODU.
                                              144