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

gLAWA   VII.   oSNOWY TEORII ALGORITMOW

pRIMER 4. lEGKO UBEDITXSQ W TOM, ^TO SHEMA N. A. m.:
    0b ! 1        a0 ! 0a   0a ! 0b
    1b ! 2        a1 ! 1a   1a ! 1b
    2b ! 3        a2 ! 2a   2a ! 2b
    3b ! 4        a3 ! 3a   3a ! 3b
    4b ! 5        a4 ! 4a   4a ! 4b
    5b ! 6        a5 ! 5a   5a ! 5b
    6b ! 7        a6 ! 6a   6a ! 6b
    7b ! 8        a7 ! 7a   7a ! 7b
    8b ! 9        a8 ! 8a   8a ! 8b
    9b ! b0        a9 ! 9a   9a ! 9b
    b ! 1                   I! a
NORMALXNO WY^ISLQET FUNKCI@ f(x) = x + 1 W DESQTIRI^NOJ SISTEME S^ISLENIQ (W ALFAWITE
X = f0
 1
 2
 3
 4
 5
 6
 7
 8
9g). zDESX W KA^ESTWE RASIRENIQ X ALFAWITA X RASSMATRIWAETSQ ALFA-
WIT X = X Sfa
 bg.
   3.5. pRINCIP NORMALIZACII mARKOWA. sOZDATELEM TEORII NORMALXNYH ALGORITMOW
QWLQETSQ SOWETSKIJ MATEMATIK a. a. mARKOW (1903{1979). iM BYLA WYDWINUTA ESTESTWENNO-
NAU^NAQ GIPOTEZA, PODOBNAQ TEZISAM ~ER^A I tX@RINGA. oNA POLU^ILA NAZWANIE PRINCIP NORMA-
LIZACII mARKOWA.
pRINCIP NORMALIZACII mARKOWA. ~ASTI^NAQ ^ISLOWAQ FUNKCIQ QWLQETSQ WY^ISLIMOJ TOG                 -
DA I TOLXKO TOGDA, KOGDA ONA QWLQETSQ NORMALXNO WY^ISLIMOJ.
    oTMETIM, ^TO a. a. mARKOWYM VE DOKAZANO, ^TO KLASS NORMALXNO WY^ISLIMYH FUNKCIJ SOW-
PADAET S KLASSOM ^ASTI^NO REKURSIWNYH FUNKCIJ (I, SLEDOWATELXNO, S KLASSOM WY^ISLIMYH PO
tX@RINGU FUNKCIJ). iZ \TOGO REZULXTATA WYTEKAET \KWIWALENTNOSTX PRINCIPA NORMALIZACII
mARKOWA TEZISAM ~ER^A I tX@RINGA. |TO OZNA^AET, ^TO TEORII REKURSIWNYH FUNKCIJ, MAIN
tX@RINGA I NORMALXNYH ALGORITMOW mARKOWA RAWNOSILXNY. w RAZNOE WREMQ W RAZNYH STANAH
U^ENYE NEZAWISIMO DRUG OT DRUGA, IZU^AQ INTUITIWNOE PONQTIE ALGORITMA I ALGORITMI^ESKOJ
WY^ISLIMOSTI, SOZDALI TEORII, OPISYWA@]IE DANNOE PONQTIE, KOTORYE OKAZALISX RAWNOSILXNY-
MI. eSLI BY ODIN IZ \TIH KLASSOW OKAZALSQ IRE KAKOGO-LIBO DRUGOGO, TO SOOTWETSTWU@]IJ TEZIS
~ER^A, tX@RINGA ILI mARKOWA BYL BY OPROWERGNUT. nAPRIMER, ESLI BY KLASS NORMALXNO WY-
^ISLIMYH FUNKCIJ OKAZALSQ IRE KLASSA REKURSIWNYH FUNKCIJ, TO SU]ESTWOWALA BY NORMALXNO
WY^ISLIMAQ, NO NE REKURSIWNAQ FUNKCIQ. w SILU EE NORMALXNOJ WY^ISLIMOSTI I PRINCIPA NORMA-
LIZACII mARKOWA ONA BYLA BY ALGORITMI^ESKI WY^ISLIMA W INTUITIWNOM PONIMANII ALGORITMA,
I PREDPOLOVENIE OB EE NEREKURSIWNOSTI OPROWERGALO BY TEZIS ~ER^A. oDNAKO \TI KLASSY FUNK-
CIJ SOWPADA@T, ^TO SLUVIT E]E ODNIM KOSWENNYM PODTWERVDENIEM TEZISOW ~ER^A, tX@RINGA
I PRINCIPA NORMALIZACII mARKOWA. oTMETIM, ^TO SU]ESTWU@T E]E I DRUGIE WARIANTY TEORIJ
ALGORITMOW, FORMALIZU@]IH INTUITIWNOE PONQTIE ALGORITMA, I DLQ WSEH NIH TAKVE DOKAZANA
IH RAWNOSILXNOSTX S RASSMOTRENNYMI TEORIQMI.
   3.6. nOWYE TERMINY. pODSLOWA I WHOVDENIQ SLOW W DRUGIE SLOWA. mARKOWSKAQ PODSTA-
NOWKA, FORMULA MARKOWSKOJ PODSTANOWKI. pRIMENIMYE I NEPRIMENIMYE PODSTANOWKI K DANNO-
MU SLOWU. zAKL@^ITELXNYE PODSTANOWKI. sHEMA NORMALXNOGO ALGORITMA. nORMALXNYJ ALGORITM
(mARKOWA), OPREDELQEMYJ DANNOJ SHEMOJ. pERERABOTKA N. A. m. ODNOGO SLOWA W DRUGOE. pRIME-
NIMYJ I NEPRIMENIMYJ N. A. m. K DANNOMU SLOWU. nORMALXNO WY^ISLIMYE FUNKCII. pRINCIP
NORMALIZACII mARKOWA.
   3.7. kONTROLXNYE WOPROSY.
  1. sKOLXKO WHOVDENIJ IMEET SLOWO aa W SLOWO aaaa?

                                               140