Altynning algoritmlar nazariyasi fanidan mavzu: tyuring mashinasi va tezisi

2.4.  Tyuring mashinasi yordamida yechiladigan misollar: 

Quyidagi  funksiyalarni  hisoblovchi  algoritmlari  Tyuring  mashinasining  dasturlari 

sifatida ifodalang: 

 

   Dastlab a) misolni yechishdan boshlasak, 

    Tashqi alfavit: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 

    Ichki alfavit: {

0

q

,  

1

q

,  

2

q

,  L, s} 

  

0

q

 - to’xtash holati 

   

1

q

 - dastlabki holat 

 

0

a

 

0 

1 

2 

3 

4 

5 

6 

7 

8 

9 

1

q

 

2 s.  

 

2 s. 

0

q

 

3 s. 

0

q

 

4 s. 

0

q

 

5 s. 

0

q

 

6 s.  

0

q

 

7 s. 

0

q

 

8 s. 

0

q

 

9 s. 

0

q

 

0 L. 

2

q

 

1 L. 

2

q

 

2

q

 

1 s. 

0

q

 

1 s. 

0

q

 

2 s. 

0

q

 

3 s. 

0

q

 

4 s. 

0

q

 

5 s. 

0

q

 

6 s.  

0

q

 

7 s. 

0

q

 

8 s. 

0

q

 

9 s.  

0

q

 

0 L. 

2

q

 

 

   Endi shu Tyuring mashinasi yordamida misol ishlab ko’rsak, 

1-qadam: 

0

a

 

0

a

 

9 

8 

0

a

 

0

a

 

 

2-qadam: 

0

a

 

0

a

 

9 

0 

0

a

 

0

a

 

 

 

---

3-qadam: 

0

a

 

0

a

 

0 

0 

0

a

 

0

a

 

 

4-qadam: 

0

a

 

1 

0 

0 

0

a

 

0

a

 

   Ko’rinib  turibdiki,  misol  qilib  98  sonini  oldik.  98  soniga  2  sonini  qo’shish 

natijasida 100 degan javob oldim. 

 

   Endi b) misol uchun Tyuring mashinasini tuzsak, 

Tashqi alfavit: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 

    Ichki alfavit: {

0

q

,  

1

q

,  

2

q

,  L, s} 

  

0

q

 - to’xtash holati 

   

1

q

 - dastlabki holat 

 

0

a

 

0 

1 

2 

3 

4 

5 

6 

7 

8 

9 

1

q

 

4 s.  

 

4 s. 

0

q

 

5 s. 

0

q

 

6 s. 

0

q

 

7 s. 

0

q

 

8 s.  

0

q

 

9 s. 

0

q

 

0 L. 

2

q

 

1 L. 

2

q

 

2 L. 

2

q

 

1 L. 

2

q

 

2

q

 

1 s. 

0

q

 

1 s. 

0

q

 

2 s. 

0

q

 

3 s. 

0

q

 

4 s. 

0

q

 

5 s. 

0

q

 

6 s.  

0

q

 

7 s. 

0

q

 

8 s. 

0

q

 

9 s.  

0

q

 

0 L. 

2

q

 

 

   Endi shu Tyuring mashinasi yordamida misol ishlab ko’rsak, 

1-qadam: 

0

a

 

0

a

 

9 

8 

0

a

 

0

a

 

 

---

2-qadam: 

0

a

 

0

a

 

9 

2 

0

a

 

0

a

 

 

 

3-qadam: 

0

a

 

0

a

 

0 

2 

0

a

 

0

a

 

 

4-qadam: 

0

a

 

1 

0 

2 

0

a

 

0

a

 

   Ko’rinib turibdiki, misol qilib yana 98 sonini oldim. 98 soniga 4 sonini qo’shish 

natijasida 102 degan javobni oldim. 

 

 

 

 

 

 

 

 

 

 

 

---

III.  XULOSA. 

   Men ushbu kurs ishimni yozish davomida аlgоritm judа mаshhur bo’lib, XX-аsr 

bоshlаrigаchа  «аlgоritm»  so’zining  o’zi  «Еvklid  аlgоritmi»  mа’nоsidа  ishlаtilib 

kеlindi.  Bоshqа  mаtеmаtikа  mаsаlаlаrni  bоsqichli  еchishni  tаsvirlаsh  uchun  esа 

«usul» so’zidаn fоydаlаnilgаn. 

 1936 yildа Аlgоritmlаr nаzаriyasi bo’yichа birinchi fundаmеntаl ilmiy ishlаr bir-

biridаn аlоhidа tаrzdа Аlаn Tyuring, Аlоiz CHyorch vа Emil Pоstlаr e’lоn qildilаr. 

Ulаr tоmоnidаn tаklif etilgаn Tyuring mаshinаsi, Pоst mаshinаsi vа CHyorchning 

lyamdа-hisоblаnuvchаnlik  usuli  аlgоritm  fоrmаlizmining  ekvivаlеnt  shаkllаridir. 

Ulаr  tоmоnidаn  tаklif  etilgаn  tеzislаr  аlgоritm  intuitiv  tushаnchаsi  vа  fоrmаl 

tizimlаrning ekvivаlеntligini tа’kidlаb bеrdi. Аlgоritmik еchimsiz muаmmоlаrning 

fоrmulirоvkаsi vа isbоti ushbu ishlаrning muhim nаtijаsi bo’ldi. 

   Ushbu  kurs  ishim  uchun  men    Tyuring  mashinasini,  uning  sxemasini,  Tyuring 

mashinasi imkoniyatlarini, Tyuring tezisini o’rganib chiqdim. Bir qancha misollar 

uchun Tyuring mashinasini tuzib chiqdim va shu mashinani to’g’riligini tekshirish 

maqsadida  uni  sinovdan  o’tkazib  ko’rdim.    Tyuring  tezisi  va  unga  ekvivalent 

bo’lgan    tushunchalarni ham  o’rganib  chiqdim.  Bundan  tashqari  men  ushbu  kurs 

ishimda Tyuring mashinasining tarkibiy qismlarini ham keltirib o’tganman.  

 

 

 

 

 

 

 

---

IV. 

Foydalanilgan adabiyotlar. 

1.  В.И.Игошин. Математическаya логика и теориya алгоритмов. 

Издательство Саратовского Университета,1991.209-211с.  

2.   О.П.Kузнецов. Дискретнаya математика длya инженера. 

М:Энергоатомиздат, 1982, 144-155 с. 

3.  Н.А.Kриницкий,Г.А.Mиронов,  Г.Д.  Фролов.  Программирование  и 

алгоритмические yaзыки,M:Наука,1979, 63-66 с.  

4. E.З. Любимский, В.В. Mартынюк, Н.П.Tрифонов 

Программирование, M:Наука, 1980,13-17 с. 

5.  Yuldashev  Z.X.    “Algoritmlar  (magistrlar  uchun  ma’ruza  matni)”  Toshkent 

2008-yil 99-bet. 

6. Boboxo’jayeva N.M.  “Algoritmlar nazariyasi”  86 bet 

7. http://structur.h1.ru/hash.htm 

http://intsys.msu.ru/stuff/vnosov/theorald.htm#top

 

8. 

www.hpcc.unn.ru

 

9. 

www.procmem.ru 

10. https://plato.stanford.edu/entries/turing-machine/

 

11. 

https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-

machine/one.html