12-§. Tyuring mashinasi va unda algoritmni realizasiya qilish Tyuring mashinasi tushunchasi

12.1-misol. Dastlabki konfiguratsiya quyidagicha berilgan bo‘lsin:

Boshqaruvchi kallak harfini ko‘rib turganligi va mashina holatda bo‘lganligi uchun mashina komandani ishlab chiqadi va natijada ikkinchi konfiguratsiyani hosil qilamiz.

Ravshanki, navbatdagi konfiguratsiyalar quyidagi ko‘rinishlarda bo‘ladi:

					–	uchinchi konfiguratsiya,

					–	to‘rtinchi konfiguratsiya,

					–	beshinchi konfiguratsiya.

Beshinchi konfiguratsiyada mashina holatda (to‘xtash holatida) turganligi uchun so‘z hisoblashning natijasi bo‘ladi.

12.2-misol. Boshlang‘ich konfiguratsiya quyidagicha bo‘lsin:

12.1-jadvaldagi funksional sxemadan foydalanib, quyidagi konfiguratsiyalarga kelamiz:

						–	ikkinchi konfiguratsiya,

						–	uchinchi konfiguratsiya,

						–	to‘rtinchi konfiguratsiya,

Ikkinchi va oltinchi konfiguratsiyalardan ko‘rinib turibdiki, mashinaning ish jarayoni takrorlandi va, demak, natija bo‘lmaydi.

						–	beshinchi konfiguratsiya,

						–	oltinchi konfiguratsiya.

Tyuring mashinasida algoritmni realizasiya qilish.

Tyuring mashinasida o‘nlik sistemada dan ga o‘tish algoritmini realizasiya qilish. O‘nlik sanoq sistemasida sonning yozuvi berilgan bo‘lsin va sonning o‘nlik sistemasidagi yozuvini ko‘rsatish, ya’ni funksiyani hisoblash talab etilsin.

Ravshanki, mashinaning tashqi alfaviti 0,1,2,3,4,5,6,7,8,9 raqamlardan va bo‘sh katakcha dan iborat bo‘lishi kerak. Lentaga o‘nlik sistemada sonni yozamiz. Bu yerda qatorasiga bo‘sh joysiz har bir katakchaga bitta raqam yoziladi.

Qo‘yilgan masalani yechish uchun ishning birinchi taktida mashina sonning oxirgi raqamini o‘chirib, uni bir birlik katta songa almashtirib va agar oxirgi raqam 9 sonidan kichik bo‘lsa, u holda to‘xtash holatiga o‘tishi kerak.

Agar sonning oxirgi raqami 9 bo‘lsa, u holda mashina 9 raqamni o‘chirib, bo‘sh qolgan katakchaga 0 raqamni yozib, o‘sha holatda qolgan holda chapga yuqoriroq razryadli qo‘shnisiga surilishi kerak. Bu yerda ishning ikkinchi taktida mashina yuqoriroq razryadli raqamga 1 sonini qo‘shishi kerak.

Tabiiyki, chapga surilish paytida yuqoriroq razryadli raqam bo‘lmasa, u holda mashinaning boshqaruvchi kallagi bo‘sh katakchaga chiqishi mumkin. Bu holatda bo‘sh katakchaga mashina 1 raqamini yozadi.

Aytilganlardan shu narsa kelib chiqadiki, funksiyani hisoblash algoritmini realizasiya qilish paytida mashina bor yo‘g‘i ikkita va holatlarda bo‘ladi.

Shunday qilib, o‘nlik sistemada dan ga o‘tish algoritmini realizasiya etadigan Tyuring mashinasi quyidagi ko‘rinishda bo‘ladi:

		0	1	2	3	4	5	6	7	8	9

Quyida va sonlar uchun mos ravishda ularning konfiguratsiyalari keltirilgan.

Natural sonlarni qo’shish algoritmi. Mashina lentasiga tayoqchalar majmuasi shaklida ikkita son berilgan bo’lsin. Masalan, 2 va 3 sonlari. Bu sonlarni

qo’shish talab etilsin. Qo’shish simvolini (belgisini) yulduzcha bilan belgilaymiz. Shunday qilib, mashina lentasiga quyidagi so’z yoziladi.

(12.1)

(1) so’zga tatbiq qilish natijasida 2 va 3 sonlarining yig‘indisini, ya’ni

(12.2)

so‘zni beradigan funksional sxemani topish talab etiladi.

Qo’yilgan masalani yechish jarayonini izohlab beraylik. Dastlabki momentda mashinaning kallagi eng chapdagi tayoqchani ko’rib tursin. Uni to birinchi bo’sh katakchaga erishguncha hamma tayoqcha va yulduzchalarni cheklab o’ngga so’rish kerak. Bu bo’sh katakchaga birinchi tayoqcha yoziladi. Undan so’ng ikkinchi tayoqchaga qaytib kelish kerak va uni uchirib to’xtash kerak. Mashina ishining hamma taktini quyidagi mos konfiguratsiyalarda ifodalab beramiz.

