17-tema. Algoritm túsigi. Dara rekursiv funkciyalar. Tyuring mashinaları

17-tema. Algoritm túsigi. Dara rekursiv funkciyalar. Tyuring mashinaları 

 

Matematikaniń  dáslepki  rawajlanıw  qádemlerinen  baslap-aq  ,  onda  matematikalıq  xarakterge  iye  bolǵan,  málim  bir  sxema 

járdeminde alıp barılatuǵın esaplaw processleri payda bola basladı. Bir tipli, bir qıylı mazmunǵa iye bolǵan kóp ǵana máseleler bir 

qıylı usıl hám de qádemler járdeminde esaplanatuǵın matematikadaǵı bunday processler algoritmler dep atala basladı.Hár qanday 

matematikalıq  másele  óziniń  “shártleri”  dep  atalıwshı  shamalardıń  bazı  bir  sisteması  hám  onıń  “sheshimi”  dep  atalıwshı 

shamalardıń ekinshi bir sistemasınan ibarat boladı. Matematikalıq máselelerdiń shártleri ádette berilgen bolıp, onıń sheshimin tabıw 

talap etiledi. Bul jerde “shama” túsinigin keń mazmunda túsindiriliwi kerek- sanlar, funkciyalar , matritsalar, aytimlar, formulalar, 

geometriyalıq obyektler hám taǵı basqalar shama túsinigine mısal bola aladı. 

Mısalı. 1) “

a

 hám 

b

 natural sanlarınıń eń úlken uliwma bóliwshi(EÚUB)sin tabıń degen máselede 

a

 hám 

b

 natural sanlar másele 

shártin payda etiwshi shamalar boladı. 

2) “



dx

xe

x

 

anıq emes integralın esaplaw” degen máseleniń shártin 

x

xe

у 

 funkciya payda etedi. 

3) “Matritsalardı kóbeytiw assotciativ ámel ekenligin dálilleń ” degen máselede shártti qálegen úsh 

A

;

B

;

C

 matritsa (shamalar 

sisteması) payda etse, máseleniń sheshimi bolsa 

)

(

)

(

BC

A

C

AB



 teńliginiń orinli ekenliginen ibarat. 

Bul mısallardan hár birine sáykes bolǵan uliwma qásiyet bar ekenligin seziw qıyın emes- hár bir máseleniń shártleri qandayda 

bir  sheksiz  kóplikten  alınǵan  boladı.  Máselen,  1-máseleniń  shártleri  natural  sanlar  kópligi 





...

,

...,

,

3

,

2

,

1

n

N 

  nen  2-máseleniń 

shártleri bir ózgeriwshili haqıyqıy argumentli differensiyalanıwshı funkciyalar kópliginen, 3- máseleniń shárti qálegen 

P

 maydan 

(yamasa  associativ  koltso)  retinde  qaralıp  atırǵan  matritsalar  kópligi 

)

(P

M

  kópliginen  alınatuǵinlıǵı  málim  .

A

  qálegen 

matematikalıq  másele 

n

a

a

a

...,

,

,

2

1

 

anıq 

Q

  kópliginen  alinǵan  shártleri  bolsa,  onda  shártleri(máselen, 

n

b

b

b

...,

,

,

2

1

)  usi  kóplikten 

alinǵan hám 

A

 másele menen bir qiyli bolǵan sheksiz kóp máseleler bar boladı. Bunnan, joqarıdaǵı 1-másele sheksiz kóp tómendegi 

bir tiptegi, bir qiyli hár túrdegi máselelerdi óz ishine aladi: “

330

 hám 

480

 niń EÚUBsin tabiń ”, “

775

 hám 

220

 nińEÚUBsin tabiń 

”, ”

141

  hám 

233

  tiń  EÚUBsin  tabiń  ”  hám  t.  b. (

a

  hám 

b

  lardiń  ornina qálegen  natural  sanlar  qoyiladi). Solay  etip, hár  bir  A 

matematikalıq  másele  ózinde  sheksiz  kóp  bir  túrdegi  máselelerdi  biriktiredi.  Barlıq  bir  túrdegi  máseleler  kópligi  “uluwmalıq 

másele” delinedi. 

Bir tiptegi máseleniń jáne bir uliwmalıq qásiyeti sonnan ibarat, bul máseleler bir túrdegi jol, usil, yaǵniy bir qıylı algoritmler 

járdeminde sheshiledi. Usinday jáne bir mısaldı qarayıq. 

4) “

