ТЬЮРИНГ МАШИНАСЫ жә не Марковтың нормальді алгоритмы

Семей қаласының Шәкәрім атындағы мемлекеттік университеті Физика - математика факультеті,математика мамандығы

ТЬЮРИНГ МАШИНАСЫ жә не Марковтың нормальді алгоритмы

Орындаған: Абдулина П. Т-311 Тексерген:Рысжанова А.С.

Семей 2015ж

Жоспар
I. Кіріспе бөлім А) Тьюринг машинасы және Марковтың нормальді алгоритмі II. Негізгі бөлім А) Тьюринг машинасының құрылысы және оның тезисі, негіздемесі Б) Марковтың норальдау принциптері және оның міндеттері С) Марковтың нормальді алгоритмі және Тьюринг машинасының композициясы III.Қорытынды IV. Әдебиеттер тізімі

Алан тьюрингтің есептеуіш машинасы
Алан Мэтисон Тьюринг (ағылш. Alan Mathison Turing; 23.06.1912 - 07.06.1954) — информатиканың дамуына үлкен үлес қосқан ағылшын математигі, логигі, криптографы. 1937 жылы абстрактілі есептеу және логикалық процестерді, принципінде алдын ала жоғары дәлдікпен жүзеге асыру мүмкіндігі туды. Алгоритм ұғымын анықтаудағы алғашқылардың бірі. "Тюринг машинасы" болды, ол кейіннен өмірге келген әмбебап-цифрлы есептеу машиналарының көптеген қасиеттерін бойына жинақтады. Тюринг үйрету машинасын жасаудың аса маңыздылығын ерекше атап көрсетті, бұл машина келе-келе тәжірибе жинақтап, сыртқы ортамен істестік барысында өз "мінезқұлқын" жетілдіре түспек. Тьюринг Белоусов-Жаботинский секілді ауытқып отыратын реакцияларды болжай білді. Белоусов-Жаботинский реакциясы ғылыми бірлестіктерге 1968 жылы ғана таныстырылған болатын. 1950 жылы Алан компьютердің жасанды зердесін сынауды көздейтін Тьюринг тестін ұсынды. Тьюринг машинасын оқу информатикаға және математикаға қызығатын оқушыларға, «Информатика» мамандығында оқитын студенттерге өте пайдалы.

Алан Мэтисон Тьюринг (23.06.1912 - 07.06.1954)

Тьюринг машинасы

Марковтың нормальдау алгоритмі
Марковтың алгоритмді деп аталатын жүйе не модель берілген алфавиттің кез-келген кіру жолына колдануға болатын құрылымдық тип операциясына негізделген. Бұл модельдің жақтаудағы жол үсті монипуляция типтері нақты түоде шектелмеген.Грамматика деп а. Екінші моделінде бізді қызықтыратын жолдармен берілген монипуляциялар ғана емес, берілген алфавиттен алынған анықталған қатар жиындарының туындылары. Екі модельде тәжіриберлік бағалануды көрсетеді не осы бөлінің келесі параграфтарында көрсетілген мысалдармен дәлелденге. Біз зерттеп отырған жолдарды манипуляциядардың алғашқы формальдау жүйесі кәдімгі Марков алгоритмі береді. Ол формальді математикалық жүйе бола тұрып, жолдарды қайта құрудың бірінші тілі СОМІТ-тің негізінің қолданылатын СНОБОЛ программалау тілі арасында таң қаларлық ұқсастық бар. Алгоритм ұғымын формальдау үшін орыс математигі А.А.Марков ассоциативтік есептеулерді қолдануды 1953 жылы ұсынды.Мұнда алгоритм ауыстырымдар жүйесі түрінде беріледі.Олар қандай символдарды ауыстыру керек екендігін және бұл ауыстырулар қандай ретпен жүретіндігін көрсетеді.Мұндай тәсілді А.А.Марков елуінші жылдары ұсынды,ол нормальды алгоритм ұғымын енгізді. Қарапайым (Марковтік) өнім деп u→w түріндегі жазбаны айтады, мұндағы u және w-V’ жолдары, себебі V алфавиті құрамына «→» жане «.» символдары кірмейді. А.А.Марков ұсынған алгоритм ұғымын анықтау тәсілі мына төмендегідей анықталатын қалыпты алгоритм ұғымына негізделген. А әріппесі және В алмастырулар жүйесі берілсін. Кез келген Р сөзі үшін В-дағы алмастырулар сол В-дағы өз ретімен алынады. Егер келісті алмастыру табылмаса, үрдіс тоқтатылады. Керісінше жағдайда келісімді алмастырулардың біріншісі алынып, оның Р-дағы солжақ бөлігінің бірінші кірісі оның оңжақ бөлігімен ауыстырылады. Сонаң соң барлық әрекет жаңадан алынған Р1 үшін қайталанады. Егер В жүйесінің соңғы алмастыруы қолданылатын болса, үрдіс тоқтатылады. Мұндай ұйғарымдар жиыны А әріппесімен және В алмастырулар жиынымен қалыпты алгоритмді анықтайды. Үрдіс екі жағдайда ғана тоқтайды: 1) тиімді алмастыру табылмаған жағдайда; 2) олардың жиынындағы соңғы алмастыру пайдалынылған жағдайда. Әртүрлі қалыпты алгоритмдер бір-бірінен әріппелері және алмастырулар жүйесі арқылы ерекшеленеді. Натурал сандарды (бірлер жиынымен берілген) қосуды сипаттайтын қалыпты алгоритмге мысал келтірейік. Мысал : Әріппе Алмастырулар жүйесі P сөзі: 11+11=111 Р сөзін Марковтың қалыпты алгоритмі арқылы біртіндеп қайта өңдеу мына кезеңдер арқылы өтеді:

Р=11+11+111 P5=+1+111111 P1=1+11+111 Р6=++1111111 P2=+1111+111 P7=+1111111 P3= +111+1111 Р8=1111111 P4=+11+11111 P9=1111111

Марковтың қалыпты алгоритмін кез келген алгоритм берілуінің әмбебап түрі ретінде қарастыруға болады. Қалыпты алгоритмдер әмбебаптығы қалыптастыру принципі арқылы жарияланады: кез келген ақырлы А әріппесінде кез келген алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм құруға болады.Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында тек А әріппесінің әріптерін пайдаланатын болсақ, А әріппесінде берілген алгоритмге эквивалент қалыпты алгоритм құрылмайды. Дегенмен, А әріппесін кеңейту арқылы (оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм құруға болады. Бұл жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданылатын болса да құрылған алгоритмді А әріппесі бойынша алгоритм дейді. Егер N алгоритмі А әріппесінің кейбір кеңейімінде берілген болса, онда N А әріппесі бойынша қалыпты алгоритм дейді.

Машинаның Құрылымы
Тьюринг машинасы 3 бөліктен тұрады: лентадан, оқитын-жазатын бөлшектен және логикалық құрылғыдан.

Лента сыртқы жады қызметін атқарады; ол шексіз деп есептеледі - мұның өзі Тьюринг машинасы модельді құрылғы екенін көрсетеді, өйткені ешбір құрылғы шексіз өлшемді жадыдан тұрмайды. Лента жеке ұяшықтарға бөлінген, оған (0,1, ,N-1) алфавитінің символдары жазылады. Тьюринг машинасында бөлшек қозғалмайды, ал лента оған қатыстыоңға не солға қозғалады. Екінші бір ерекшелігі ол екілік емес қандайда да бір шектелген алфавитінде-сыртқы алфавитте жұмыс істейді.Онда арнайы символ –бос таңба болады. Оны қандайда да бір ұяшыққа орналастырса, ондағы таңбаны өшіреді жіне ұяшықты бос етеді.Лентаның әрбір ұяшығына тек бір символ жазылуы мүмкін.Лентада сақталаты ақпарат сыртқы алфавиттің бос таңбадан өзгеше таңбалардың шектелген тізбегімен кескінделеді.Автомат(q1,..,qr) күйінің бірінде бола алады және әр уақыт аралығында (R,L,S) қозғалысының біреуін жүзеге асырады:R-бір ұяшыққаоңға орын ауыстыру,Lбір ұяшыққа солға орын ауыстыру, S-орнында қалу.Мұндай құрылғының жұмысын баңдарлама деп аталатын арнайы кесте көмегімен беруге болады.Сол жақ шеткі бағанда (0,1, ,N-1) (машинаның сыртқы алфавиті)алфавитінің символдары орналасады. (q1,..,qr) жиыны-машинаның ішкі алфавиті.Бұл кестенің кейбір торларыбос болуы мүмкін. Бұл кесетнің торларына

q1 0 1 a . . . N-1

qi

qr

cDq

А 1

q z1S q1R

z z S z1S

Ішкі алфавит Q=(q,z) жиынымен беріледі, мұндағы q- логикалық құрылғының жұмыс күйіне, ал z-тоқтатуға сәйкес келеді.Барлық түрлендірулер ережесінің жиынтығы төмендегі функ-дық схема түрінде көрсетілуі мүмкін. Баған және жолдарын білдіретін танбалар логикалық құрылғынын ішкі параметрлерін аныктайтындай, ал олардың қиылысуындағы ұяшықта сырткы команда тұратын функ-дық схема кесте түрінде құырлады. Дербес жагдайда егер машинаның бастиегі лентаның 1 танбасы бар секциясын бақыласа және машина (q) жұмыс күйінде болса, онда онын берілген тактідегі жұмыс нәтижесі берілген секцияда бірді қайталау және бір секцияға оңға өту болып табылады-бұл команда былай жазылады q1R. Егер бақыланатын секцияда болса, онда 1-ге ауыстырылады, лентанын ығысуы болмайды және машина токтайды – z1S.

Тьюринг машинасының құрылысы акырлы автоматқа ұқсас. Автомат келесі схемада жұмыс істейді. Бірінші кіріс лентадағы символдар кезекпен саналады. Содан кейін цикл кайталанады. Тұтас лентақнделгеннен кейін жұмыс аякталады. Тьюринг машинасының саны әр уакытта әр түрлі күйде болады. Машинаның жұмысы бастапқы күйден басталып, жіберілу күйінде (суретте Ү болып белгіленеді), немесе (N) қайтарылу күйінде анықталады. Тьюринг машинасының акырлы автоматтан айырмашылығы, оның лентаның кез-келген жеріне орналастырылатын, санайтын және жазба жазба жазатын ерекшелігі бар.

Машинаның құрылымына кіреді
а) шексіз таспа (ұяшықтарға бөлінген).Әрбір ұяшыққа тек бір ғана әріп жазылуы мүмкін. б) оқып - жазушы құрылғы.Оқып - жазушы құрылғының шолу жасау,ұяшыққа жазылған әріпті оқу,ұяшыққа әріпті жазу,жылжу мүмкіндіктері бар. в) басқару құрылғысы – машинаның программасы көмегімен машина жұмысын басқарады. г) машинаның бір конфигурациясынан басқасына өтулерін анықтайтын машинаның программасы.Егер шолу жасалған ұяшық пен машинаның жағдайы белгілі болса, онда машинаның конфигурациясы белгілі деп аталады. Тьюринг машинасының 3 алфавиті бар: 1.Бос символмен берілген сыртқы алфавит- –А É {L}. 2.Ішкі алфавит немесе жағдайлар алфавиті Q={q ₀,q ₁, .,qn }. q ₀ жағдайы қорытынды жағдай, q₁–бастапқы жағдай, q₂,q₃, .qn – жұмыс жағдайлар деп аталады. 3.Қозғалыстар алфавиті S={-1,0,+1}.