1)		2)		3)
4)		5)		6)
7)		8)		9)
10)		11)		12)
13)		14)		15)
16)		17)		18)
19)		20)		21)
22)		23)		24)
25)		26)		27)
28)		29)		30)

Bu jarayon masalaning yechish algoritmini ikki o‘lchovli 12.2-jadval shaklida yozishga imkoniyat yaratadi.

Shunday qilib, bu yerda – tashqi alfavit va – mashina holatlaridan foydalanildi.

12.2-jadval
		

Evklid algoritmi. Evklid algoritmi berilgan ikkita natural son uchun ularning eng katta umumiy bo‘luvchisini topish kabi masalalarni yechishda qo‘llaniladi. Ma’lumki, Evklid algoritmi quyidagi kamayuvchi sonlar ketma-ketligini tuzishga keltiriladi: birinchisi berilgan ikki sonning eng kattasi bo‘ladi, ikkinchisi – kichigi, uchinchisi – birinchi sonni ikinchisiga bo‘lishdan hosil bo‘lgan qoldiq, to‘rtinchisi – ikkinchi sonni uchinchisiga bo‘lishdan hosil bo‘lgan

qoldiq va hokazo, bu jarayon qoldiqsiz bo‘linguncha davom ettiriladi. Oxirgi bo‘lishdagi bo‘luvchi masala yechimining natijasi bo‘ladi.

Evklid algoritmini Tyuring mashinasining dasturi sifatida ifodalash talab etilgan bo‘lsin. Bu dastur sonlarni taqqoslash va ayirish sikllarining navbatma-navbat (navbatlashib) kelishini ta’minlashi kerak.

To‘rtta harfdan iborat tashqi alfavitdan foydalanamiz. Bu yerda – bo‘sh katakcha simvoli, – tayoqcha, va – tayoqcha rolini vaqtinchalik o‘ynaydigan harflar.

Masalaning yechilishini boshlang‘ich konfiguratsiyasi

bo‘lgan hol uchun 4 va 6 sonlarning eng katta umumiy bo‘luvchisini topish misolida ko‘rib o‘taylik.

Birinchi navbatda mashina lentada yozilgan sonlarni taqqoslashi kerak. Shu maqsadga erishish uchun mashina birinchi sonni ifodalovchi tayoqchalarni harfi bilan va ikkinchi sonni ifodalovchi sonlarni harfi bilan almashtirishi kerak. Mashina ishining birinchi to‘rt taktiga mos keluvchi uning konfiguratsiyasi quyidagicha bo‘ladi:

1)		2)
3)		4)

Shu bilan dastlabki sonlarni taqqoslash sikli tamom bo‘lib, ayirish sikli boshlanadi. Bu sikl davomida kichik son lentadan butunlayiga o‘chiriladi, harfi bilan belgilangan ikkinchi son tayoqchalar bilan almashinadi va, demak, katta 6 soni ikkita 4 va 2 sonlariga bo‘linadi.

Bu operasiyalarga bir qator konfiguratsiyalar to‘g‘ri keladi. Shulardan ayrimlarini yozamiz:

..........................................

..........................................

Shu bilan birinchi ayirish sikli tamom bo‘ladi.

Endi mashina 4 va 2 sonlarini taqqoslashi kerak. Bu sonlarni taqqoslash sikli quyidagi

konfiguratsiyaga va ayirish sikli

konfiguratsiyaga olib keladi.

Uchinchi taqqoslash sikli 2 va 2 sonlarini

konfiguratsiyaga va ayirish sikli

oxirgi konfiguratsiyaga olib keladi.

Shunday qilib, Tyuring funksional sxemasi 12.3-jadval ko‘rinishida bo‘ladi.

12.3-jadval

Mustaqil bajarish uchun muammoli masala va topshiriqlar

1. 
   Quyidagi funksiyalarni hisoblovchi algoritmlarni Tyuring mashinasining dasturlari sifatida ifodalang:
   

a) ; b) ; d) .

2. 
   Quyidagi funksiyalarni funksiyani hisoblovchi Tyuring mashinasini tuzing:
   

a)

b)

3. 
   Ushbu funksiyani hisoblovchi Tyuring mashinasini tuzing.
   
4. 
   Ushbu funksiyani hisoblovchi Tyuring mashinasining dasturlarini alfavitda yozing.
   
5. 
   Funksional sxemalari 1-va 2-jadval jadvallarda berilgan Tyuring mashinasi qanday funksiyalarni hisoblashi mumkinligini aniqlang.
   

