Alisher navoiy nomidagi samarqand davlat universiteti mexanika-matematika fakulteti

tatbiq etilmaydi deb ataladi. 
Misollar. 
1- m i s o l . 
A
 alfavit 
}
,
{ c
b
 ko‘rinishda berilgan bo‘lsin. Quyidagi algoritm 
sxemasini ko‘ramiz:   
 







c
c
b
. 
Bu  sxema  bilan  berilgan 
U
  normal  algoritm 
A
  alfavitdagi  tarkibiga  kamida  bitta 
b
  harfi 
kirgan har qanday 
P
 so‘zni shunday o‘zgartiradiki, bu so‘z 
P
 so‘zdan uning tarkibiga eng chapdan 
kirgan 
b
 so‘zni o‘chirish natijasida hosil bo‘ladi. 

 
107 
 
Haqiqatan  ham, 
P
  so‘z  tarkibiga  eng  chapdan  kirgan 
b
  so‘zdan  chaproqda  turgan  har 
qanday 
c  harfni 
c
c   oddiy o‘rniga qo‘yish formulasi yana  c  harfiga o‘tkazadi va eng chapdagi 
b
 
harfini 



b
 natijaviy o‘rniga qo‘yish formulasi 
  natijaviy bo‘sh so‘zga o‘zgartiradi. Masalan, 
agar 
ccbbc
P 
 bo‘lsa, u holda 
Q
P


 bo‘ladi, bu yerda 
ccbc
Q 
. 
U
 algoritm bo‘sh so‘zni o‘z-
o‘ziga o‘zgartiradi. 
U
  algoritmi 
b
  harfi  kirmagan  bo‘sh  bo‘lmagan  so‘zlarga tatbiq  etilmaydi.  Haqiqatan  ham, 
agar 
P
  so‘z  faqat 
c   harflardan  iborat  bo‘lsa,  u  holda 
c
c    oddiy  o‘rniga  qo‘yish  formulasi  uni 
yana  o‘ziga  aylantiradi.  U  holda  hamma  vaqt 
P
P 
  bo‘ladi  va  biz  natijaviy  o‘rniga  qo‘yish 
formulasiga kela olmaymiz, ya’ni jarayon cheksiz davom etadi. ■ 
2- m i s o l . 
A
 alfavit 
}
,...,
,
{
1
0
n
a
a
a
 ko‘rinishda berilgan bo‘lsin. Quyidagi sxemani ko‘ramiz 













n
a
a
a
...
1
0
 
Bu sxemani 
)
(



i
a
i
 (
A
a
i

) ko‘rinishida ham yozish mumkin. Bu sxema 
A
 alfavitdagi 
har qanday so‘zni bo‘sh so‘zga o‘zgartiradigan 
U
 normal algoritmdir. 
Masalan, 





3
2
3
1
2
3
1
2
1
0
3
1
2
1
:
a
a
a
a
a
a
a
a
a
a
a
a
a
a
U
 
va 
oxiri 


:
U
. 
Demak, 


)
(
0
3
1
2
1
a
a
a
a
a
U
. ■ 
3- m i s o l . 
A
 alfavit 
1
S  harfdan iborat bo‘lsin. Bu harfni 1 bilan belgilaymiz. Har qanday 
n  
natural  son  uchun  induksiya  metodi  bo‘yicha 
1
0    va 
1
1
n
n


  larni  aniqlaymiz.  Shunday  qilib, 
11
1 
, 
111
2 
 va hokazo. 
n
 so‘zlar raqamlar deb aytiladi. 
Ushbu 
1
{



 
sxema  orqali  berilgan 
U
  normal  algoritmni  aniqlaymiz. 
A
  alfavitidagi  har  qanday 
P
  so‘z  uchun 
P
P
U
1
)
(

  ga  ega  bo‘lamiz.  Xususiy  holda,  har  qanday 
n   natural  son  uchun   
1
)
(

 n
n
U
.  Har 
qanday 
P
  so‘z 
   bo‘sh  so‘zning  kirishidan  boshlanishini  (chunki 
P
P


)  eslasak,  keltirilgan 
algoritmning to‘g‘riligiga ishonamiz. ■ 
 
Markov bo‘yicha qismiy hisoblanuvchi va hisoblanuvchi funksiyalar 
 
Markov  bo‘yicha  qismiy  hisoblanuvchi  va  hisoblanuvchi  funksiya  tushunchalari. 
U
  va 
K
 
algoritmlar, 
P
  esa  so‘z  bo‘lsin.  Agar 
U
  va 
K
  algoritmlarning  ikkalasi  ham 
P
  so‘zga  tatbiq 
etilmaydigan  yoki  ikkalasi  ham  unga  tatbiq  etiladigan  va  keyingi  holda 
)
(
)
(
P
K
P
U

  bo‘lsa,  bu 
holatni 
)
(
~
)
(
P
K
P
U

 ko‘rinishda ifodalaymiz. 
Umuman, agar 
C
 va 
D
 biror ifodalar bo‘lsa, u holda 
D
C 
~
 munosabat quyidagini bildiradi: 
yo ikkala ifoda ham aniqlanmagan, yoki ikkalasi ham aniqlangan va ular bir xil obyektni belgilaydi. 
1- t a ’ r i f . Agar 
A
 alfavitdagi istalgan 
P
 so‘z uchun 
)
(
~
)
(
P
K
P
U

 bo‘lsa, u holda 
U
 va 
K
 algoritmlar 
A
 ga nisbatan 
A
 alfavit ustida batamom (tamomila) ekvivalent deb ataladi. 

 
108 
 
Agar 
P
  berilgan 
A
  alfavitdagi  so‘z  bo‘lganida  har  doim 
)
(
~
)
(
P
K
P
U

  hamda  hech 
bo‘lmaganda 
)
(P
U
 yoki 
)
(P
K
 so‘zlarning birortasi aniqlangan va yana 
A
 ning so‘zi bo‘lsa, 
U
 va 
K
 algoritmlar 
A
 alfavitga nisbatan ekvivalent deb ataladi. 
M
 ushbu 
}
,
1
{   alfavit, 
  hamma natural sonlar to‘plami,   esa  n  
argumentli  qismiy  effektiv  hisoblanuvchi  arifmetik  funksiya,  ya’ni 
n
   to‘plamning  ayrim  qism 
to‘plamini 
 ga akslantiruvchi funksiya bo‘lsin. 

B
 
orqali 
hech 
bo‘lmaganda 
bir 
tomoni 
aniqlangan 
holda 
har 
doim 
)
,...,
,
(
)
)
,...,
,
(
(
2
1
2
1
n
n
k
k
k
k
k
k
B



  tenglikni  o‘rinli  qiladigan 
M
dagi  algoritmni  belgilaymiz.  Bu 
algoritm 
)
,...,
,
(
2
1
n
k
k
k
 so‘zdan farq qiluvchi boshqa so‘zlarga tatbiq etilmaydi deb faraz qilamiz. 
2-  t a ’ r i f .  Agar 
M
  ustida 
M
ga  nisbatan 

B
ga  batamom  ekvivalent  bo‘lgan  normal 
algoritm mavjud bo‘lsa, u holda 
  Markov bo‘yicha qismiy hisoblanuvchi funksiya deb ataladi. 
3- t a ’ r i f . Agar 
  funksiya har qanday  n  natural son uchun (hamma joyda) aniqlangan va 
Markov bo‘yicha qismiy hisoblanuvchi funksiya bo‘lsa, u 
holda u Markov bo‘yicha hisoblanuvchi funksiya deb ataladi. 
Markov bo‘yicha qismiy  hisoblanuvchi  funksiya tushunchasi  bilan qismiy rekursiv  funksiya 
tushunchasi  hamda  Markov  bo‘yicha  hisoblanuvchi  funksiya  tushunchasi  bilan  umumrekursiv 
funksiya tushunchalari ekvivalentdir. 
Yuqoridagi tasdiqni tasdiqlovchi quyidagi teoremani isbotsiz keltiramiz. 
1-  t o r e m a .  Har  qanday  qismiy  rekursiv  funksiya  Markov  bo‘yicha  qismiy  hisoblanuvchi 
funksiya bo‘ladi va har qanday umumrekursiv funksiya Markov bo‘yicha hisoblanuvchi funksiyadir. 
Quyidagi teoremalarni ham isbotsiz keltiramiz. 
2-  t o r e m a .  Agar 
A
  alfavit  ustidagi 
U
  algoritm  bo‘yicha, 
U
   funksiya  qismiy  rekursiv 
(rekursiv) bo‘lsa, u holda 
A
 alfavit ustida 
A
ga nisbatan 
U
 algoritmga batamom ekvivalent bo‘lgan 
normal algoritm mavjuddir. 
3- t o r e m a . Agar 
U
 algoritm 
A
 alfavit ustidagi normal algoritm bo‘lsa, u holda 
U
  qismiy 
rekursiv  funksiya  bo‘ladi;  agar,  bundan  tashqari, 
U
  algoritm 
A
  alfavitdagi  har  qanday  so‘zga 
tatbiq etiladigan bo‘lsa, u holda 
U
  umumrekursiv funksiya bo‘ladi.  
N a t i j a .  Agar berilgan 
  qismiy funksiya Markov bo‘yicha qismiy hisoblanuvchi funksiya 
bo‘lsa, u qismiy rekursiv funksiya ham bo‘ladi va agar 
  Markov bo‘yicha hisoblanuvchi funksiya 
bo‘lsa, u holda 
  umumrekursiv funksiya hamdir. 
Teoremalar va natijaning isbotini o‘rganishni o‘quvchiga topshiriq sifatida havola qilamiz
44
. 
Normallashtirish (normalizasiya) prinsipi. Yuqorida keltirilgan 1- teorema  va  natija  Markov 
bo‘yicha qismiy hisoblanuvchi funksiya tushunchasi bilan qismiy rekursiv funksiya (xuddi shunday 
Markov bo‘yicha hisoblash bilan rekursivlik) tushunchasining ekvivalentligini ko‘rsatadi. 
O‘z  navbatida  Chyorch  tezisi  bo‘yicha  hisoblanuvchanlik  tushunchasi  bilan  rekursivlik 
tushunchasi  (qismiy  effektiv  hisoblanuvchanlik  tushunchasi  qismiy  rekursivlik  tushunchasiga) 
ekvivalentdir. A.A.Markov algoritmlar atamasida normallashtirish (normalizasiya) prinsipini yaratdi: 
                                                
44
 Мендельсон Э. Введение в математическую логику. М.: Наука. 1976. 

 
109 
 
A
  alfavitdagi  har  qanday  algoritm 
A
ga  nisbatan 
A
  ustidagi  biror  normal  algoritmga  batamom  
ekvivalentdir. 
Chyorch  tezisi  yordamida  normallashtirish  prinsipining  ekvivalentligi  aniqlandi.  Haqiqatan 
ham,  Chyorch  tezisi  to‘g‘ri  va 
A
  alfavitda 
U
  algoritm  berilgan  bo‘lsin.  Unga  mos  keladigan 
U
  
funksiya  qisman  effektiv  hisoblanuvchi  bo‘ladi.  U  holda,  Chyorch  tezisiga  asosan, 
U
   qismiy 
rekursiv  funksiyadir.  Demak,  2-  teoremaga  ko‘ra, 
U
  algoritm 
A
  ustidagi  biror  normal  algoritmga 
A
ga  nisbatan  batamom  ekvivalentdir.  Shunday  qilib,  agar  Chyorch  tezisi  to‘g‘ri  bo‘lsa,  u  holda 
Markovning normallashtirish prinsipi ham to‘g‘ridir.  
Endi normallashtirish prinsipi to‘g‘ri va 
  ixtiyoriy qisman effektiv hisoblanuvchi funksiya, 

B
 esa 
  funksiyaga mos keluvchi 
M
dagi algoritm bo‘lsin. Normallashtirish prinsipiga asosan 

B
 
algoritm 
M
  ustidagi  biror  normal  algoritmga 
M
ga  nisbatan  batamom  ekvivalentdir.  Demak, 
  
funksiya  Markov  bo‘yicha  qisman  hisoblanuvchi  funksiyadir.  U  holda  olingan  natijaga  ko‘ra 
  
qisman rekursiv (rekursiv) funksiya bo‘ladi. Shunday qilib, Markovning normallashtirish prinsipidan 
Chyorch tezisini keltirib chiqardik. 
Ma’lumki,  algoritm  va  effektiv  hisoblanuvchi  funksiya  tushunchalari  intuitiv  tushunchalar 
bo‘lganligi uchun biz Markovning normallashtirish prinsipi va Chyorch tezisining to‘g‘riligini isbot 
qila olmaymiz. 
Shuni  ham  ta’kidlash  kerakki,  Chyorchning 
 -hisoblanuvchanlik  nazariyasi  va  Postning 
normal  sistemalar  nazariyasidan  kelib  chiqadigan  tushunchalar  ham qisman  rekursiv  funksiya  yoki 
normal algoritm tushunchalariga ekvivalent bo‘ladi. 
 
5-ilova 
 
6-ilova 
Insert texnikasi bo`yicha mavzuni o`qib 
chiqing va jadvalni to`ldiring. 
 
№ 
Asosiy tushunchalar 
Belgi 
1. 
Universal usul. 
 
2. 
Tyuring tezisi. 
 
3. 
Alfavit. Simvollar. 
 
4. 
Harflar. 
 
5. 
Bo‘sh so‘z. 
 
6. 
Algoritm sxemasi. 
 
7. 
Ekvivalent algoritmlar. 
 
 
 
Insert jadvali qoidasi 
 
 
 
 
 
                  
 
 
 
XULOSA 
1.Algoritmlar nazariyasining asosiy gipotezasining mohiyatini o’rganildi; 
2.Markov normal algoritmining amallari va ularni bajarilish jarayonini o’rganildi; 
3.Markov bo’yicha hisoblanuvchi funksiyalarga misollar keltirib izohlab berildi. 
    –   avval olgan bilimiga to’g’ri keladi. 
+    –   yangi ma’lumot 
--    –   olgan bilimiga qarama-qarshi 
?     –   tushunarsiz (aniqlanishi zarur   
            bo’lgan ma’lumotlar) 

 
110 
 
Sinov savollari 
 
1. 
A
  alfavit  va  bu  alfavitda  ixtiyoriy 
Q   so‘z  berilgan  bo‘lsin.  Quyidagi  sxemalar  orqali  berilgan 
normal algoritmlarning ishini ifodalang: 
a) 
Q



{
; 
b) 
}
{


A
B 
 alfavitidagi sxema, bu yerda 
A


: 











;
,
),
(





Q
A
a
 
d) 









;
),
(
Q
A


 
e) 
}
1
{

A
B 
 alfavitdagi sxema: 

1


 
})
1
{
(

 A

 

1


. 
2. 
f  funksiyasi qisman rekursiv funksiya bo‘lmasligini isbot qiling: 
a) 




holda;
 
aks
,
0
,
lsa
bo'
 
aniqlangan
)
(
agar
,
1
)
,
(
y
y
x
f
x

 
b) 




holda;
 
aks
,
0
,
lsa
bo'
 
aniqlangan
)
(
agar
,
1
)
(
x
x
f
x

 
d) 




holda;
 
aks
,
0
,
lsa
bo'
 
aniqlangan
)
(
agar
),
(
)
,
(
y
y
y
x
f
x
x


 
e) 





holda;
 
aks
,
0
,
lsa
bo'
 
)
(
agar
,
1
)
,
,
(
z
y
z
y
x
f
x

 
f) 







holda.
 
aks
,
0
,
lsa
bo'
)
(
        
          
          
lsaki,
bo'
 
mavjud
shunday
agar 
,
1
)
,
,
(
z
y
у
z
y
x
f
x

 
3. 
f  funksiya qisman rekursiv funksiya bo‘lish yoki bo‘lmasligini aniqlang: 
a) 





holda;
 
aks
,
0
,
lsa
bo'
1
)
(
agar
,
1
)
(
x
x
f
x

 
b) 




holda;
 
aks
,
0
,
lsa
bo'
 
aniqlangan
)
(
agar
,
an
aniqlanmag
)
(
x
x
f
x

 
d) 






holda;
 
aks
,
0
lsa,
bo'
 
elementi
 
plamining
    to'
qiymatlar
 
funksiya
1
agar
,
1
)
(
x
x
f

 
e) 




holda;
 
aks
,
0
,
lsa
bo'
 
funksiya
 
rekursiv
 
primitiv
)
(
agar
,
1
)
(
y
x
f
x

 

 
111 
 
f) 






holda.
 
aks
,
0
lsa,
bo'
nollar 
 
p
ko'
 
cheksiz
 
a
yoyilmasid
        
agi
sistemasid
 
sanoq
nlik 
o'
 
sonning
agar
,
1
)
(

x
f
 
4.  Markov  bo‘yicha  qismiy  hisoblanuvchi  funksiya  tushunchasi  bilan  qismiy  rekursiv  funksiya 
tushunchasi  hamda  Markov  bo‘yicha  hisoblanuvchi  funksiya  tushunchasi  bilan  umumrekursiv 
funksiya tushunchalari ekvivalentligini o‘rganing. 
K o ‘ r s a t m a .  E.  Mendelsonning  (Мендельсон  Э.  Введение  в  математическую  логику. 
М.: Наука. 1976.) kitobidagi 242-244 va 246-249 sahifalarga murojaat qiling. 
 
Mustaqil ishlash uchun savollar 
1.  Markovning normal algoritmlari deganda nimani tushunasiz? 
2.  Alfavit, simvollar, harflar, so‘z, bo‘sh so‘z tushunchalarini bilasizmi? 
3.  Algoritm ta’rifi qanday berilgan? 
4.  Alfavit ustidagi algoritm deb nimaga aytiladi? 
5.  Alfavitdagi algoritm bilan alfavit ustidagi algoritm bir-biridan qanday farqlanadi? 
6.  Tatbiq etiladigan va etilmaydigan algoritmlar tushunchalarini bilasizmi? 
7.  O‘rniga qo‘yish usuli deganda nimani tushunasiz? 
8.  Algoritm sxemasi nima? 
9.  Normal algoritm va Markov algoritmi bir-biridan farqlanadimi? 
10. Batamom ekvivalent algoritmlar deganda nimani tushunasiz? 
11. Qanday algoritmlar ekvivalent algoritmlar deb ataladi? 
12. Markov bo‘yicha qismiy hisoblanuvchi va hisoblanuvchi funksiyalar deganda nimani tushunasiz? 
13. Qismiy rekursiv funksiya bilan Markov bo‘yiicha qismiy hisoblanuvchi funksiya orasida qanday 
munosabat bor? 
14. Umumrekursiv  funksiya  bilan  Markov  bo‘yicha  hisoblanuvchi  funksiya  orasidagi  munosabatni 
bilasizmi?