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

gLAWA   VII.   oSNOWY TEORII ALGORITMOW

    pOLOVIM:
                                      MT(1) = MT0 
                                      MT(n+1) = (MT(n))0 :
   gOWORQT, ^TO MAINA T PERERABATYWAET MAINNOE SLOWO M W M1 , ESLI NAJDETSQ TAKOE
NATURALXNOE ^ISLO n, ^TO MT(n) = M1 . w \TOM SLU^AE BUDEM PISATX:
                                           M)
                                            T M
                                                1

.
    w SLU^AE n = 1 BUDEM PISATX TAKVE
                                           M j= M1 .
   2.3. mODELX MAINY tX@RINGA. pRIWEDENNYE W P. P. VII.2.1.{VII.2.2. ABSTRAKTNYE PO-
NQTIQ PROINTERPRETIRUEM NA IDEALXNOJ (NE REALIZUEMOJ) \MAINE".
   pUSTX IMEEM NEKOTOROE USTROJSTWO, WKL@^A@]EE W SEBQ SLEDU@]IE KOMPONENTY: KONE^NU@
LENTU, UPRAWLQ@]U@ GOLOWKU, MEHANI^ESKOE USTROJSTWO, WNEN@@ I WNUTRENN@@ PAMQTX, PRO-
GRAMMU.
kONE^NAQ LENTA RAZBITA NA KONE^NOE ^ISLO ODINAKOWYH Q^EEK. kAVDAQ Q^EJKA W KAVDYJ MOMENT
WREMENI NAHODITSQ W ODNOM IZ SOSTOQNIJ ai , i = 0
 1
 : : :
 m, TO ESTX W KAVDYJ MOMENT WREMENI W
KAVDOJ IZ Q^EEK ZAPISAN ODIN IZ SIMWOLOW ALFAWITA A = fa0 
 a1
 : : :
 am g WNENEJ PAMQTI.
   kAK PRAWILO, SIMWOL a0 S^ITA@T PUSTYM SIMWOLOM I W KA^ESTWE a0 OBY^NO WYBIRAETSQ SIM-
WOL 0. w KA^ESTWE SIMWOLA a1 , KAK PRAWILO, WYBIRAETSQ SIMWOL 1. w SOOTWETSTWII S PRAWILAMI,
KOTORYE BUDUT W DALXNEJEM PRIWEDENY, K LENTE MOGUT \PRISTRAIWATXSQ" Q^EJKI SLEWA ILI
SPRAWA. pRISTRAIWA@TSQ Q^EJKI W PUSTOM SOSTOQNII. sOSTOQNIE LENTY, SOSTOQ]EJ IZ r Q^EEK, W
KAVDYJ MOMENT WREMENI OPISYWAETSQ SLOWOM aj1 aj2 : : :ajr , GDE ajs | SIMWOL IZ A, ZAPISANNYJ W
s-OJ Q^EJKE LENTY.
wNENQQ PAMQTX PREDSTAWLENA ALFAWITOM A = fa0
 a1
 : : :
 amg I USTROJSTWOM, SPOSOBNYM W
SOOTWETSTWU@]IJ MOMENT WREMENI WPISYWATX SIMWOLY IZ A W Q^EJKI LENTY, STIRAQ PERED \TIM
IH PREDYDU]EE SODERVIMOE.
wNUTRENNQQ PAMQTX | \TO ALFAWIT Q = fq0
 : : :
 qng WNUTRENNIH SOSTOQNIJ MAINY I USTROJ-
STWO, SPOSOBNOE MENQTX ODNO WNUTRENNEE SOSTOQNIE MAINY NA DRUGOE. w KAVDYJ KONKRETNYJ
MOMENT WREMENI MAINA MOVET NAHODITXSQ W ODNOM I TOLXKO W ODNOM WNUTRENNEM SOSTOQNII. sO-
STOQNIE q0 | OSOBOE. eSLI MAINA POPADAET W SOSTOQNIE q0, TO ONA POLNOSTX@ PREKRA]AET SWO@
RABOTU, TO ESTX OSTANAWLIWAETSQ. pO\TOMU q0 NAZYWAETSQ TAKVE STOP-SIMWOLOM , A SOOTWETSTWU-
@]EE SOSTOQNIE | STOP-SOSTOQNIEM ILI ZAKL@^ITELXNYM SOSTOQNIEM. q1 PRINQTO NAZYWATX
ISHODNYM ILI NA^ALXNYM SOSTOQNIEM.
uPRAWLQ@]AQ GOLOWKA UPRAWLQET PROCESSOM PREOBRAZOWANIQ MAINNYH SLOW W MAINE tX@-
RINGA. w KAVDYJ KONKRETNYJ MOMENT UPRAWLQ@]AQ GOLOWKA OBOZREWAET (WOSPRINIMAET) ODNU
I TOLXKO ODNU Q^EJKU LENTY. uPRAWLQ@]AQ GOLOWKA PO SOOTWETSTWU@]IM KOMANDAM MOVET PE-
REDWIGATXSQ WLEWO ILI WPRAWO, MENQTX SODERVIMOE WOSPRINIMAEMOJ Q^EJKI. eSLI PO KAKOJ-TO
KOMANDE UPRAWLQ@]EJ GOLOWKE PREDPISANO PEREDWIVENIE WLEWO (WPRAWO) NA ODNU Q^EJKU, A OBO-
ZREWAEMAQ W DANNYJ MOMENT Q^EJKA BYLA KRAJNEJ SLEWA (SPRAWA), TO MEHANI^ESKIM USTROJSTWOM
(SM. NIVE) K LENTE \PRISTRAIWAETSQ SLEWA" (SPRAWA) DOPOLNITELXNAQ Q^EJKA, W KOTOROJ ZAPISAN
PUSTOJ SIMWOL WNENEGO ALFAWITA.
pROGRAMMU MAINY tX@RINGA BUDEM TRAKTOWATX KAK SOWOKUPNOSTX KOMAND, W SOOTWETSTWII S
KOTORYMI OSU]ESTWLQETSQ RABOTA MAINY.
mEHANI^ESKOE USTROJSTWO PRISTRAIWAET K LENTE PO SOOTWETSTWU@]IM KOMANDAM DOPOLNI-
TELXNYE Q^EJKI I (ILI) PEREDWIGAET UPRAWLQ@]U@ GOLOWKU.
   2.4. rABOTA MODELI MAINY tX@RINGA. sOSTOQNIE MAINY tX@RINGA OPREDELQETSQ
SOSTOQNIEM LENTY, WNUTRENNIM SOSTOQNIEM MAINY I NOMEROM OBOZREWAEMOJ Q^EJKI, TO ESTX
SOSTOQNIE MAINY tX@RINGA POLNOSTX@ OPREDELQETSQ MAINNYM SLOWOM M = Cqiaj B, GDE
Caj B | SOSTOQNIE LENTY, aj | OBOZREWAEMAQ Q^EJKA, qi | WNUTRENNEE SOSTOQNIE MAINY.

                                              132