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

Презентация қосу

Қазақстан Республикасының Білім және Ғылым Министрлігі
Семей қаласының Шәкәрім атындағы Мемлекеттік
Университеті
физика-математика факультеті.

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

Орындаған: Бексейіт Ә.Д
Тобы: Т-311
Тексерген: Рысжанова А.С.
ЖОСПАРЫ:
1. Кіріспе бөлім
а.Алан Тьюринг туралы мағлұмат
2.Негізгі бөлім
а.Тьюринг машинасы
б.Тьюринг машинасының құрылымы
с.Марковтың нормальды
алгоритмдері
3. Қорытынды бөлім
4.Қолданылған ақпарат көздері
Алан Мэтисон Тьюринг
Алан Мэтисон Тьюринг (ағылш. Alan Mathison
Turing; 23.06.1912 - 07.06.1954) —
информатиканың дамуына үлкен үлес қосқан
ағылшын математигі, логигі, криптографы. 1937
жылы абстрактілі есептеу және логикалы қ
процестерді, принципінде алдын ала жоғары
дәлдікпен жүзеге асыру мүмкіндігі туды.
Алгоритм ұғымын анықтаудағы
алғашқылардың бірі. "Тюринг машинасы"
болды, ол кейіннен өмірге келген әмбебап-
цифрлы есептеу машиналарының көптеген
қасиеттерін бойына жинақтады.
Тюринг үйрету машинасын жасаудың аса маңыздылығын
ерекше атап көрсетті, бұл машина келе-келе тәжірибе
жинақтап, сыртқы ортамен істестік барысында өз "мінез-
құлқын" жетілдіре түспек.
Ұлы Отан соғысы кезінде Алан Тьюринг Блетчли-паркта
орналасқан Үкіметтік Байланыс Орталығында қызмет атқарды. Тьюринг
Жапония, Германия және Италия секілді нацисттік елдер мен олардың
жақтаушыларың құпия жазбаларын, шартты белгілерінің мағынасын
ашумен айналысқан. Ол Германияның әскери-теңіз флотының
хабарламаларының криптоанализіне жауапты Hut 8 тобын басқарды.
Тьюринг криптоанализдің бірқатар тәсілдерін ойлап тапты. Соның
ішінде, неміс шифраторы Enigma-ның құпия жазбаларын шешуді мақсат
ететін Bombe базасы ойлап табылды.
Тьюринг машинасы –бұл абстрактты орындаушы (абстрактты
есептеу машинасы), 1936 жылы алгоритм ұғымын формальдау үшін Алан
Тьюринг ұсынды. абстрактты орындаушы (абстрактты есептеу машинасы).
Тьюринг машинасы –ақырлы автоматтың кеңейтілген түрі, басқа
орындаушыларды қадамдап есептеу процесін жүзеге асырып имитациялай
алады (өту ережелерін беру арқылы қарапайым), қадамдар аса қарапайым.

Тьюринг машинасының құрамы:
екі жағы шексіз лентадан (олар
ұяшыққа бөлінген)
басқару құралы,осы күйлердің
біреуінде болады
күйлер жиыны. Күйлердің саны
шектеулі және нақты беріледі
Басқару құралы лентада солға, оңға жылжи алады,
лентаға қандай да бір ақырлы алфавиттің символдарын
жазады не оқиды. Бос символ болады, ол лентаның кірістік
деректер жазылмаған,қалған ұяшықтарына жазылады.
Басқару құралы өту ережесі бойынша жұмыс істейді. Өту
ережесі Тьюринг машинасында жүзеге асатын алгоритм.
Өтудің әрбір ережесі Тьюринг машинасына ағымдағы
күймен ағымдағы ұяшықтағы символға байланысты, осы
клеткаға жаңа символ жазуды, жаңа күйге өтуге немесе бір
клеткаға оңға немесе солға жылжуға бұйрық береді.

