Mirzo Ulugʻbek nomidagi Oʻzbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti

Tyuring mashinasida oʻnlik sistemada n dan n + 1 ga oʻtish
Agoritmini realizatsiya qilish.Oʻnlik sanoq sistemasida n sonning yozuvi berilgan boʻlsin va n+1 sonning oʻnlik sistemasidagi yozuvini koʻrsatish, ya’ni f(n)= n+1 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 n sonini yozamiz. Bu yerda qatorasiga boʻsh joysiz har bir katakchaga bitta raqam yoziladi. Qo`yilgan masalani yechish uchun ishning birinchi taktida mashina n 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.
Shunday qilib, oʻnlik sistemada n dan n+1 ga oʻtish algoritmini realizatsiya etadigan Tyuring mashinasi quyidagi koʻrinishda boʻladi:

	a0	0	1	2	3	4	5	6	7	8	9
q1	1Jq0	1Jq0	2Jq0	3Jq0	4Jq0	5Jq0	6Jq0	7Jq0	8Jq0	9Jq0	0Chq1

2-jadval
Quyida n = 183 va n = 399 sonlar mos ravishda ularning konfiguratsiyalari keltirilgan:
_{ }183_{   }399_{ 
   
 }184_{   }390_{ 
   
 }400_{ 
 }
Evklid algoritmi. Evklid algoritmi berilgan ikkita natural son uchun ularning eng katta umumiy boʻluvchisini topish kabi masalalami yechishda qoʻllaniladi. Ma’lumki, Evklid algoritmi quyidagi kamayuvchi sonlar ketma - ketligini tuzishga keltiriladi:

	 	*	|
q1		 Jq0	 Oʻq2
q2	|Jq3	*Oʻq2	|Oʻq2
q3	 Oʻql	*Chq3	|Chq3

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 sonlami 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 holi uchun 4 va 6 sonlarning eng katta umumiy bo‘luvchisini topish
misolida ko‘rib o‘taylik.
Birinchi navbatda mashina lentada yozilgan sonlami taqqoslashi kerak. Shu maqsadga erishish uchun mashina birinchi sonni ifodalovchi tayoqchalarni α harfi bilan va ikkinchi sonni ifodalovchi sonlami β 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 operatsiyalarga bir qator konfiguratsiyalar to‘g‘ri keladi. Shulardan ayrimlarini yozamiz:
_{ }ααααββββ | |_{ 
 
 }ααααββββ| |_{ 
 
 }ααααββββ| |_{ 
 }
…………………….
_{    }| | | | | |_{ 
 
    }| | | | | |_{ }
q₂
Shu bilan birinchi ayirish sikli tamom bo‘ladi.Endi mashina 4 va 2 sonlarini taqqoslashi kerak. Bu sonlarni taqqoslash sikli quyidagi
| | α α β β
q₄
konfiguratsiyaga va ayirish sikli
| | | |
q₁
konfiguratsiyaga olib keladi.
Uchinchi taqqoslash sikli 2 va 2 sonlarini
α α β β
q₃
konfiguratsiyaga va ayirish sikli
| |
_{ }
oxirgi konfiguratsiyaga olib keladi.

Shunday qilib, Tyuring funksional sxemasi 2- jadval ko'rinishida boladi.

		|	α	β
 	O` q3	αJ q2	αCh 	βCh 
q2	Ch q4	βJ 	αO` q2	O` q2
q3	Jq0	|J q2	O` q3	|O` q3
q4	Jq0	|J 	|Ch q4	Ch q4

3-jadval


Xulosa
Bu kurs ishini yozish davomida quyidagi xulosaga ega boʻldim: Men birinchi navbatda algoritm tushunchasi haqida ko`proq ma’lumotga ega boʻlib.Roʻyxatlar haqida tushuncha ularning turlari va algoritmlarning jadval ko`rinishida tasvirlanish usullarini o`rganib chiqdim.
Tyuring mashinasining ishlashida Tyuring jadvalining o`rni juda yuqori ekanligi va shu haqida ma’lumotga ega boʻldim.