|
Tyuring mashinasida algoritmni realizasiya qilish
|
| bet | 4/4 | | Sana | 28.11.2023 | | Hajmi | 409,53 Kb. | | #106838 |
Bog'liq 3-Ma\'ruza. T’yuring mashinasi va tezisiTyuring mashinasida algoritmni realizasiya qilish
Ayrim oddiy arifmetik algoritmlarni realizasiya qiladigan (amalga oshiradigan) Tyuring mashinasini yasashni misollarda o‘rganamiz.
Tyuring mashinasida o‘nlik sistemada n dan n+1 ga o‘tish algoritmini realizasiya 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 0a dan iborat bo‘lishi kerak. Lentaga o‘nlik sistemada n sonni 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.
Agar n 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, f(n)=n+1 funksiyani hisoblash algoritmini realizasiya qilish paytida mashina bor yo‘g‘i ikkita va holatlarda bo‘ladi.
Shunday qilib, o‘nlik sistemada n dan n+1 ga o‘tish algoritmini realizasiya etadigan Tyuring mashinasi quyidagi ko‘rinishda bo‘ladi:
Quyida n=183 va n=399 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.
so’zga tatbiq qilish natijasida 2 va 3 sonlarining yig‘indisini, ya’ni
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.
Bu jarayon masalaning yechish algoritmini ikki o‘lchovli 1- jadval shaklida yozishga imkoniyat yaratadi.
Shunday qilib, bu yerda – tashqi alfavit va – mashina holatlaridan foydalanildi.
Shunday qilib, Tyuring funksional sxemasi 2- jadval ko‘rinishida bo‘ladi.
Foydalanilgan adabiyotlar:
1.Тўраев Ҳ.Т., Математик мантиқ ва дискрет математика, Тошкент: Ўқитувчи нашриёти, 2003, 378 б.
2.Лихтарников Л.М., Сукачева Т.Г., Математическая логика. Курс лекций. Задачник-практикум и решения, Санк-Петербург: ЛАНЬ, 1999, 286 с.
3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. Учебное пособие. Москва: Наука.
4. Искандаров Р.И., Математик логика элементлари,Самарқанд:СамДУ,1970,324 б.
|
| |