Тьюринг машинасын анықтау үшін мыналар көрсетіледі:
Сыртқы алфавит
Тьюринг машинасының кейбір күйлері A= {} - ұяшықтың бос символы
терминалды деп белгіленеді, бұл күйге өту Ішкі күйлердің алфавиті немесе оны ішкі алфавит деп
жұмыстың аяқталмағанын, яғни атаймыз.
Q = { } , мұндағы - тоқтаудың күйі. Осыған келгенде машина
алгоритмнің тоқтағанын білдіреді. Бір
жұмысын тоқтатады. - бастапқы күй, машина жұмысын
ғана ережеден тұратын Тьюринг бастайды.
машинасы анықталған Программа (функционалды схема), ол –команда деп аталатын
(детерминирленген) Тьюринг машинасы өрнектердің жиынтығы. Мынандай әрбір жұп үшін () тек
деп аталады, ал егер екі немесе одан да көп бір ғана команда болады.
командасы болатын «лента символы — Ереженің жалпы түрі:
- жаңа күй, ол кейде қалуы мүмкін.
күй» жұбы бар болса, мұндай Тьюринг
- -ның орнына жазылатын жаңа символ
машинасы анықталмаған Тьюринг машинасын сипаттау үшін бастапқы және соңғы
(детерминирленбеген) деп аталады. күйді (), лентадағы бастапқы орналасуды және басқару
құрылғысының бас тиегінің орнын көрсету керек.
Жартылай шексіз лентада жұмыс істейтін Тьюринг
машинасы. Мұндай машинаны Тьюринг машинасына өзгерту
оңай, ол үшін ұяшықтарды қайта нөмірлейді, күйлердің санын 2
еселейді, басқару құрылғысының қозғалысын реттейді.

* белгісі Тьюринг машинасының сөздігінде
сақталмайды, штрихталған зонада шекараға жеткендігін білдіреді, ал бастапқы күй
жартылай шексіз лентада қай жерде тұрса, мұнда да сол жерде тұрады.
Машина штрихталмаған зонада жұмыс істейді. Еер жұмыс

