Algoritm tushunchasi Tyuring mashinalari

Download 52,08 Kb. bet 2/5 Sana 05.07.2022 Hajmi 52,08 Kb. #740626

Bog'liq
Algoritm tushunchasi Tyuring mashinalari

P (x) =a	0	xn + a xn1 + ...+  a	n1	x+a	n
=0

Butun sonli koefficiyentlerden iborat tenglamading to'nkasi butun son bo'lsa, u holda bu to'nka a n koefficiyenttiń bo'luvchisi boMadi. Bu tasdiqqa asoslanib, quyidagi algoritmni taklif etish mumkin :
a n sonniń hamma bo'llariniwshilarin toppish :, d 2,.. ., dn ;
2) a n sanning har bir bo’linuvchisi uchun Pn (x) ning yechimi ni aniqlash :
pn (d,) d ' = l«);
3) agar 1, 2 sonlardan qandayda-bir i uchun Pn ( d i ) = 0 bo'Isa, u holda d t tenglamaning yechimi bo’ladı. Agar barcha i e { 1, 2 uchun Pn ( d i) ^ 0 bolsa, u holda tenglama butun sonly yechimlarga ega emas (algoritm tugadi).
Gilbertning 10 - muammosi bilan dunyoning ko'p matematiklari deyarli 70 yil davomida shug'ullanishni va nihoyat, 1968-yilga kelib Sonkt-Peterburglik yosh matematik Yu. v. Matiyasevich1 va sol so'ng, aniqraǵi, 1970-yilda rus matematigi G. v. Chudnovskiy bu muammoni yechishdi. Aniqlangdii, qo 'yilgan masalaniń yechimini bera oladigan algoritm yo'qlar.
Algoritmding intuitiv ta'rifi qat'iy emasligine qat'iy nazar, u muayyan masalaniń yechimini tovatugın algoritmding to'g'rilıgına guman uyg'otpaydı. Matematikada o'shanaqa yechimi tabilgan narsagan algoritmik muammolar barki, ular qarorga iyeme yoki ega emasmikan ekanligin aniqlash muammosi paydo bo'ladı. Ushbumashqalanı yechishda algoritmding intuitiv ta'rifi yordam berolmayni. Bu jagdaylarda yoki algoritmding mavjudligin, yoki uning yo'qlarlıgın tasdiqlash zurur bo'ladi. Birinchi holda masalani oyitugın jarayonni tasvirlash yetarli. Bu jarayonning darhaqiqat algoritm ekanligine ishonch hosil qilish uchun algoritmding intuitiv tushunchasi yetarli bo'ladi. Ikkinchi holda algoritmding yo'qlarlıgın tasdiqlash zurur. Buning uchun algoritmding nima ekanligin aniq bilishlik taqozo etiladi. XX asrning 30 - yillariga qadar algoritmga aniq ta'rif berilmagan edilar. O'sha sababli algoritm tushunchasiga aniq izohlash keyingi davr matematikasining tamalgı masalalarigan biri bo'lib qoldi. Bu ta'rifni ishlab shıgıw jarayonida ko'p qiyinchilik mavjudligi ma'lumki bo'ldi. Birinchidan, bunday ta'rif algoritm intuitiv ta'rifining ma'nosini aks ettirishi, ikkinchidan bo'lsa, u shakllanıqlıq nuqtai nazarinian takomillashgan bo'lishi zurur edilar. Bu muammoning tadqiqotchilari tomonidan algoritmding bitta nechta ta'rifi ishlab chiqildi. Biroq vaqt o'tishi bilan bu ta'riflaming o'zaro teng kuchliligi aniqlangdi. Ana o'sha ta'rif xozirgi zamon algoritm tushunchasi dir.
Algoritm tushunchasini aniqlashga yondashuvlar.
Algoritm tushunchasin aniqlash bo'yicha yondoshuvlami uchlar asosiy yo'nalishke
b o iish mumkin. Birinchi yo'nalish effektiv hisoblanuvchi funksiya tushunchasin aniqlash bilan aloqador. Bu yo'nalish bo'yicha A. Chyorch, K. Gyodel S. Klini1 izlanish yumushlarini olib borishgan. 1932-1935-yillar davomida A. Chyorch va S. Klini tomonidan o'rganilgan va « Ya -qaralmish funksiyalar» deb atalgan, to'g'ri aniq - langan hisoblanuvchi nazariylik -sonli funksiyalar sinfming « Ya -qaralmish funksiyalar» sinfi bizning intuitiv tasavvurimiz bo 'yicha hisoblanuvchi deb qaraladigan hamma funksiyalami qamrashi mumkin degan fikr uwıllıǵi 1935-yiIda yozma xabar qilindi. Bu kutilmagan xotima edilar. J. Erbranning2 bitta g'oyasi asosida 1934-yilda K. Gyodel tomonidan aniqlangan va «umumrekursiv funksiyalar» deb atalgan boshqa hisoblanuvchi funksiyalar sinfi ham « -qaralmish funksiyalar» xossalariga o'xshash xossalarga ega edilar. 1936 -yilda A. Chyorch va S. Klini tomonidan bu ikkita sinf mushtarak sinf ekanligi tasdiqlandi, ya'ni har qanday Ya -qaralmish funksiya umumrekursiv funksiya bo 'lishi va har qanday umumrekursiv funksiya Ya - qaralmish funksiya ekanligi tasdiqlandi. 1936 -yilda Chyorch quyidagi tezisti e'lon qildi : har qanday intuitiv effektiv (samarodor ) hisoblanuvchi funksiyalar umumrekursiv funksiyalar dir. Bu teorema emas, balki tezis dir : tezis tarkibida intuitiv aniqlangan effektiv hisoblanuvchi funksiya tushunchasi, aniq matematik atamalarda aniqlangan umumrekursiv funksiya tushunchasi bilan ayni tengqurti-ril-gan. O'sha sababli bu tezisti tasdiqlash mumkin emas. Biroq Chyorch va boshqa olimlar tomonidan bu tezisti quvvatlovchi ko'p dalillar namoyish etildi Ikkinchi yo'nalish algoritm tushunchasin bevosita aniqlash bilan aloqador : 1936 -1937-yillarda, A. Tyuring3 Chyorch yumushlaridan bexabar holda yangi funksiyalar sinfin kiritdi. Bu funksiyalami «Tyuring bo'yicha hisoblanuvchi funksiyalar» deb atadilar. Bu sinf ham yuqorida aytilgan xossalarga ega edilar va buni Tyuring tezisi deb aytamiz. 1937-yildaA. Tyuring uning hisoblanuvchi funksiyalari X-qaralmish funksiyalar - ning o 'zi va, demak, umumrekursiv funksiyalaming xududi o 'zi ekanligin isbotladi. O'sha sababli Chyorch tezisi bilan Tyuring tezisi ekvivalent dir. 1936 -yilda E. Post (Tyuring yumushlaridan bexabar holda ) ayni Tyuring erishgan natijalarga mos kelarlik xotimalami e'lon qildi va 1943-yilda, 1920 -1922-yillardagi bosma etilmagan yumushlariga asoslanib, to'rtinchi ekvivalent tezisti bosma qildi. Shunday qilib, algoritm tushunchasin bevosita aniqlashga va so'ngra uning yordamida hisoblanuvchi funksiya tushunchasin aniqlashga birinchi bo'lib bir-birinien bexabar holda E. Post va A. Tyuring erishdilar. Post va Tyuring algoritmik jarayonlar ma'lumki bitta tuzilishga ega bo'llar - gan «mashina» bajaradigan jarayonlar ekanligin ko'rsatishni. Ular bu «mashinalar» yordamida borlik hisoblanuvchi funksiyalar sinfi bilan borlik bo'lagiy rekursiv funksiyalar sinfi mushtarak ekanligin ko'rsatdilar va, demak, Chyorch tezisining yana bitta fundamental tasdig'i yuzaga keldi. Uchunchi yo'nalish - Rossiya matematigi A. Markov1 tomonidan ishlab chiqilgan normal algoritmlar tushunchasi bilan aloqador
Agar qandaydir ommaviy muammoni hal etish algoritmi ma'lumki bo'lsa, u holda uni realizasiya etish uchun o'sha algoritmda aniq yoritilgan ko'rsatmalarni kuylash zarur. 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. Birinchidan, «Tyuring mashinasi» xato etolmaydi, ya'ni u egishmay (chetga chiqmasdan) yoritilgan qoidani bajaradi.
Ikkinchidan, «Tyuring mashinasi» potensial cheksiz yod bilan ta'minlangan. Endi Tyuring mashinasi tushunchasi bilan toliq tanishamiz. Tyuring mashinasin quyidagilar toliq aniqlaydi.
1. tashqi alfavit, ya’nıy

Download 52,08 Kb.

Do'stlaringiz bilan baham: