Baki qizlar universiteti
Yüklə 229,1 Kb.
|
- Bu səhifədəki naviqasiya:
- Budaqlanan alqoritml ə rin
- Dövrü alqoritm
|
Xətti alqoritmlər sadə hesablama prosesini ifadə edən bir neçə ardıcıl əməliyyatlardan ibarət olur və onlar yazıldığı ardıcıllıqla da icra olunur. Xətti alqoritmdə bloklar ardıcıl şəkildə yerinə yetirilir.
başlangıc son g-nin çapi g= A,B nin girisi baslangic Budaqlanan alqoritmlərin tərkibində bir və ya bir neçə məntiq mərhələsi olur. Bu mərhələdə müəyyən kəmiyyətlərin hər hansı bir şərti ödəyib-ödəmədiyi yoxlanılır və ona uyğun olaraq sonrakı gedişin istiqaməti seçilir. Yəni nəzərdə tutulan şərt ödənilirsə, bir istiqamətə, həmin şərt ödənilmirsə, başqa istiqamətə doğru hərəkət edilir. Beləliklə, alqoritmdə budaqlanma baş verir. Budaqlanan alqoritmlərdə şərt operatorundan istifadə olunur a>b a b nin girisi başlanğıc he yox Max=a Min=b Max elementi capi son Dövrü alqoritm - Alqoritmin hər hansı mərhələsi təkrar-təkrar yerinə yetirilirsə belə alqoritm dövru alqoritm adlanırm. Dövri alqoritmlərdə şərt blokundan və sayğacdan istifadə olunur. başlanğıc N in girisi S:=0 i:=1 i n S:=s+i he
I:=i+2 S –in çapi son 3.Sonlu Avtomatlar Avtomatlar nəzəriyyəsi nəzəri kibernetikanın əsas bölmələ rindən biridir. Burada avtomat adlanan riyazi modellər öyrənilir. Bu modellər vasitəsi ilə real mövcud olan və ya reallaşdırıla bilan diskret zaman ərzində diskret informasiyaları (texniki, bioloji v s) emal edən qurğulardır. Avtomat anlayışı rəqəmi hesablayıcı texnikanın və idarəetmə maşınların, həmçinin alqoritmlər nəzə riyyəsinin və riyazi məntiqin tələbindən yaranmışdır. Burada sonlu, sonsuz, ehtimalli, avtonom işləyən, determinalı və s. avtomatlar ola bilər. Maksimum dərəcədə ən ümumi avtomatların yaradıl ması məsələsinin tam həll olunduğunu hələ demək olmaz, ancaq idarə etmək sistemlərin xüsusi halına baxmaq olar. Avtomat terminin ilk rüşeymləri 1930-cu illərdə alqoritmlər və releyli qurğular nəzəriyyəsində yaranmışdır, lakin 1950-ci ildən sonra bir problem kimi meydana çıxmışdır. Məlumdur ki, alqoritmlər nəzəriyyəsində sonlu avtomatlar Turinq maşınları geniş öyrənil mişdir və göstərilmişdir. İxtiyari informasiyaları effektiv çevirmək üçün hər dəfə ixtisaslaşdırılmış avtomatlar yaratmaq lazım deyildir, bir universal avtomat yaratmaq kifayətdir. Məhz universal hesablama texnikasının yaradılması bu mə-sələnin həllidir. Avtomatlar nəzəriyyəsində cəbrin, riyazi məntiqin, kombinator analizin (qraf nəzəriyyəsi daxil olmaqla) və ehtimal metodlarından istifadə edilir, ona görə avtomatların cəbri nəzəriyyəsi, mücərrəd avtomatlar nəzəriyyəsi və s. nəzəriyyələr vardır. Avtomatlar hərflər ardıcıllığını hərflər ardıcıllığına çeviricilardir. Bu qurğular nə maddə, nə də enerji emal etmir, siqnallarla işləyir. Müəyyən siqnallar vasitəsi ilə daxil olan «sözü>> başqa dilin sözünə çevirir. Bu termin texnikada işlənən «avtomat» sözündən tamamilə fərqlənir. MƏNTİQİ ELEMENTLƏR, MƏNTİQİ QURĞULAR VƏ AVTOMATLARIN STRUKTURU
Və məntiqi əməli (konyuksiya) - hər iki açar qapalı olduqda və ancaq onda lampa yanır. Belə qurğu konyuktor adlanır. b Deyil (inkar) məntiqi əməli açar qapalı olmadıqda lampa yanır. Bu növ qurğu invetor adlanır. Vibe nim Sadə məntiq əməllərinin nəticələri siqnal yaradan qurğular məntiqi element adlanır. Məntiqi elementlər ən sadə avtomatlardır. Konyuktur, dizyunktur və inventorlardan ibarət olan sxemlǝr funksional sxemlər adlandırılır. Avtomatın daxili quruluşu onun strukturu adlanır. Avtomatların strukturunu düstur və ya sxemlər vasitəsi ilə təsvir etmək olar. Əgər avtomatın struktur düsturu məlumdursa, burada məntiqi elementlərin sayı və elementlərin birləşdirilməsi sxemini tayin etmək olar. AVTOMATLARIN SİNTEZİ ÜÇÜN ALQORİTMLƏR
1. Avtomatın işləməsini təmin edən şərtləri təyin etmək. 2. Layihələşdirilən avtomatı "sehrli qutu" səviyyəsində təsəvvür etməli, bu avtomatın girişləri və çıxışları sayını müəyyənləşdirməyə imkan verir. 3. Layihələşdirilən avtomatın işini təsvir edən cədvəl qurmalı 4. Cədvəldən istifadə edərək avtomatın Bul funksiyasını yazmalı 5. Struktur düsturu minimallaşdırmalı 6. Sonuncu struktur düstura görə avtomatın funksional sxemini tərtib etməli. Məsələn, bir rəqəmdən ibarət üç ikilik rəqəmləri cəmləyən avtomatın məsələsinə Məsələni başa düşmək üçün analoji bir məsələyə baxaq. Zavodun A, B, C sxemləri var. Bu sxemləri X və Y generatoru olan elektrik stansiyası təmin edir. X generatorunun gücü y-in gücündən 2 dəfə artıqdır. Sxemlərdən yalnız birinin işlənməsi üçün y generatorunu, 2 sex üçün X generatorunu işə salmaq kifayətdir. Növbəti A, B və C sexlərindən stansiyaya daxil olan siqnalları izləyir və lazım olan generatoru işə salır. Növbətçini əvəz dən avtomat düzəltmək tələb olunur.
1. Avtomat A, B, C sexlərindən siqnal alır, deməli onun üç girişi olmalıdır. 2. Avtomatın yaratdığı siqnallar 2 ünvana X vǝ Y generatorlarına göndərilməlidir, yəni avtomatın 2 çıxışı olmalıdır. A X B Y C Avtomatın işini təsvir edən cədvəli çəkək. 2-ci sətir göstərir ki, enerji yalnız C sexinə lazımdır. 8-sətir isə hər 3 sexǝ enerji verilməsini tələb edir. Alqoritmin strukturuna bir qutuya qoyulmuş 2 qurğu kimi baxmaq olar. Onlardan birinin çıxışı X, digərinin çıxışı Y-dir. Beləliklə, çıxışda ya A, B və Csexlərinin üçündən ya B və C, ya A və B, ya da A və C ibarət olmaqla 4 siqnal alınır.
X=ABC+ABC´+AB´C+A´BC (1) Y=ABC+ABC´+A´BC (2) Sonrakı addımda düsturların minimallaşdırılması məsələsi no baxmalıyıq. Bu düsturda 3 mülahizə iştirak edir, ona görə kubdan istifadə edilə bilər. 4 1 A 3 2 B C düsturunun hədlərini kubun uyğun təpələrində təsvir edək. Əgər minimallaşdırma üçün həndəsi metoddan istifadə etsək X generatorunu idarə edən avtomat üçün yeni düstur alırıq: X= AB+ AC + BC İndi kubun uyğun tillərində (2) düsturunu təsvir edək. Bu halda nişanlanmış təpələrdən istənilən 2-si bir til üzərinə düşmədiyində (2) düsturunu minimallaşdırmaq mümkün deyil. Y generatorunun isə idarə edən avtomatın struktur düsturu əvvəlki kimi qalır. 4 1 A 3 2 B C İndi tutaq ki A,B,C birmertebeleri ikilik ededlerdir.Onlarin cemini tapmaq istiyirik A
__ C__ XY Burada asagidaki hallar ola biler 2) 3) 4) 5) 6) 7) 8) 1 1 1 0 0 0 0 *1 *1 *0 *0 *1 *1 *0 *0 Görürük ki, avtomat "növbətçi" bir mərtəbəli 3 ikilik ədədi toplaya bilər. Deməli, ikilik say sistemində hesablamaları avto- matlara tapşırmaq olar. T k+1 Bilirik ki, EHM-lər əsas komponenti cəmləyicidir. Kompüterdə istənilən hesablama cəmləməyə gətirilir və terefinden icra edilir. Birmərtəbəli cəmləyicinin üç girişi (Pk;Qk;Tk-1) ve iki çıxışı (Sk; Tk+1) vardır. Pk va Qk girişləri vasitəsi ilə cəmləyiciyə toplananlar Tk vasitəsi ilə K mərtəbəsindən ötürülən rəqəm haqqında signal daxil olur. Sk çıxışında cəmin uyğun mərtəbəsinin rəqəmi Tk+1 çıxışında isə (k+1)-ci mərtəbəyə ötürülməli olan rəqəm barədə siqnal yaranır. Yazılışı sadələşdirmək üçün Pk. Qk.Tk girişlərini P.Q.T. Sk ve Tk çıxışlarını S və T ilə işarə edək. P,Q, R, S vǝ T yalnız 0 və 1 qiymətlərini ala bilir. Burada T vǝ S çıxışları P, Q və R girişlərinin Bul funksiyası olacaqdır. Yəni T (P. QR) və S(P,Q, R) funksiyalarını alırıq. Burada mükəmməl konyuktiv normal forma (MKNF)-ni təyin edə bilərik. Hədləri bütün dəyişənləri və ya onların inkarınımn müxtəlif dizyunksiyalarından ibarət olan konyunksiyaya MKNF deyilir.
Hədləri bütün dəyişənlərinin və ya onların inkarının müxtəlif konyunksiyalarından ibarət olan dizyunkiyaya mükəmməl dizyuktiv normal forma (MDNF) deyilir. T va S üçün minitermləri yazıb onların ifadələrini tərtib etmək olar MDNF- də Ifadelerini tertib etmek olar. TMDNF = P´QR + PQ´R+ PQR´ + PQR SMDNF =P´Q´R+P´QR´ + PQ´ R´ + PQR Bu məntiqi sxemləri sadələşdirməklə yaza bilərik:
S = PQR+T´(P+Q+R) Bu düsturlardan istifadə edərək üç girişli bir mərtəbəli 2-lik cəmləyicinin məntiqi sxemini qurmaq olar.
Girişində müəyyən say sistemində olan ədədi çıxışda özünə bərabər başqa say sisteminə çevirən avtomata deşifrator deyilir. İkilik, səkkizlik və tərsinə səkkizlik ikilik deşifratorlar çox yayılmışdır. İkilik səkkizlik deşifratorun girişində 3 mərtəbəli ikilik ədədlər (000, 001, 010, ...) çıxışda səkkizlik rəqəmlərə çevrilir (0,1, 2, 3,...,7). Çap qurğusuna çıxış siqnalları verilsə avtomat öz girişlərindən ikilik ədədi oxuyur və səkkizliyə çevrilir. İkilik səkkizlik deşifratorun çıxışlarından hər birini yazımakinasının düyməsinə bənzətmək olar. TURİNG MASİNİNLARİN FORMAL TEYİNİ
Maşın diskret hücrələrə bölünmüş sonsuz yaddaş lentində işləyir, hər birində maşının əlifbası adlanan sonlu simvollar toplusundan çəkilmiş bir simvol saxlaya bilir . Onun “başı” var ki, maşının işləməsinin istənilən nöqtəsində bu hüceyrələrdən birinin üzərində yerləşdirilir və sonlu vəziyyətlər dəstindən seçilən “dövlət” var. Fəaliyyətinin hər addımında baş öz hücrəsindəki simvolu oxuyur. Sonra simvola və maşının indiki vəziyyətinə əsaslanaraq, maşın eyni hücrəyə simvol yazır və başı bir addım sola və ya sağa hərəkət etdirir, və ya hesablamanı dayandırır. Hansı əvəzedici simvolun yazılacağı və hansı istiqamətə köçürüləcəyi seçimi cari vəziyyətin və oxunan simvolun hər bir kombinasiyası üçün nə ediləcəyini müəyyən edən sonlu cədvələ əsaslanır. Tyurinq maşını 1936-cı ildə Alan Turinq tərəfindən icad edilmişdir və onu " a - machine" (avtomatik maşın) adlandırmışdır. Turinqin doktorluq üzrə məsləhətçisi Alonzo Kilsəsi daha sonra bir araşdırmada "Türinq maşını" terminini istifadə etdi. Türinq maşınları mexaniki hesablamanın gücündə fundamental məhdudiyyətlərin mövcudluğunu sübut etdi. Onlar ixtiyari hesablamaları ifadə edə bilsələr də, minimalist dizaynı onları praktikada hesablamalar üçün yararsız edir: real dünya kompüterləri Turing maşınlarından fərqli olaraq təsadüfi giriş yaddaşından istifadə edən müxtəlif dizaynlara əsaslanır . Turinqin tamlığı , təlimatlar sisteminin Turing maşınını simulyasiya etmək qabiliyyətidir. Tam Turing olan proqramlaşdırma dili nəzəri cəhətdən kompüterlərin yerinə yetirə biləcəyi bütün tapşırıqları ifadə etməyə qadirdir; Sonlu yaddaşın məhdudiyyətləri nəzərə alınmasa, demək olar ki, bütün proqramlaşdırma dilləri Turing tamamlanmışdır. Turing maşını, məlumatları saxlamaq üçün ardıcıl yaddaşdan istifadə edən kanonik maşınla kompüter tərəfindən edilən bütün məlumat manipulyasiyasına nəzarət edən mərkəzi emal vahidinin (CPU) ümumi nümunəsidir . Daha dəqiq desək, bu, əlifbanın etibarlı sətirlərinin bəzi ixtiyari alt çoxluğunu sadalaya bilən maşındır ( avtomat ) ; bu sətirlər rekursiv olaraq sadalana bilən çoxluğun bir hissəsidir . Turing maşınının oxu və yazma əməliyyatlarını yerinə yetirə biləcəyi sonsuz uzunluqlu bir lent var. Turing maşını riyazi olaraq lent üzərində mexaniki olaraq işləyən maşını modelləşdirir. Bu lentdə maşının lent başlığından istifadə edərək bir-bir oxuya və yaza biləcəyi simvollar var. Əməliyyat sonlu elementar göstərişlər toplusu ilə tam müəyyən edilir, məsələn, "42-də, əgər görünən simvol 0-dırsa, 1-i yazın; görünən simvol 1-dirsə, 17 vəziyyətinə keçin; 17-ci vəziyyətdə, əgər görünən simvol 0, 1 yazın və 6 vəziyyətinə dəyişin;" Turinq mexanizmi deyil, "kompüter" adlandırdığı, bu deterministik mexaniki qaydaları köləliklə yerinə yetirən bir insanı təsəvvür edir
1.Maşın müəyyən yəni detərminələşdirilmiş olmalı və muǝyyən qaydalar sistemi əsasında işləməlidir; 2. Maşına ilkin verilənlərin daxil edilməsi mümkün olmalıdır; 3.Maşın üçün əməllərin icra mexanizmi elə olmalıdır ki, alqorit- min icra nəticəsini « Belə icraçı maşınların konstruksiyası ilə bağlı çoxlu təşəbbüslər göstərilmişdir. 1936-cı ildə ingilis riyaziyyatçısı Turinq(1912-1954) belə bir maşın haqqında təklif vermiş və həmin maşın Turinq maşını kimi tarixə daxil edilmişdir. Bu maşın real işləyən maşın deyil, «xəyali» maşındır. Bu maşının real maşından fərqi : 1) bu maşın heç bir səhv edə bilməz, proqramı sırf mexaniki yerinə yetirir. 2) bu maşın potensial sonsuz yaddaşa malikdir, yəni informasiyaların yuxarı sərhədi yoxdur. Turing maşını Lentdən (yaddaşdan), əlifbadan, idarəedici boşluqdan, daxili vəziyyətdən və proqramdan ibarətdir. LENT - Maşında olan lent sonsuz sayda xanalara bölünmüşdür. Burada Lentin ən sol xanasının olmasını şərtləşmək olar, sağa tərəf isə sonsuz sayda qəbul edək. Bəzi hallarda hər iki tǝrǝfə sonsuz olması şərti qoyulur.
Lentin yalnız sonlu sayda xanaları A əlifbasının S0, hərfindən fərqli hərflərlə doldurula bilər. Əgər müəyyən anda hərfləri dəyişmək lazımdırsa onu < Bu o deməkdir ki, Sj, hərfi Si, hərfi ilə əvəz olunmuşdur. a) i-j olsa xanadakı hərf dəyişdirilmişdir. b) i j olduqda hərf dəyişdirilməmişdir. c) i=0 olsa boş xanaya sg hərfi yazılmışdır. d) j=0 olsa, So Si deməkdir ki, baxılan xanadaki Si- hərfi pozulmuşdur. Idarəedici baslig
Idareedici bosluq Bir xanada olan informasiyanı (hərfi) oxuyur (görür, tanıyır) lazım gəldikdə onu dəyişdirir və həm də lent üzrə hərəkət etdirir. 1) idarəedici başlıq ancaq bir xananı görür. 2) idarəedici başlıq maşının bir taktı zamanı soldakı (və ya sağdakı) xanaya keçib onu oxuyur və dayanır. Başlığın hərəkətləri çoxluğunu T={L, R, C} ilə işarə edək. L-sol, R-sağ, C isə yerini dəyişməməsi deməkdir. Daxili vəziyyətlər. Turinq maşının sonlu sayda Q={90, 91,… 9m) daxili vəziyyəti vardır. Hər bir anda bir vəziyyətin başqa vəziyyətlərdən birində ola bilər. Bir taktı yerinə yetirdikdən sonra vəziyyətini dəyişə bilər və növbəti anda xananı yeni və. ziyyətdə oxuya bilər. Hər hansı bir anda qo vəziyyətinə keçdikdə dayanır. qo-passiv və ya son vəziyyət adlanır. Qalan bütün vəziyyətləri aktiv vəziyyətdir. q₁-ǝ başlanğıc vəziyyəti deyilir, yəni maşın həmişə q₁ -vəziyyətində işə başlayır. Program. Əlifbası A{So, S1,...,Sk), daxili vəziyyətlər çoxlu- ğu Q = {q0, q1, qm} olan Turinq maşının işini proqram idarə edir. Proqramın əsas cədvəlləri var.
yeni proqram bir qayda olaraq k+1 sütunu və m sətri olan cədvəl şəklində tərtib olunur. Cədvəlin i-ci (i=0, 1,...,k) sütunu ilə j-ci (j=1, 2,..., m) sətirlərin kəsişməsində üçhərfli söz yazılmışdır.
Siqj Sgtgi, ǝmrdir. Əgər müəyyən anda idarəedici başlıq Si hərfi yazılan xananı oxuyursa və qj, vəziyyətindirsə, o aşağı- dakı işi yerinə yetirir.
Elementar Turing masinilari Burada Turinq maşının əlifbasının A={0,1} olduğunu qəbul edirik. Turinqin maşınlarının müxtəlif variantlarını nəzərdən ke çirək: A-maşını əgər başlanğıc q vəziyyətində boşluq A maşını boş xana üzərindədirsə (boş xananı görürsə) ora 1 yazıb (xananı doldurur) və başlıq dayanır. Maşın başlanğıc anda dolu xana üzǝrində olduqda isə lentdə həmin xanadan sağdakı ilk boş xananı <
Cox noqteler baxilan taktlarda lentin deyismeyen xanalarini gosterir.
2. B maşını. Bu maşının da ancaq (passiv vəziyyət nəzərə alınmazsa) bir daxili vəziyyəti vardır. O1 baxdığı xanadakı (əgər xana boş deyilsə) və ya ondan soldakı ilk xanadakı 1 simvolunu pozur, bir xana sol keçir və dayanır.
C masini. Baslangic xananin sagindaki sifirlar qrupundan sonar yerlesen ilk vahidler qrupunu axtarir ve bu qrupun sonuncu vahidin uzerinde dayanir.
D masini. İki vahidden qrupu arasindaki birinci araligi ancaq bir xana saxlamaqla doldurur.Eger baslangic taktda basliq q1 ve q4 veziyyetlerinde bos xana uzerinde deyilse (q1,0) ve (q4,0) hali sonralarda hec vaxt yaranmir. q1- veziyyeti umumiyyetle hec vaxt tekrarlanmayacaq. q4- veziyyetine ise masin ancaq 1 cap edildikde kece biler.
5. E maşını. Başlanğıc anda dolu xana üzərində yerləşib, soldakı qonşu xanadakı 0 və ya 1 olmasını müəyyən edir. Bundan asılı olaraq q0 və ya vəziyyətinə keçir və əvvəlki xana üzǝrində dayanır. 6. F maşını solda sıfırlar qrupundan sonrakı vahidlər qrupunu axtarıb tapır. 7. G maşını sol tərəfdəki yaxın sifra qədər bütün vahidləri silir. 8. H maşını sağda vahidlər qrupundan sonra bir boş xana buraxıb vahid yazır. A-dan fərqli olaraq soldakı ilk boş xanaya 1 yazır. 9. X maşını dolu xanadan başlayaraq, onu təmizləyir və "1-i soldakı ilk boş xanaya köçürür". 10. K maşını başlanğıc xanadan sağda bir vahid silir. 11. L maşını dolu xanadan başlayaraq solda vahidlər qru- pundan 2 xana sonra dayanır. 12. M maşını iki vəziyyətə malikdir - hansı boş və ya dolu xana üzərində olduğunu müəyyən edir və bundan asılı olaraq bi- rinci x₁ va ya 2-ci passiv vəziyyətə keçir. 13. L maşını. Lentdəki istənilən yazıya tətbiq edilərək qəbul edilən xananı sola köçürür. 14. R masini. Lentdeki istenilen yaziya tetbiq edilerek qebul edlen xanani saga kocurur ve sonra lentdeki yazini deyisdirerek dayanir 15. R masini. Standart veziyyetde lentin en sol xanasinda olmayan ededi qebul ederek standart veziyyetde saga en yaxin eded uzerine kecir TURİNQ MAŞINLARIN KOMPOZİSİYASI Turing maşınların iş sistemindən görürük ki, hətta ən sadə mesələlərin həlli üçün kifayət qədər mürəkkəb Turinq maşınları qurulmalıdır. Qarşıya sual çıxır ki, bir neçə sadə Turinq maşınlarının birləşdirilməsi ilə Turinq maşınlarını layihələndirmək olarmı? Tərif. Tutaq ki, M1 və M₂ Turinq maşınlarıdır. Onlar A={So,S1,…,Sk) elifbasına və uyğun olaraq (q0,q1,….qn) ve (q0,q1,…qm) vəziyyətlərinə malikdirlər. Əlifbası A daxili vəziyyətləri q1,q2,….,qn q1,q2….qm,q0 olan Turing maşınına M1, ve M₂-nin kompoziyasiyası deyilir va M1 M₂ kimi işarə edilir. Buradan alırıq ki, M1 M2, kompozisiyasının başlanğıc veziyyəti M1-maşının başlanğıc vəziyyəti (yəni q1), onun son vəziyyəti isə M₂-nin son vəziyyətidir. Kompozisiya komutativ deyildir, M1 M2 M2 M1 assosiativlik xassəsi doğrudur. (M1 M2)°M, = M₁°(M₂°M3) Turinq maşının özü ilə kompozisiyası M°M = M² M°M°M... M = TERIF: Tutaq ki A=(S0,S1,….,SK) elifbasina uygun olaraq, q0,q1,….,qn,q0,q1,…qm, , ,…., q0
TURİNQ MAŞINLARINDA HESABLAMALAR Hər bir alqoritm verildikdə onu yerinə yetirə bilən Turinq maşını vardır. Bu təklifi dəqiqləşdirmək üçün hər bir alqoritmin rekursiv funksiyasının hesablanmasına gətirilməsinin mümkünlüyü haqqında Görç tezisindən istifadə edirik. Burada Turinq maşınında hesabi funksiyalarının « İlk 2 ədədin kodlarının lentdəki təsvirləri arasında bir və ancaq 1 boş xana olduqda deyəcəyik ki, həmin 2 ədəd ardıcıl yerləş- mişdir. Məsələn, 0011110101110 yazılışında 0 ədədinin yanında solda 3, sağda 2 ədədi yerləşir, başqa sözlə 3, 0 və 2 ədədləri ardıcıl yazılmışdır. Düzəldilmiş Turinq maşını ya arqument kimi istənilən natu ral üçün ədəd üçün və ya ancaq bir neça a üçün c-f(a)-ni hesablayırsa və ya a-nın heç bir qiyməti üçün hesablamır. Əgər hər bir a ucun c=f(a) -nın qiymətini hesablayırsa, onda deyirik ki, f(a) Turing görə hesablanandır. Hər xanada "1" tipli çubuq qoymaqla ədədləri təsvir edirik. « Meselen:
Maşın arqument kimi 1-e o zaman tetbiq edilir ki «<0> anında göstərilən vəziyyətdə olsun. Burada 1, 3-cü xananin üstündə yazılmışdır, bu o deməkdir ki, həmin xana aktivləşir ya başlanğıc situasiya 011'000... vəziyyətini alır. Hesablama başa çatdıqda 0110111 00... halı alınır. Boş xanalar «0»>-lǝ, dolu xanalar 1-lə doldurulur, yəni hansı xanada, «> çubuq varsa 1-lə işarə olunur lentdə. 3 arqumentli funksiyanı aşağıdakı kimi təsvir edək: ilk 2 xananı boş saxlayaq və 3-cü xanadan başlayaraq sərbəst dəyişənlərin nömrəsinə uyğun ardıcıllıqla onların qiymətini qəbul olunan kodlarla yazaq:
Tutaq ki, maşın həmin başlanğıc vəziyyətdən işə başlayır. Əgər ixtiyari x1,x2,...,xn, ədədləri üçün a) T maşının xo passiv vəziyyətinə keçəcəyi; b) Lentdə maşının standart vəziyyətdə gördüyü (n+1) sayda X1, X2,…, Xn, x (x = (x1,x2,...,xn,)) ədədlərinin təsvir olunduğu; c) üzərində başlığın yerləşdiyi xanadan sağdakı bütün xanaların boş olduğu an varsa, deyəcəyik ki, T maşını x= (x1,x2,...,xn) funksiyasını hesablayır. Əgər hər hansı x1, x2,...,xn,, sistemi üçün maşın heç vaxt dayanmazsa (passiv vəziyyətə keçməsə) və ya dayanarsa ancaq b) və c) şərtləri ödənməzsə T maşını funksiyası hesablanır. Məsələn, n = 3 (x1, x2,...,xn) = x1 + x2 + xn dir x1=2, x2 = 1, x3 = 3 Maşının başlangıc vəziyyəti 00111011011110 Sekilde olan lentin masinin dayanan andaki veziyyeti 00111011011110111111100 Olmalidir Artıq deyə bilərik ki, hər hansı rekursiv funksiya verildikdə bu funksiyanı hesablayan Turinq maşını qurmaq olar, yəni ardıcıl gəlmə, sabitə bərabər, eynilik funksiyasını hesablayan, kompozisiya əməlini, induksiya əsasında hesablamanı və ən kiçik ədədin tapılması əməliyyatını yerinə yetirə bilən Turinq maşınlarının varlığı isbat olunmuşdur. Bu təklifin isbatını aparmaq üçün bir neçə Turinq maşının kompozisiyasına baxılır. Post masinlarin formal teyini Bu abstrakt maşınların yaradıcısı Emil Leon Post (1897- 1954) adlı amerikan riyaziyyatçısıdır. O, Alan Türinqdən asılı olmayaraq, ancaq praktiki olaraq onunla eyni bir zamanda (1936-cı ildə) Türinq maşınlarına bənzər maşınları kəşf etmişdir. Əslində Post maşınları Türinq maşınları ilə ekvivalentdir və bunların hər ikisi "alqoritm" anlayışını dəqiqləşdirmək üçün yaradılmışdır Öz maşınını quran zaman Post mümkün qədər sadə abstraksiyadan istifadə etmişdir: informasiya emalı zamanı əməliyyatların sayı minimum olsun, giriş informasiyanın kodlaşdırılması üçün minimum simvoldan istifada olunsun. Post maşını çox sada olması ilə yanaşı, on elementar əməliyyatları yerinə yetirməklə proqramlaşdırmağa imkan verir. Buna baxmayaraq Post maşınında da Türinq maşınındakı kimi, müəyyən mənada, ixtiyari məsələni həll etmək mümkündür. Alqoritmlər nəzəriyyəsində "Post tezisi" belə səslənir: "İxtiyari alqoritmi Post maşınında proqramlaşdırmaq olar". Bu tezis hom də "alqoritm" anlayışının formal təriflərindən biridir. Post tezisi, əslində hipotezdir, onu isbat etmək olmaz. Post tezisini inkar etmək üçün elə bir alqoritm qurmaq tələb olunur ki, onu Post maşınında proqramlaşdırmaq mümkün olmasın, lakin bunu etmək heç kimə müyəssər olmayıb və yəqin ki olmayacaq.
Post masinin informasiya lentinin qurulmasi Post maşını informasiya lentindın, həmçinin oxuyan-yazan qurğudan (başlıq) ibarətdir. Lentin uzunluğu sonsuzdur, eyni ölçülü xanalara bölünmüşdür. Hər məqamda başlıq xanalardan birini göstərir. Hər bir xanada ya "V" işarəsi qeyd olunub, bəzən bunu "1" kimi qeyd edirlər, ya da heç nə qeyd olunmayıb, bunu "O" kimi qəbul edirlər. Lentin vəziyyəti dedikdə "1" və "0" simvollarından ibarət informasiya başa düşülür. Maşının işi zamanı lentin vəziyyəti (məzmunu) dəyişir. Başlıq sağa, yaxud sola sürüşə, və ya yerində qala bilər. Vahid zaman ərzində başlıq üç əməliyyatdan birini icra edə bilir: yazını silir, yazı yazır, qonşu xanaya keçir. Post maşınının vəziyyəti dedikdə lentin məzmunu və başlığın vəziyyəti başa düşülür. Başlıq Post maşınının proqramı asasında iş görür. Proqram nömrələnmiş emrlər ardıcıllığından ibarətdir, her emr, adeten, bir setrda yazılır. Əmrlərin altı tipi var. Post maşının amrlari aşağıdaki kimi icra olunur 1. lenti bir xana qədər sağa sürüşdürüb i nömrəli sətirə keçilir. 2. lenti 1 xana qədər sola sürüşdürüb i nömrəli sətirə keçilir. 3.baxılan xanaya 1 yazılır və i nömrəli sətirə keçilir; 4.baxilan xanaya 0 yazılır i nömrəli sətirə keçirilir, 5. əgər baxılan xanaya 0 yazılıbsa, i nömrəli əmrǝ, I yazılıbsa, j nömrəli əmrə keçməli; 6. alqoritm işini qurtarır. Bunlardan başqa maşının qəzalı vəziyyətlərdə dayanma halları da ola bilər: 1. dolu xanaya yazı yazmaq cəhdi olanda; 2. boş xananı silmək cəhdi olanda; 3.düyünə düşmək, yəni eyni hesablama fraqmentinin mənasız olaraq dəfələrlə təkrarlanması zamanı. Post maşınının işini başlamaq üçün maşının proqramını yazmaq və başlığın ilkin vəziyyətini təyin etmək lazımdır. Əgər maşının işi düyünə düşmürsə, gec-tez dayanırsa, onda deyirlər ki, proqram maşının cari vəziyyətinə tətbiq oluna biləndir.
Post maşını üçün proqramlaşdırmaya aid nümunələr. Misal 1. 3+1 hesablayan proqram yazın. Post maşınında natural ədədləri yadda saxlamaq üçün aşağıdakı qaydadan istifadə olunur. "0" adadini yadda saxlamaq üçün bir xana nişanlanır. "1" ədədi üçün 2 ardıcıl xana, "2" adadi üçün 3 ardıcıl xana nişanlanır və s. Qurğunun başlığı "3" adadinin lent üzərində kodunun solunda birinci boş xanaya tuşlanıb. Helli 1;3 Lentin baslangic veziyyeti
↑ Lentin son veziyyeti
Misal 2. Lentin iki ardıcıl xanasını nişanlamaq tələb olunur. bunlardan birincisi başlığın altında, digəri bunun sağında. Hǝlli: 1. v 2 2. 3 3. v 4 4.! Misal 3. Lent üzərində birdən çox nişanlanmış xanalar var. Nişanlanmış xanalar arasında sayı birdən çox olmayan boş xanalar da mövcuddur. Bunları nişanlamaq tələb olunur. Həlli: Məsələnin şərtindən aydın olur ki, iki ardıcıl boş xana baxılan sözün sonunu göstərir. 1. 2 2. ? 3,1 3. 4 4. ? ,5, 6 5.! 6. 7 7.v 1 Lentin baslangic veziyyeti
Lentin son veziyyeti
Misal 4. Lent üzərində yalnız bir xana nişanlanıb. Başlıq bundan sol tərəfdə müəyyən məsafədə dayanıb. Nişanlanmış xananı silmək və başlığı bunun sol tərəfindəki xana üzərində saxlamaq tələb olunur. Halli: 1. →2 2. ? 1,3 3. x 4 4. 5 5.! Yüklə 229,1 Kb. Dostları ilə paylaş:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||