0



a

  hám 

c

b

a

,

,

  lar haqıyqıy  sanlar bolsa  , onda 

0

2







c

bx

ax

  teńlemesin sheshiń ”. Bunnan 

b

a,

  hám 

c

  larǵa qálegen 

haqıyqıy mánisler berilgende 

)

0

( 

a

 sheksiz kóp bir túrdegi máseleler payda bolıp , olardiń hár biri bir ǵana jol menen sheshiledi: 

 

a

ac

b

b

x

2

4

2

2

,

1









 

Joqarıdaǵı formuladan kórinip turǵanınday-aq, teńlemeniń korenin tabiw shekli qádemde orinlanadı: 

b

nı kvadratqa kóteriw , 

a

 

ni 

c

 ǵa , 

ac

 nı bolsa 

4

 ke kóbeytiw, 

2

b

 tan 

ac

4

 nı ayırıw , 

ac

b

4

2



 dan kvadrat korenin shıǵarıw, 

)

( b



 ǵa

ac

b

4

2



  nı 

qosıw(ayırıw), 

a

 ni 

2

 ge kóbeytiw hám de aqırında -

b

±

ac

b

4

2



 nı 

a

2

 ǵa bóliw sıyaqlı jánede usi qádemlerdı orinlaw bolip 

tabıladı. 

 Jáne  de,  joqaridaǵı  1-máselege  qaytamiz  .  Bizge  málim,  eki  natural  sannıńEÚUBsin  tabiw  ushın  Evklid  algoritiminen 

paуdalanamız. Evklid algoritminiń qádemleri tómendegilerden ibarat: 

1

0

. 

)

0

,

0

(







b

a

b

a

 bolsa, olardıń EÚUBsi usi sanlardıń biri boladı.  

2

0

. Уеger 

b

a 

 bolip, máselen 

b

a 

 bolsa, onda 

a

 sani b ǵa bólinedi: 

 

)

1

(

).

0

(

1

1

1

b

r

r

bq

a









  

Bunda 

0

1



r

 bolsa, onda algoritm óz jumisin toqtatadı hám EÚUBsi 

b

 ekenligin kórsetetedi , 

0

1



r

 bolsa , onda algoritm óz 

jumisin dawam ettiredi. 

3

0

. 

b

 sanı 

1

r

ge

 

bólinedi: 

 

)

2

(

).

0

(

1

2

2

2

1

r

r

r

q

r

b









 

 Уеgerde 

0

1



r

 bolsa, onda algoritm óz jumisin toqtatip, EÚUB 

1

r

 ekenligin kórsetedi, al 

0

2



r

 bolsa, onda algoritm óz jumısın 

dawam ettiredi. 

4

0

. 

1

r

 qaldiq 

2

r

 ge bólinedi: 

 

)

3

(

).

0

(

2

3

3

3

2

1

r

r

r

q

r

r









 

 Bul  proces  shekli  qádemnen  soń  toqtaydi,  sebebi 

),...

3

(

),

2

(

),

1

(

lardan  kórinip  turǵanday 

,....

,

,

3

2

1

r

r

r

 

qaldiqlar 

....

,

3

2

1







r

r

r

 

shártlerin qanaatlandıradı hám ol 

k

 qádemnen soń 

0



k

r

 boladı. Bunnan keyin algoritm óz jumisin toqtatip, EÚUB si 

1



k

r

 ekenligin 

bazıbir jupliqlar ushin qisqa bolsa, al bazıbir jupliqlari ushin uzaq dawam etiwi múmkin. .Biraq, bul algoritmniń qádemler sanı 

shekli bolıp, algoritm natural sannıńqálegen juplıqları ushin onıń EÚUB sin esaplap beredi. Solay etip, evklid algoritmi de sheksiz 

kóp juplıqlar ushin EÚUBsin tabıw máselesin sheshedi. 

Joqarıdaǵı qaralǵan máselelerden kórinip turǵanday-aq ,hár bir algoritmlik process sheksiz kóp bir qıylı mazmunlı máselelerdi 

sheshiwge qollaniladı eken .Hár bir algoritm qandayda bir shamanıń baslanǵish sisteması (máseleniń shártleri) ústinde jumıs alıp 

barlıwı hám de diskret rejimde islep , hár bir gezektegi waqıt momentinde (aralıǵında) shamalardıń sistemasınıń málim bir nızami 

(dástúri)na tiykarlanıp shamalardıń keyingi (taza) sistemasına ótkizedi.  



1

máselede 

16

,

39





b

a

  bolsin.  Bul  máselede  shamalardıń  dáslepki  sisteması 

)

