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

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

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ
ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ СЕМЕЙ ҚАЛАСЫНЫ Ң ШӘК ӘРІМ АТЫНДА ҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ
ФИЗИКА-МАТЕМАТИКА ФАКУЛЬТЕТІ
Тақырыбы: Тьюринг машинасы.
Тьюринг тезисі және

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

Орындаған: Бабаева Ш.Қ
Тексерген: Рысжанова А.С.
Тобы: Т-313
Жоспар:
I.Кіріспе
II.Негізгі бөлім
1. Тьюринг машинасының сыртқы және ішкі
алфавиттері
2. Пост машинасы
3. Командалары
4. Графиктері
III.Пайдаланылған әдебиеттер
IV.Қорытынды

АЛАН МЭТИСОН ТЬЮРИНГ
Тьюринг машинасы бұл өте қарапайым есептеу құрылғысы және
абстрактты орындаушы (абстрактты есептеу машинасы). Тьюринг
машинасы –ақырлы автоматтың кеңейтілген түрі, басқа
орындаушыларды қадамдап есептеу процесін жүзеге асырып
имитациялай алады. Тьюринг машинасын а ғылшын математигі Аллан
Тьюринг 1936 ж. ұсынды.
Тьюринг машинасының құрамы:

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

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

Бір ғана ережеден тұратын Тьюринг
машинасы анықталған (детерминирленген)
Тьюринг машинасы деп аталады, ал егер екі
немесе одан да көп командасы болатын «лента
символы — күй» жұбы бар болса, мұндай
Тьюринг машинасы анықталмаған
(детерминирленбеген) деп аталады.
Жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы.
Мұндай машинаны Тьюринг машинасына өзгерту оңай, ол үшін ұяшықтарды қайта
нөмірлейді, күйлердің санын 2 еселейді, басқару құрылғысының қозғалысын реттейді.

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

Машина штрихталмаған зонада жұмыс істейді. Еер жұмыс кезінде ‘*’ символы кезіксе,
оқу-жазу бастиегі зона шекарасына жеткені. Лентаның «*» сол жа ғында ғылар б ұл
машинада қарастырылмайды. Жаңа Тьюринг машинасының бастапқы күйі бастапқы
машинадағыдай жақта орналасады.
Төменде жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы жұмысының
схемасы берілген:
ТЬЮРИНГ МАШИНАСЫ КЕЛЕСІ ЕРЕЖЕЛЕР
БОЙЫНША ЖҰМЫС ІСТЕЙДІ:

Ережелер Ережелер
q0*→q0R q4a→q4aR
q01→q0R q4=→q4=R
q0×→q1×R q41→q41R
q11→q2aR q4*→q51R
q21→q21L q5*→q2*L
q2a→q2aL q6a→q61R
q2=→q2=L q6×→q7×R
q2×→q3×L q7a→q7aR
q31 → q4aR q71→q2aR
q3a→q3aL q7=→q8=L
q3*→q6*R q8a→q81L
q4×→q4×R q8×→q9H
ТЬЮРИНГ МАШИНАСЫН АНЫҚТАУ ҮШІН
МЫНАЛАР КӨРСЕТІЛЕДІ:

Ішкі алфавит:
Сыртқы алфавит: Q = { q˳,q₁,..qᵣ } ,
A= {a˳,aa₁a
,..aa} мұндағы - qᵣ тоқтаудың
a˳ - ұяшықтың бос күйі. Осыған келгенде
символы машина жұмысын
тоқтатады.q˳ - бастапқы
күй, машина жұмысын
бастайды.
ПОСТ МАШИНАСЫ:
I-2,I-1,I,I+1,I+2
Пост абстракты машинасы жазатын немесе
оқитын түбіртек арқылы не ен жазылып, не
ен оқылатын жеке секцияларға (ұяшықтарға)
бөлінген ақырсыз таспа болып табылады.
Таспа (немесе түбіртек) командаға

байланысты бір адым солға немесе оңға ауыс
қимыл жасай алады. Таспа әрқашан
түбіртектің қарсы алдында секция (ұяшық)
тұратындай етіп тоқтайды.
АБСТРАКТЫ АВТОМАТ КОМАНДАЛАРЫ ӘДЕТТЕ
КЕЛЕСІ ӘРЕКЕТТЕРДІҢ БІРІНЕН ТҰРАДЫ:
Команда Таспаның күйі Командадан
кейін
Түбіртектің оңға
қозғалуы →m

Түбіртектің солға
қозғалуы ←m

М енін жазу m

С енін өшіру m

Басқаруды беру
m1;m2