Чёрча—Тью́рингтің Те́зисі
Бұл тезис математикалық теорема болып есептелінбейді.Ол дәллелдене алмайды, тек кана дұрыс болуы мүмкін. Чёрча—Тью́рингтің Те́зисі - информатика, кибернетика, т.б. ғылыми облыстарда фундаментальдық бекіткен. Бұл тезисті Алонзо Чёрча пен Аланом Тьюринг 1930-жылдардың ортасында ұсынды. Олардың айтуынша. Алгоритмдерді жүзеге асыратын барлық механизмдер, негізінен бір-біріне ұқсас болып келеді. Тезистің тұжырымдауынша,программаға колданатын белгілі бір әдіс мүлдем жоқ. Бұл бір жа,ынан шындық сиякты. Мысалы, егер сізге екі санды көбейтіңіз деп сұраса, онда сіз мүмкін қарапайым алгоритмді қолдануыныз мүмкін, ол программаланған болады. Ал егер осы сандарды көбейткіштерге жіктеуді сұраса, онда сіз оған арнайы әдісті қолданасыз, ол әрине прграммамен жазылған болушы еді. Ең бастысы, ондай алгоритмдік проблеманы адам шеше алатын, бірақ компьютер шеше алмайтын арнайы әдіс жоқ. Бірақ бұл керісінше де бола алады. Кез-келген компьютерлік программаны адам өз қолына алып және ондағы нұсқаулықты қақ бетке қарындашпен орындауы мүмкін. Бірақ, өте маңыздысы, осы Черча-тьюринг тезистің пайымдауынша, жартылай рекурсивтік функция аяқталып, ол программалаған болуы мүмкін. Осы тезистің центрлік ортасы деп осы есептеуіштің тоқтатылуы. Физикалық тұрғыда Черча-Тьюринг тезистің ұйғаруынша, кезкелген функцияны физикалық құрылғымен, мүмкін Тьюринг машинасымен есептеле алынады.