1-jadval				2-jadval
...	...	...

6. 
   Dasturi 3-jadvaldagi funksional sxema orqali berilgan Tyuring mashinasi qanday ko‘rinishdagi funksiyani hisoblashi mumkinligini aniqlang.
   

3-jadval

7. Berilgan

programma bo’yicha Tyuring mashinasini P so’ziga qo’llash mumkinmi? Bunda, q₁-boshlang’ich holat, q₀-tugallangan holat.

1. P=[10]²0011;

2. P=[01]²0011;

3. P=[101]²0011;

4. P=1³0³[01]²;

5. P=1² 0²[01]²;

6. P=1⁵[01]²;

7. P=100 [10]²;

8. P=0011[01]²;

9. P=0011 [101]²;

10. P=[01]²1³0³;

11. P=[01]²1² 0²;

12. P=[01]²1⁵;

13. P=[110]²0011;

14. P=[011]²0011;

15. P=[11]²0011;

16. P=1³0³[11]²;

17. P=1² 0²[11]²;

18. P=1⁵[11]²;

19. P=100 [11]²;

20. P=1011[10]²;

21. P=1010 [10]²;

22. P=[10]²1³0³;

23. P=[10]²1² 0²;

24. P=[10]²1⁵;

25 P=[101]²1⁵;
8. T₁ va T₂ mashinalarning (q_10, q₂₁) holatlar juftligi bo’yicha kompzisiyasin tuzing. Bunda, q_10-T₁ mashinaning tugallovchi holati, q₂₁- T₂ mashinaning boshlang’ich holati, q₂₀ esa tugallovchi holati.

9. T₁ va T₂ mashinalarning (q_10, q₂₁) holatlar juftligi bo’yicha kompzisiyasin tuzing. Bunda, q_10-T₁ mashinaning tugallovchi holati, q₂₁- T₂ mashinaning boshlang’ich holati, q₂₀ esa tugallovchi holati.

10. Berilgan P so’zga T=T(T₁,(q’₁₀,q₂₁), T₂,(q’’₁₀,q₃₁),T₃) mashinani qo’llanilishini aniqlang.

Bunda, q₂₀ -T₂ mshinaning tugallovchi holati, q₃₀ -T₃ mashinaning tugallovchi holati.

11. Berilgan P so’zga T=T(T₁,(q’₁₀,q₂₁), T₂,(q’’₁₀,q₃₁),T3) mashinani qo’llanilishini aniqlang.

Bunda, q₂₀ -T₂ mshinaning tugallovchi holati, q₃₀ -T₃ mashinaning tugallovchi holati.

1. 
   11[011]³
   
2. 
   101³11²
   
3. 
   1[1011]²
   
4. 
   101²10²
   
5. 
   1²0[01]²
   
6. 
   1²[[01]²]²
   
7. 
   1[1²0¹1²]¹
   
8. 
   1²0²[01]²
   
9. 
   [[10]²0]²
   
10. 
    [1]²[01]²
    
11. 
    011[11]²1
    
12. 
    [11]²[01]³
    
13. 
    0101³0
    
14. 
    11[011]²
    
15. 
    [101²]²
    
16. 
    1010²[1²]²
    
17. 
    [01100]²
    
18. 
    01[011]²
    
19. 
    [011]³
    
20. 
    [01]²[10]²1
    
21. 
    10[101]²
    
22. 
    011³[10²]²
    
23. 
    [101²]²
    
24. 
    [[10]²1]²
    
25. 
    [101]²1011
    
26. 
    1[10²]²1
    
27. 
    [[10]²1]²
    
28. 
    1[10]²10]²
    
29. 
    [1[01]²]²
    
30. 
    [[01]²]²
    

Adabiyotlar

1. 
   Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012
   
2. 
   Мендельсон Э. Введение в математическую логику. М.: Наука, 1984
   
3. 
   Яблонский С. В. Введение в дискретную математику. – М.: Наука, 1986.
   
4. 
   Юнусов А.С. Математик мантиқ ва алгоритмлар назарияси элементлари, Т., 2008.
   
5. 
   To‘rayev X.T., Matematik mantik va diskret matematika. - T., O‘qituvchi,2003.
   
6. 
   Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физ.-мат. литература, 1995.
   
7. 
   Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. - М.: Наука. -1969.
   
8. 
   Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1987.
   
9. 
   Клини С. К. Математическая логика. М.: Мир, 1973
   
10. 
    Партее Б., тер Меулен А., Wалл Р. Матҳематиcал Метҳодс ин Лингуистиcс. Дордречт: Реидел, 1989.
    
11. 
    Гиндикин С. Г. Алгебра логики в задачах. – М.: Наука, 1972.
    
12. 
    Малсев А. И. Алгебраические системы. – М.: Наука, 1970.