16

,

39

(

  juplıǵı  boladı. 

16

39 

  hám 

16

39 

 

bolǵanlıǵı ushin algoritmniń birinshi qádemi 

)

16

7

0

,

7

2

16

39











 dan keyin shamalardıń keyingi sisteması 

)

7

,

2

,

16

,

39

(

 payda 

boladı 

).

7

,

2

(

1

1



 r

q

 

0

1



r

  bolǵanlıǵı  ushin  ekinshi  qádem 

,

2

2

7

16







 

2

,

2

,

7

2

0

2

2









r

q

  en  keyin  shamalardıń  úshinshi 

sisteması 

)

2

,

2

,

7

,

16

(

 payda boladı. 

0

2



r

 bolǵanlıǵı ushin algoritmniń úshinshi qádemi 

1

,

3

,

2

1

0

,

1

3

2

7

3

3















r

q

 den sońǵı 

taza sistema 

)

1

,

3

,

2

,

7

(

 payda boladı. 

Aqırında , 

0

3



r

 bolǵanlıǵı ushin algoritmniń tórtinshi qádemi 

0

,

2

,

0

2

1

2

4

4











r

q

 den keyin shamalardiń aqirǵı sisteması

)

0

,

2

,

1

,

2

(

 payda boladı. Bul procesti shártli túrde tómendegishe ańlatiw múmkin: 

 



)

16

,

39

(

)

7

,

2

,

16

,

39

(

 



 

)

2

,

2

,

7

,

16

(



)

1

,

3

,

2

,

7

(



)

0

,

2

,

1

,

2