кезінде ‘*’ символы кезіксе, оқу-жазу бастиегі зона
шекарасына жеткені. Лентаның «*» сол жағындағылар
бұл
машинада қарастырылмайды. Жаңа Тьюринг
машинасының бастапқы күйі бастапқы машинадағыдай жақта
орналасады.Төменде жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы
жұмысының схемасы берілген:
Марков алгоритмдерінің таралуы жəне бірігуі.
Марковтың нормаль алгоритмі (МНА) — алгоритм ұғымының формалді
анықтамасын берудің стандарты тəсілдерінің бірі (Тьюринг машинасы сияқты). Бұл
ұғымды көрнекті кеңес математигі А.А.Марков(1903-1979жж.) 1940-жылдардың
соңында енгізген. Марков алгоритмдері туралы сөз болғанда, "алгорифм" деп атау
қабылданған.
Марковтың қалыпты алгоритмдері. Марковтың қалыпты алгоритмінің
жұмысының сипаттамасы. Марковтың цифрлы алгоритмы Алгоритм ұғымын
тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты
пайдалануды ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық.
Әріппе (әртүрлі таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы
таңбаларды әріптер деп атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі
(олардың сызықты қатары) осы әріппедегі сөз деп аталады. Әлдебір А
әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса, онда N
M-ге енеді дейді. Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N–
M, S-Т, ..., мұндағы N,M,S,T,... –осы әріппедегі сөздер. Кез келген N-M алмастыруын
әлдебір К сөзіне былай қолдануға болады: егер К-да N-сөзінің бір немесе бірнеше
кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады және
керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады.
Марковтың нормальды алгоритмдері.
Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара
эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты
мынада: әртүрлі математикалық есептердің алгоритмдік шешімділігі мәселесін
шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма?- деген
сұраққа жауап беру. Біз осы мәселенің қойылуын және есептердің алгоритмдік
шешімділігі теориясының кейбір нәтижелерін қарастырамыз, бірақ алдымен Пост,
Тьюринг машиналары және Марковтың нормалы алгоритмдері мысалында автоматтар
теориясындағы алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті функциялар
теориясы негіздерін талқылаймыз.
Өздеріне арналған программалардың қасиеттері туралы әртүрлі
тұжырымдауды дәлелдеуге арналған абстракты ( яғни шын емес, тек қиялда ғана бар)
Пост пен Тьюринг машиналарын американдық математик Эмил Пост пен ағылшын
математигі Аллан Тьюринг бірінен-бірі тәуелсіз (және іс жүзінде бір уақытта) 1936 ж.
ұсынды. Бұл машиналар бастапқы мәліметтерді “енгізіп”, программалар
орындалғаннан соң нәтижені оқуға мүмкіндік беретін, толығымен анықталған
әмбебап орындаушылар болып табылады. Пост машинасы аса танымал емес, бірақ
Тьюринг машинасына қарағанда әлдеқайда қарапайым.
Пост машинасы: i-2,i-1,i,i+1,i+2
Пост абстракты машинасы, жазатын немесе о қитын
түбіртек арқылы не ен жазылып, не ен оқылатын жеке
секцияларға (ұяшықтарға) бөлінген ақырсыз таспа
болып табылады.
Пост абстракты машинасы.
Таспа (немесе түбіртек) командаға байланысты бір адым

солға немесе оңға ауыс қимыл жасай алады. Таспа
әрқашан
түбіртектің қарсы алдында секция (ұяшық) тұратындай етіп
тоқтайды. Абстракты автомат командалары әдетте келесі
Команда Таспаның күйі командадан
әрекеттердің бірінен тұрады:
кейін оңға
Түбіртектің
қозғалуы
Түбіртектің солға қозғалуы
М енін жазу m
С енін өшіру m
Басқаруды беру
Тоқтау стоп n

Пост машинасында ақпарат сызық бойынша орналасады да, бірінен соң бірі
оқыла береді, ал ЭЕМ-де ақпаратты адресі бойынша оқуға болады; ЭЕМ
командаларының жиынтығы әлде- қайда кең әрі Пост машинасы
командаларына қарағанда айқын, т.с.с.
Қорытынды:
Тьюринг машинасы – белгілі бір есептерді шығаруға арналған қатаң математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп аталу себебі оны ң құрамдас бөлігінің ж әне функцияларыны ң есептеу техникасына ұқсауында. Тьюринг машинасыны ң есептеу техникасынан ерекшелігі оны ң еске са қтау
құрылғысы шексіз лентадан тұруында, ал есептеу техникасының еске сақтау құрыл ғысы қаншалықты үлкен көлемді болса да шектеулі. Сонды қтан Тьюринг машинасын лентасы шексіз бол ғанды қтан есептеу техникасы т үрінде қолдануға болмайды.
Марковтың нормальды алгоритміне қойылатын талаптар: алгоритм қарапайым орындалатын саны шектеулі ережелерден т ұруы тиіс, я ғни жазбаларды ң шектеулі болуы талабын қана ғаттандыруы тиіс; алгоритм шектеулі қадамнан со ң есепті шешуі тиіс, я ғни әрекеттерді ң шектеулі болу талабын қана ғаттандыруы
тиіс; алгоритм барлық мүмкін болатын бастапқы деректер үшін біреу ғана болуы керек, я ғни әмбебапты қ талабын қана ғаттандыруы тиіс; алгоритм қойыл ған есептің д ұрыс шешімін табуы керек, я ғни д ұрыс болу талабын қана ғаттандыруы тиіс. Б ұл аны қтамаларда әрекетті орындаушы к өрсетілуі тиіс ж әне ол
орындайтын «қарапайым» операцияларға не жататыны на қтылануы тиіс. Алгоритмді әрт үрлі формада бейнелеуге , я ғни беруге болады.
Қолданылған ақпарат көздері:
1. А.Шәріпбаев «Информатика» , Алматы, 1992
2. О. Камардинов «Информатика», Алматы,2006
3. studopedia.ru/5_164228_algoritm-abstraktili-m.
4. rankw.ru/k/тьюринг+машинасы/

Ұқсас жұмыстар

Тьюринг тезисі және оның негіздемесі

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

Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі

Марковтың нормальды алгоритмі

Тьюринг машинасы. Алан Мэтисон Тьюринг

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

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

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

Тьюринг машинасы және Пост машинасы

Программалау тілдері туралы ақпарат

Пәндер