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

                                                        x 4. aLGORITMI^ESKI NERAZREIMYE PROBLEMY

KOTORYJ, O^EWIDNO, S^ETEN. |TO ZNA^IT, ^TO MNOVESTWO WSEH N. A. m., WY^ISLQ@]IH NORMALXNO
WY^ISLIMYE ^ASTI^NYE ^ISLOWYE FUNKCII, QWLQETSQ S^ETNYM.
   tAKIM OBRAZOM, KLASS KNW NORMALXNO WY^ISLIMYH ^ASTI^NYH ^ISLOWYH FUNKCIJ S^ETEN. nO
MNOVESTWO WSEH ^ASTI^NYH ^ISLOWYH FUNKCIJ IMEET MO]NOSTX KONTINUUMA. |TO OZNA^AET, ^TO
SU]ESTWU@T ^ASTI^NYE ^ISLOWYE FUNKCII, NE QWLQ@]IESQ NORMALXNO WY^ISLIMYMI I, SLEDO-
WATELXNO, NE QWLQ@]IESQ REKURSIWNYMI I NE QWLQ@]IESQ WY^ISLIMYMI PO tX@RINGU. tAKIE
^ISLOWYE FUNKCII NAZOWEM NEWY^ISLIMYMI.
   4.2. pRIMER NEWY^ISLIMOJ FUNKCII. tAK KAK NORMALXNO WY^ISLIMYH FUNKCIJ S^ET-
NOE MNOVESTWO, TO PERENUMERUEM WSE \TI FUNKCII. tAKIM OBRAZOM, WSQKAQ NORMALXNAQ FUNKCIQ
IMEET NEKOTORYJ NOMER. pUSTX '0 
 '1
 '2
 : : : | WSE NORMALXNO WY^ISLIMYE FUNKCII. oPREDELIM
^ISLOWU@ FUNKCI@ f SLEDU@]IM OBRAZOM:
                                (
                       f(x) =       'x (x) + 1
 ESLI 'x (x) OPREDELENO

                                    1
          ESLI 'x (x) NE OPREDELENO:
   eSLI PREDPOLOVITX, ^TO FUNKCIQ f(x) NORMALXNO WY^ISLIMA, TO POLU^IM, ^TO f(x) = 'k (x)
DLQ NEKOTOROGO k 2 N0 . tAK KAK f(x) WS@DU OPREDELENA, TO I 'k (x) OPREDELENA WS@DU NA N0 .
tOGDA
                                            f(k) = 'k (k):
nO PO OPREDELENI@ FUNKCII f(x) IMEEM:
                                          f(k) = 'k (k) + 1:
iZ DWUH POSLEDNIH RAWENSTW POLU^AEM PROTIWORE^IWOE RAWENSTWO:
                                         'k (k) = 'k (k) + 1:
tAKIM OBRAZOM, OPREDELENNAQ WYE FUNKCIQ f(x) NE QWLQETSQ NORMALXNO WY^ISLIMOJ, I POTOMU
NE QWLQETSQ WY^ISLIMOJ PO tX@RINGU I ^ASTI^NO REKURSIWNOJ, TO ESTX DLQ WY^ISLENIQ WSEH EE
ZNA^ENIJ NE SU]ESTWUET ALGORITMA.
  4.3. rEKURSIWNYE MNOVESTWA.
oPREDELENIE 1. pUSTX A  N0 ~ISLOWAQ FUNKCIQ
                                    .


                                                 0
 ESLI x 2 A
                                             
                                        A=       1
 ESLI x 2= A
NAZYWAETSQ HARAKTERISTI^ESKOJ FUNKCIEJ MNOVESTWA A.
pRIMER 1.
   1. eSLI A = ?, TO ? (x) = 1.
   2. eSLI A = N0 , TO N0 (x) = 0.
oPREDELENIE 2. ~ISLOWOE MNOVESTWO A  N0 NAZYWAETSQ REKURSIWNYM ESLI EGO HARAKTE
                                                                              ,                 -
RISTI^ESKAQ FUNKCIQ     A QWLQETSQ REKURSIWNOJ.
   mNOVESTWO, NE QWLQ@]EESQ REKURSIWNYM NAZYWAETSQ NEREKURSIWNYM.
pRIMER 2.
   1. iZ PRIMERA 4.3.1 WIDNO, ^TO PUSTOE MNOVESTWO I MNOVESTWO N0 QWLQ@TSQ REKURSIWNYMI, TAK
KAK IH HARAKTERISTI^ESKIE FUNKCII QWLQ@TSQ REKURSIWNYMI. w SAMOM DELE, ? (x) = 1 = s(o(x))
I N0 (x) = 0 = o(x), GDE o(x) I s(x) | PROSTEJIE FUNKCII.
   2. pUSTX A = fa1 
 a2
 : : :
 ang | PROIZWOLXNOE KONE^NOE MNOVESTWO. pOKAVEM, ^TO ONO QWLQETSQ
REKURSIWNYM.
                                                  143