Марковтың норальдау принциптері және оның міндеттері
Алгоритм ұғымын тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты пайдалануды ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық. Әріппе (әртүрлі таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы таңбаларды әріптер деп атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі (олардың сызықты қатары) осы әріппедегі сөз деп аталады. Әлдебір А әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса, онда N M-ге енеді дейді. Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N–M, S-Т, ..., мұндағы N,M,S,T,... –осы әріппедегі сөздер. Кез келген N-M алмастыруын әлдебір К сөзіне былай қолдануға болады: егер К-да N-сөзінің бір немесе бірнеше кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады және керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады. Р1 және Р2 сөздері әлдебір ассоциативтік қисапта сыбайлас аталады, егер олардың біреуі екіншісінен мүмкін алмастыруды бір ғана қолданғанда түрлендірілетін болса. Р,Р1,Р2,...,М cөздерінің тізбегі Р сөзінен М сөзіне әкелетін дедуктивті тізбек аталады, егер осы тізбектің қатар тұрған екі сөзінің әрқайсысы сыбайлас болса. Егер Р-дан М-ге тізбек және кері тізбек бар болса, онда Р және М сөздері эквивалентті аталады. Мысал: Әріппе Алмастырулар {а,в,с,d,e} ac-ca; abac-abace аd-da; eca-ae bc-cb; eda-be bd-db; edb-be abcde және acbde сөздері-сыбайлас (bc-cb алмастыру) abcde-cadbe сөздері эквивалентті.

Алгоритмді жазудың мынандай жолдары бар:
1) Табиғи тілдегі жазылуы 2) Белгілі бір түйінді сөздер – терминдер арқылы қысқаша тізбекті түрде жазу,мұны қарапайым алгоритмдік тіл деп атайды. 3) Графиктік жолмен(блок – схема арқылы) жазу 4) Программалау тілдеріндегі жазылуы

Алгоритмдер теориясының міндеттеріне есептің алгоритмдік шешімі болмауын формальды түрде дәлелдеу, алгоритм күрделілігін асимптотикалық талдау, күрделілік кластарына сәйкес алгоритмдерді жіктеу, алгоритмдер сапасын салыстырмалы түрде бағалаудың өлшемдерін жасау және т.б. жатады. Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі міндеттері: «Алгоритм» ұғымын формальдау және формальды алгоритмдік жүйелерді (есептеулер модельдерін) зерттеу; Есептің алгоритмдік шешімі болмайтынын дәлелдеу; Алгоритмдердің дұрыстығы мен эквиваленттілігін формальды түрде дәлелдеу; Есептерді классификациялау, күрделілігі бар кластарды анықтау және зерттеу; Есептің күрделілігінің теориялық төменгі бағасын дәлелдеу; Тиімді алгоритмдерді құру әдістерін табу; Итерациялық алгоритмдердің күрделілігін асимптотикалық талдау; Рекурсивті алгоритмдерді зерттеу және талдау; Алгоритмдердің қиындығының нақты функцияларын табу; Алгоритмдердің классификациясын жасау; Есептер мен алгоримдердің сыйымдылығы бойынша күрделілігін (жад ресурстары бойынша) зерттеу; Алгоритмдердің ресурстық тиімділігін салыстырмалы түрде бағалаудың критерийлерін және оларды салыстырмалы талдаудың әдістерін жасау. Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады.

Марковтың нормальді алгоритмі және Тьюринг машинасының композициясы

Ұяшықтарға бөлінген лента, оларға # арнайы шектелген маркермен қосылған (T ⋃N) символдар жазылады жәнеесептеледі. 0 типті грамматика-жалпы грамматика. Бұларда тек қана бір ғана шектеу

Пән: Информатика


Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь