Algoritm tushunchasi Tyuring mashinalari

Tyuring mashinasında algoritmdı realizatsiya qılıw
Tyuring mashinasinda o'nlik tizimda n dan n + 1 ge o'tishlik algoritmini realizatsiya qilish. O'nlik sanoq tizimida n sonniń yozishi berilgan bo'lsin va 11 + 1 sonniń o'nlik tizimsi dagi yozishin kórsatiw ya'ni fen) = 11 + 1 funksiyani hisoblash taqozo etilsin.
Belgili, mashinaning sirtqi alfaviti 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 raqamlardan va bos katakcha a0 dan iborat bo'lishi zurur. Lentaga o'nlik tizimda sonin yozamiz. Bu yerda satrasiga bos joysiz har bitta katakchaga bitta raqam yoziladi.
Qo'yilgan masalani yechish uchun ishning birinchi taktida mashina 11 sonniń oxirgi raqamini o'chirib, uni bitta birlik katta songa almashtirib va agar oxirgi raqam 9 soninan kichik bo'lsa, u yerda to'xtash sharoitina o'tishi zurur.
Agar 11 sonniń oxirgi raqami 9 bo'lsa, u holda mashina 9 raqamdi o'chirib, bos qolgan katakchaga 0 raqamdi yozib, o'sha holatda qolgan holda chapga yuqorilash razryadli qo'shnisi'ga surilishi zurur. Bu yerdaIshning ikkinchi taktida mashina yuqonroq razryadli raqamga I somm qo'shishi zurur. Tabiiyki, chapga surilmoqlik vaqtida yuqorilash razryadli raqam bo'lmasa, u holda mashinaning boshqaruvchi kallagi bos katakchaga chiqishi mumkin. Bu holatda bos katakchaga mashina I raqamini yozadi Aytilganlardan o'sha narsa kelib chiqadiki, f (n) = n + 1 funksiyani hisoblash algoritmini realizatsiya qilish vaqtida mashina bor yóǵi ikkita q, va q0 hollarda bo'ladi.
Shunday qilib, o'nlik tizimda n dan n + 1 ge o'tishlik algoritmini realizatsiya etadigan Tyuring mashinasi quyidagi ko'rinishda bo'ladi :

	a0	0	1	2	3	4	5	6	7	8	9
q1	1J q0	1J q0	2J q0	3J q0	4J q0	5J q0	6J q0	7J q0	8J q0	9J q0	0Chq0

Quyida n = 183 há n = 399 sonlar uchun soykes turda ularning konfiguratsiyalari keltiritgan:

a0183a0 a0183a0 q1

a0183a0

q1

q1

a0183a0

a0183a0

q1

q1

Natural sonlarni qo'shish algoritmi.
Mashina lentasiga tayoq -xomakir jamlanmasi tarzida ikkita son berilgan bo'lsin. Masalan, 2 va 3 son -lari. Bu sonlarni qO'chish taqozo etilsin. QO'chish simvolini (belgisin) yul-tuzcha bilan belgilaymiz. Shunday qilib, mashina lentasiga quyidagi so'z yoziladi.

a 0 \ |

* | | | a 0

(I) so 'zga qollanıw qılıw nátiyjesinde 2 hám 3 sanlarınıń yig' indisini, ya 'g’niy

«o|

I I I I

(2)

so‘zni beradigan funksional sxemani topish talab etiladi.
Qo 'yilgan masalani yechish jarayonin izohlab beraylik. Dastlabki
momentte mashinaning kallagi eng chapdegi tayoqchani ko'rib tursin. Uni xududi birinchi bos katakchaga erishganga qadar hamma tayoqcha va jul-tuzchalami cheklab 0 'ngga surish zurur. Bu bos katakchaga birinchi tayoqcha yoziladi. Undan so'ng ikkinchi tayoqchaga qaytib kelish zurur va uni o'chirib to'xtash zurur. Mashina ishiniing hamma taktini quyidagi uyg'un konfiguratsiyalarda ifodalab beramiz :
a₀II * III a₀

2)a₀II * III a₀

a₀II * III a q₁ q₂ q₂
4)a₀II * III a₀
5)a₀II * III a₀
6)a₀II * III a₀ q₂ q₂ q₂
7)a₀II * III a₀
8) a₀II * III a₀
9) a₀II * III a₀
Q₂ q₃ q₃
10)a₀II * III a₀
11) a₀II * III a₀
12) a₀II * III a₀
q₃ q₃ q₃
13)a₀II * III a₀
14) a₀II * III a₀
15) a₀II * III a₀
q₃ q₃ q₁
…………………… …............................ …………………………..
Bu jarayon masalaniń yechish algoritmini ikkita tortiladigan 1- ro'yhatTarzida yozuvga imkoniyat yaratani. Shunday qilib, bu yerda < aó *, I >-sirtqi alfavit va qó ql' q2' q3 - mashina holatlarinan foydalanildi.
Evklid algoritmi. Evklid algoritmi berilgan ikkita natural son uchun ularning eng katta umumiy bo'luvchisini topish kabi masalalarni yechishda tatbiq qilinadi. Ma'lumki, Evklid algoritmi qu-yidagi kamayuvchi sonlar ketma - ketligini tuzishga keltiriladi :

	ao	*	I
q)		aoJ qo	aoO'q2
	I J q3	*O'q2	IO'q2
q3	aoO'ql	*Ghq3	I Chql

1- keste
Birinchisi berilgan ikkita sonniń eng kattasi bo'ladi, ikkinchisi - kichigi, uchunchisi - birinchi sonni ikkinchisiga bo'lmoqdan vujudga kelgan qoldiq, to'rtinchisi - ikkinchi sonni uchunchisiga bo'lmoqdan vujudga kelgan qoldiq ham boshqa, bu jarayon qoldiqsiz bo'linguncha davom ettiriledi. Oxirgi bo'lmoq dagi bo'luvchi masala yechiminiing xotimasi bo'ladi. Evklid algoritmini Tyuring mashinasining dasturi sifatida ifodalash taqozo etilgan bo'lsin. Bu dastur sonlarni
taqqosroq va judo qilish sikIlarining navbatma-navbat (navbatlashib ) kelishin ta'minlashi zurur. To'rttalik harfdan iborat < a 0, \, CX, /3 sirtqi alfavitten foydalanamiz. Bu yerda a0-bos katakcha simvoli, I - tayoqcha, a va f3 - tayoqcha rolini vaqtinchalik bajaradigan harflar. Masalaniń yechilishini boshlang'ich konfiguratsiyasi
!!11 I1 II1111 a₀
Bo'lgan hoI uchun 4 va 6 sonlarding eng katta umumiy bo'luvchisini topish misolida ko'rib o'taylik. Birinchi navbatda mash ina lentada yozilgan sonlarni taqqoslashi zurur. O'sha maqsadga erishish uchun mashina birinchi sonni ifodalovchi tayoqchalarni a harfi bilan va ikkinchi sonni ifodalovchi sonlarni f3 harfimenen almashlashi zurur.
Mashina ishiniing birinchi to'rt taktiga uyg'un keluvchi uning konfiguratsiyasi quyidagicha bo'ladi:
a₀ lll ll ll ll ll a_{0 2)} a₀ lll ll ll ll a₀
q₁ q_2
3) a₀ lll ll ll ll a_{0 4)} a₀ lll ll ll ll a₀
q₂ q₁
Ushbuning bilan dastlabki sonlarni taqqosroq sikli tamom bo'lib, judo qilish sikli boshlanadi. Bu tsikl davomida kichik son lentadan butunlayiga o'chiriladi, f3 harfi bilan belgilangan ikkinchi son tayoqchalar bilan almashinadi va, demak, katta 6 soni ikkita 4 va 2 sonlariga bo'linadi.
Bu operatsiyalarga bitta satr konfiguratsiyalar to'g'ri keladi. Ushbulardan aksariyatin yozamiz :
a₀ II a₀
q₁
a₀ II a₀
q₃
a₀ II a₀
q₃
………………………………..
a₀ a a₀a₀a₀ II a₀
q₃
a₀ a a₀a₀a₀ II a₀
q_{3
……………………………………….}
a₀ a a₀a₀a₀ ll ll II a₀
q₃
a₀ a a₀a₀a₀ ll ll II a₀
q₂
Ushbuning bilan birinchi judo qilish sikli tamom bo'ladi
Endi mashina 4 va 2 sonlarini taqqoslashi zurur. Bu sonlarni taqqosroq sikli quyidagi
a₀ ll a₀
q₃
Konfiguratsiyaga va judo qilish sikli
a₀ ll a₀
q₀
konfiguratsiyaga olib keladi.
Shunday etip, Tyuring funksional sxeması 2- keste ko’rinishda boladı.

			ao		I		a		{3
	q,		auO'q3		aJ q2		aChq,		{3 Chq,
	q2		aoChq4		{3 J q,		aO'q2		O'Q2
	q3		aoJ qo		I J q2		aoO'Q3		IO'Q3
q4		aoJ Qo		I Jq,		IGhQ4		aoCh q4

2- ro'yhat
Tyuring nazariyasining tamalǵI gipotezasi
Tyuring tezisi. Tyuring mashinasi algoritm tushunchasin aniqlashding bitta yo'lini ko'rsatadiki. O'sha sababli bitta nechta so'rovlar paydo bo'ladı :
- Tyuring mashinasi tushunchasi qancha umumiylik xossaiga ega?
- algoritmlami Tyuring mashinasi vositasi bilan berish usulin universal usul deb bo'ladimi?
- hamma algoritmlami o'sha usul bilan berish mumkinmi?
Bu savollarga ayni vaqitda mavjud bo'lgan algoritmlar nazariyasi quyidagi gipoteza bilan javob beradi : har qanday algoritmni Tyuring funksional sxemasi qirg'oqlari berish va uyg'un Tyuring mashinasinda realizatsiya etish (amalga oshirishlik ) mumkin.
Bu gipoteza Tyuring tezisi deyiladi. Uni tasdiqlash mumkin emas, sababi bu tezis qat'iy ta'riflanmagan algoritm tushunchasin qat'iy aniqlangan Tyuring mashinasi tushunchasi bilan bog'laydi. Bu tezisti rad etish uchun Tyuring mashinasinda realizatsiyalan-moydigan (ro'yobga oshirilmaydigan ) algoritm mavjudligin ko'rsatish zurur. Biroq hozirga qadar aniqlangan hamma algoritmlami Tyuring funksional sxemasi qirg'oqlari realizatsiya etish mumkin.
Ekvivalent tushunchalar. Shuni ham aytib o'tamizki, Markovning normal algoritm tushunchasi hamda Chyorch, Gyodel va Klini tomonidan kiritilgan rekursiv algoritm va rekursiv funksiya tushunchalari, uyg'un turda, Tyuring tomonidan kiritilgan algoritm tushunchasi va Tyuring funksional sxemasi bilan ekvivalentligi hid -botlangan.
Bu dalil o'zlar navbatida Tyuring gipotezasining to'g'riligini yana bitta marta tasdiqlaydi

Xulosa
Usi kurs jumisinda Tyuring mashinasi, Tyuring mashinalariniin qalay ishlashin, realizasiya qiliw, uyrebip shiǵildi

Algoritmni realizasiya etish jarayonin avtomatlashtirish g'oyasi, tabiiyki, inson bajaradigan ishni mashinaga uzatmoqlikni taqazo etadi. Bunday mashinani XX asrning 30 -yillarida amerika matematigi E. Post va Angliya matematigi A. Tyuringlar taklif qildilar. Tyuring mashinasining tushunchasi bizga intuitiv ma'lumki bo'lgan hisoblash prosedurasini unsurar operasiyalarga ajratish sababdan paydo bo'ladı. Tyuring ta'kidlaydiki, xohlagan mumkin bo'lgan hisoblashni o'tkazish uchun uning unsurar operasiyalarini qaytarish yetarli. Tyuring ayrim turdagi nazariylik hisoblash mashinasin izohlaib berdi. Bu mashina muayyan mexanik apparat emas, balki «xayoliy» matematik mashina dir. Berilgan yo'riqnomani bajaruvchi hisoblaydigan odamnan yoki mavjud raqamli hisoblash mashinasinan Tyuring mashinasi ikkita tomoni bilan farq etadi
Har qanday algoritmni Tyuring funksional sxemasi qirg'oqlari berish va uyg'un Tyuring mashinasinda realizatsiya etish (amalga oshirishlik ) mumkin bu Tyuring tezisi. Tyuring mashinasi algoritm tushunchasin aniqlashga aytilgan gipoteza hisoblanadi
Bu gipoteza Tyuring tezisi deyiladi. Uni tasdiqlash mumkin emas, sababi bu tezis qat'iy ta'riflanmagan algoritm tushunchasin qat'iy aniqlangan Tyuring mashinasi tushunchasi bilan bog'laydi. Bu tezisti rad etish uchun Tyuring mashinasinda realizatsiyalan moydigan (ro'yobga oshirilmaydigan ) algoritm mavjudligin ko'rsatish zurur. Biroq hozirga qadar aniqlangan hamma algoritmlami Tyuring funksional sxemasi qirg'oqlari realizatsiya etish mumkin.

Foydalanilgan adabiyotlar

1. 
   H.T. To‗rayev, I. Azizov Matematik mantiq va diskret matematika. 1,2 jild. ―Tafakkur-Bo‗stoni‖, Toshkent, 2011y.
   
2. 
   H.Allambergenov, N.Juzbaev, A.Allambergenov. Diskret matematka ha’m matematikaliq logika tiykarlari Nokis , Qaraqalpaqstan baspasi 2016-j
   
3. 
   Mendelson E. Introduction to mathematical logic. Sixth edition. New York.Taylor&Francis Group,2015
   
4. 
   Yunusov.A.S Matematika mantiq va algoritmlar nazariyasi elementlari T.2003
   
5. 
   To'rayev H.T. Mulohazalar algebrasi. Muammoli lektsiyalar kursI. Samarkand, SamDU nashriyotI. 2003.
   

Internet saytlar
www.ziyonet.uz
www.edu.uz
www.lex.uz