Тоқтау стоп n
МАРКОВТЫҢ НОРМАЛЬДЫ АЛГОРИТМДЕРІ.
Марковтың нормаль алгоритмі (МНА) — алгоритм ұғымының формалді аны қтамасын
берудің стандарты тəсілдерінің бірі (Тьюринг машинасы сия қты). Бұл ұғымды к өрнекті ке ңес
математигі А.А.Марков(1903-1979жж.) 1940-жылдарды ң со ңында енгізген. Марков
алгоритмдері туралы сөз болғанда, "алгорифм" деп атау қабылдан ған.Бірінен-бірі т әуелсіз
тарихи пайда болған бұл тәсілдер, со ңыра өзара эквивалентті болып шы қты. Алгоритм
ұғымын тұрпаттандырудың негізгі мақсаты мынада: әрт үрлі математикалы қ есептерді ң
алгоритмдік шешімділігі мәселесін шешуге жол ашу, я ғни есеп шешіміне әкелетін алгоритм
құруға бола ма?- деген сұраққа жауап беру.
Марковтың қалыпты алгоритмдері. Марковтың қалыпты алгоритмінің жұмысыны ң
сипаттамасы. Марковтың цифрлы алгоритмы Алгоритм ұғымын т ұрпаттандыру үшін Россия
математигі А.А. Марков ассоциативтік қисапты пайдалануды ұсынды. Ассоциативтік қисапты ң
кейбір ұғымдарын қарастырайы қ. Әріппе ( әртүрлі та ңбаларды ң а қырлы жиынты ғы) бар
болсын. Оны құраушы таңбаларды әріптер деп атаймыз. Әріппе әріптеріні ң кез келген а қырлы
тізбегі (олардың сызықты қатары) осы әріппедегі с өз деп аталады. Әлдебір А әріппесіндегі N
және M екі сөзін қарастырайық. Егер N M-нің б өлігі болса, онда N M-ге енеді дейді. Әлдебір
әріппеде алмастырулардың ақырлы жүйесі берілсін: N–M, S-Т, ..., м ұнда ғы N,M,S,T,... –осы
әріппедегі сөздер. Кез келген N-M алмастыруын әлдебір К с өзіне былай қолдану ға болады: егер
К-да N-сөзінің бір немесе бірнеше кірістері болса, онда оларды ң кез келгенін М-мен
алмастыруға болады және керісінше, егер М-ні ң кірісі бар болса, онда оны N-мен алмастыру ға
болады.
ҚОРЫТЫНДЫ:
Тьюринг машинасы – белгілі бір есептерді шы ғару ға арнал ған қата ң
математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп
аталу себебі оның құрамдас бөлігінің және функцияларыны ң есептеу
техникасына ұқсауында. Тьюринг машинасыны ң есептеу техникасынан
ерекшелігі оның еске сақтау құрылғысы шексіз лентадан т ұруында, ал
есептеу техникасының еске сақтау құрылғысы қаншалы қты үлкен к өлемді
болса да шектеулі. Сондықтан Тьюринг машинасын лентасы шексіз
болғандықтан есептеу техникасы түрінде қолдану ға болмайды.
Марковтың нормальды алгоритміне қойылатын талаптар: алгоритм
қарапайым орындалатын саны шектеулі ережелерден т ұруы тиіс, я ғни
жазбалардың шектеулі болуы талабын қанағаттандыруы тиіс; алгоритм
шектеулі қадамнан соң есепті шешуі тиіс, я ғни әрекеттерді ң шектеулі болу
талабын қанағаттандыруы тиіс; алгоритм барлы қ м үмкін болатын бастап қы
деректер үшін біреу ғана болуы керек, я ғни әмбебапты қ талабын
қанағаттандыруы тиіс; алгоритм қойылған есептің д ұрыс шешімін табуы
керек, яғни дұрыс болу талабын қанағаттандыруы тиіс. Б ұл аны қтамаларда
әрекетті орындаушы көрсетілуі тиіс және ол орындайтын « қарапайым»
операцияларға не жататыны нақтылануы тиіс. Алгоритмді әрт үрлі формада
бейнелеуге , яғни беруге болады.
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ:
1. Мамаев Қ.С., Айдосов Ш.И., Серікбаев Н.Қ.
«Информатиканың теориялық
негіздері»,Шымкент:Әлем,2013. -200б
2. О. Камардинов «Информатика», Алматы,2006
3. А.Бочкин «Методика преподования информатики»,
Минск,Вышейшая школа, 1998-30
4. rankw.ru/k/тьюринг+машинасы/

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

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

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

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

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

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

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

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

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

Пост машинасы

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

Пәндер