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

   x   2.   mA INY tX@RINGA
     oPREDELENIE MAINY tX@RINGA WNENIJ I WNUTRENNIJ ALFAWITY PROGRAMMA mAINNYE
                                    :                                ,          .

     SLOWA KONFIGURACII pERERABOTKA MAINNYH SLOW W MAINAH tX@RINGA mODELX MAINY
            (            ).                                                .

     tX@RINGA pRIMERY WY^ISLIMYH PO tX@RINGU FUNKCIJ sWQZX WY^ISLIMOSTI PO tX@RINGU
                .                                         .

     S ^ASTI^NOJ REKURSIWNOSTX@ tEZIS tX@RINGA
                                .                .


   tO^NOE OPISANIE KLASSA REKURSIWNYH FUNKCIJ WMESTE S TEZISOM ~ER^A DAET ODNO IZ WOZ-
MOVNYH REENIJ OB UTO^NENII PONQTIQ ALGORITMA. oDNAKO \TO REENIE NE WPOLNE PRQMOE, TAK
KAK PONQTIE WY^ISLIMOJ FUNKCII QWLQETSQ WTORI^NYM PO OTNOENI@ K PONQTI@ ALGORITMA.
sPRAIWAETSQ, NELXZQ LI UTO^NITX NEPOSREDSTWENNO SAMO PONQTIE ALGORITMA I, UVE ZATEM, PRI
EGO POMO]I OPREDELITX TO^NO KLASS WY^ISLIMYH FUNKCIJ? |TO BYLO SDELANO pOSTOM I tX@-
RINGOM W 1936{1937 GG. NEZAWISIMO DRUG OT DRUGA I PO^TI ODNOWREMENNO S RABOTAMI ~ER^A.
oSNOWNAQ MYSLX pOSTA I tX@RINGA ZAKL@^ALASX W TOM, ^TO ALGORITMI^ESKIE PROCESSY | \TO
PROCESSY, KOTORYE MOVET SOWERATX PODHODQ]E USTROENNAQ \MAINA". w SOOTWETSTWII S \TOJ
MYSLX@ IMI BYLI OPISANY W TO^NYH MATEMATI^ESKIH TERMINAH DOWOLXNO UZKIE KLASSY MAIN,
NO NA \TIH MAINAH OKAZALOSX WOZMOVNYM OSU]ESTWITX ILI IMITIROWATX WSE ALGORITMI^ES-
KIE PROCESSY, KOTORYE KOGDA-LIBO OPISYWALISX MATEMATIKAMI. aLGORITMY, OSU]ESTWIMYE NA
UPOMQNUTYH MAINAH, BYLO PREDLOVENO RASSMATRIWATX KAK MATEMATI^ESKIH \PREDSTAWITELEJ"
WOOB]E WSEH ALGORITMOW. bYLO DOKAZANO, ^TO KLASS FUNKCIJ, WY^ISLIMYH NA \TIH MAINAH, W
TO^NOSTI SOWPADAET S KLASSOM WSEH REKURSIWNYH FUNKCIJ. tEM SAMYM BYLO POLU^ENO E]E ODNO
FUNDAMENTALXNOE PODTWERVDENIE TEZISA ~ER^A. w NASTOQ]EE WREMQ WSE ALGORITMY \TOGO KLASSA
NAZYWA@TSQ PROSTO MAINAMI tX@RINGA.
   2.1. oPREDELENIE MAINY tX@RINGA. mAINOJ tX@RINGA T NAZYWAETSQ TROJKA MNO-
VESTW T = hA
 Q
 P i, GDE:
   A = A(T) = fa0
 a1
 : : :
 am g | WNENIJ ALFAWIT MAINY T (OBY^NO a0 = 0, a1 = 1)
   Q = Q(T) = fq0
 q1
 : : :
 qm g | ALFAWIT WNUTRENNIH SOSTOQNIJ ILI WNUTRENNIJ ALFAWIT
MAINY T
   P = P (T) = fT(i
 j) j i = 1
 : : :
 n j = 0
 1
 : : :
 mg | PROGRAMMA MAINY T GDE T(i
 j) |
KOMANDY \TOJ PROGRAMMY, PRI^EM, DLQ KAVDOJ PARY (i
 j) SU]ESTWUET ODNA EDINSTWENNAQ KOMANDA
T(i
 j), KOTORAQ IMEET ODIN IZ WIDOW:
                                              qiaj ! qk al 

                                              qiaj ! qk R

                                              qiaj ! qk L:

    2.2. mAINNYE SLOWA (KONFIGURACII). mAINNYM SLOWOM ILI KONFIGURACIEJ NAZY-
WAETSQ WSQKOE SLOWO WIDA Cqkal B, GDE 0  k  n, 0  l  m, A C, B | NEKOTORYE SLOWA (BYTX
MOVET, PUSTYE) W ALFAWITE A.
    dLQ MAINNOGO SLOWA M = Cqiaj B, 0  i  n, 0  j  m, MAINY tX@RINGA T ^EREZ MT0
OBOZNA^IM SLOWO, KOTOROE POLU^ITSQ IZ SLOWA M PO SLEDU@]IM NIVE PRAWILAM 1{2.
   1. dLQ i = 0 MT0 = M.
   2. dLQ i > 0.
       (a) eSLI T (i
 j) = (qiaj ! qk al ), TO MT0 = Cqk al B.
       (b) eSLI T (i
 j) = (qiaj ! qk R), TO:
             i. ESLI B NE PUSTO, TO MT0 = Caj qk B
            ii. ESLI B PUSTO, TO MT0 = Caj qk a0 .
       (c) eSLI T (i
 j) = (qiaj ! qk L), TO:
             i. ESLI C NE PUSTO I C = C1 as, TO MT0 = C1qk asaj B
            ii. ESLI C PUSTO, TO MT0 = qk a0 aj B.

                                               131