(

.  

Algoritmniń islew processinde qandayda bir waqıt momentinde (baslanǵish momentin basqa) payda etilgen shamalar sisteması 

aldińǵı  waqıt  momentinde  payda  etilgen  shamalar  sisteması  arqalı  bir  mánisli  anıqlanadı  .  Bazıbir  algoritmler  qandayda  bir 

obyektler (shamalar)sisteması ústinde islengende bazıbir qádemde payda bolǵan sistemadan keyingi sistemaǵa ótiw usılı nátiyje 

bermewi de múmkin. Bunda algoritm shamalarınıń baslanǵı sh sistemasın “aniq emeslikke” qayta isleydi. Máselen 

0

2







c

bx

ax

 

teńlemesiniń korenlerin tabiwda tek haqıyqıy korenler menen shegaralanǵanı anıq, onda 

0

4

2



 ac

b

 bolǵanda algoritm nátiyje 

bermeydi. 

Algoritmdi bazıbir shamalar sistemasına qollanǵanda algoritmlik processte tómendegi úsh jaǵdaybolıwı múmkin: 

1.  Algoritmniń  islew  processinde  birinshi  jaǵday  ekinshi  jaǵday  menen  almastırılǵanda  da,  bul  process  hesh  qashan 

toqtamaydı. 

2. Algoritmlik processte bazıbir qádemnen soń sonday jaǵday júz beriwi múmkin, onda payda bolǵan obektler sistemasına 

jánede qayta islew nızamın (qádesin) qollanıp bolmaydı hám de algoritm hesh qanday nátiyje bermey óz jumısın toqtatadı. 

3. Algoritmlik process bazıbir qádemnen soń aqırǵı jaǵdayǵa keledi hám óz jumısın toqtatadı. 

Solay  etip,  algoritmlik  processti  úshinshi  jaǵdayǵa  támiyinlew  ushin,  onıń  dáslep  algoritm  qollanıwı  múmkin  bolǵan 

obyektlerge qarata isletiliwi kerek – olar natural sanlar, ratsional sanlar, kóp aǵzalilar, matritsalar, bazıbir algoritmdegi sózler, 

teoremalar, geometriyalıq figuralar hám t. b. lardan ibarat. 

Algoritm  haqqındaǵı  kóz-qaraslar,  ásirimizdiń  30-jıllarında  amerikalı  matematikler  A.Shyursh,  K.Gyudel  hám  S.Klinilar 

algoritm túsinigin rekursiv funkciyalar járdeminde anıqlaw múmkin ekenligin (gipoteza jaǵdayında) kórsetti. 1931 jılı K.Gyudel 

birinshi márte barlıq rekursiv funkciyalar klasın bazıbir formal sistemada anıqlanǵan sanlı funkciyalar klası sıpatında anıqladı. 

1936 jılı A.Shyorsh bul máseleni pútkilley basqasha kóz-qarastan úyrenip, K.Gyudel anıqlaǵan sanlı funkciyalar klasın payda 

etti. Sanlı funkciyalar klasına alıp kelingen ideyalar analizi A.Shyurshge birinshi bolıp tómendegi tezisti járiyalawǵa imkaniyat 

berdi: 

Shyorsh tezisi. Rekursiv funkciya klası argumentlerdiń barlıq mánislerinde anıqlanǵan esaplanıwshı funkciyalar klası menen 

birdey boladı. 

Shyorsh tezisi quramında dál anıqlanbaytuǵın esaplanıwshı funkciya qatnaspaǵanliǵı sebepli , bul tezisti dálillew múmkin 

emes. 

 Joqarıda,  biz  bazıbir  algoritmler  qandayda  bir  baslanǵish  shamalar  sistemasına  qollanǵanda  bul  shamalardı  qayta  islew 

processi  sheksiz  dawam  etiwi,  yaǵniy  algoritm 

n

x

x

x

....,

,

,

2

1

  shamalar  sisteması  “anıq  emeslikke”  ótkızıwin  aytıp  ótken  edik. 

Sheksiz dawam etiwshi proceslerdi qamrap alıw maqsetinde 1936 jılı S.Klini dara rekursiv funkciyalar túsinigin kiritti. 

Klini tezisi. Algoritm járdeminde esaplanıwshı dara funkciyalar klası dara rekursiv funkciyalar klası menen birdey boladı. 

 Bunnan kórinip turǵanınday-aq , Shyorsh tezisi sıyaqlı Klini tezisin de dálillew múmkin emes, sebebi Shyorsh tezisi Klini 

tezisiniń dara jaǵdayı bolıp tabıladı. 

Algoritm túsinigin aniqlaw jolindaǵı izleniwler basqa baǵdarlardı da úyreniwler dawam etip atirǵan уedi. Algoritm túsinigin 

anıqlawǵa hám keyinirek onıń járdeminde esaplanıwshı funkciya túsinigin anıqlawǵa bir-birinen ǵárezsiz biyxabar túrde E.Post 

1939 jılı hám A.Tyuring 1937 jılı уeristi. 

 Post  hám  Tyuring  algoritmlik  processler  málim  bir  qurılmaǵa  iye  bolǵan  “mashina”  orinlaytuǵın  processler  ekenligin 

kórsetti. Olar usi waqıttaǵı matematikadaǵı málim bolǵan barlıq algoritmlik proceslerdi orınlay alatuǵın “abstrakt matematikalıq 

mashinalar”  klasın  payda  etip,  olarǵa  onıń  matematikalıq  atamalar  járdeminde  anıqlamalar  berdi.  Post  hám  Tyuring  usı 

mashinalar  járdeminde  esaplanıwshı  barlıq  funkciyalar  klası  barlıq  dara  rekursiv  funkciyalar  klası  menen  birdey  ekenligin 

kórsetti. Bul Shyorsh tezisiniń jánede tastıyıqlanıwı boldı. 

 Algoritmler teoriyası matematikanıń ishki iqtiyajları nátiyjesinde payda boldı: matematikalıq logika, algebra, matematikalıq 

analiz,  geometriya,  matematika  tiykarları  hám  de  matematikanıń  kóp  ǵana  basqa  tarawları  algoritmler  teoriyasınıń  tiykarǵı 

qollanılatuǵı  n  tarawları  bolıp  tabıladı.  Nátiyjede  Post-Tyuring  mashinaları  júdá  úlken  anıqlıq  penen  elektron  esaplaw 

mashinaları járdeminde modellestirile basladı. Bunnan tısqarı, algoritmler teoriyası ekonomika, lingvistika, psixologiya, miy 

fiziologiyası hám t. b. tarawlarda keń qollanılmaqta.