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

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

Тьюринг машинасы.
Жоспар
Кіріспе
Алгоритм турталы түсінік
Негізгі бөлім
1.Тьюринг машинасы,құрлысы,қызметі.
2.Тьюринг машинасының композициясы.
3.Морковтың нормальды
алгоритмі,нормальдау принциптері.
Қортынды
Пайдаланылған әдебиет
Алгоитм –бастапқы берілген мәліметтермен
бір мәнде анықталатын нәтиже алу үшін қай
амалды қандай ретпен орындау қажеттігін
белгілейтін есептерді шешу тәсілдерінің дәл
сипаттамасы.Алгоритмды орындау
алгоитмдік процесс деп аталады.Жалпы
Алгоритм деп алдын ала не істеу керек екні
дәл көрсетілген есептеу процесін
айтамыз.Алгоритм-электронды есептеуіш
машинада қолданылатын негізгі ұғымдардың
бірі.
Алгоритмдердің қасиеттері:

Әрбір
Өзгеруге Бір
алгаритм
болмайтын алгаритммен
Дискретті бастапқы
нақты бірнеше есепті
деректі қажет
Нұсқау береді шешуге болады
теді
Алгаритм теориясында
дәлелденгендей,алгаритмнің бір мәнді түсінілуі,ал
оның қадамдары қарапайм жане орындалатын болуы
үшін осы таптарды орындайтын машина болуы
тиіс.Мұндай машиналардың бірі-абстрактілі Тьюринг
машинасы.
Алан Мэтисон Тьюринг (ағылш. Alan Mathison Turing; 23.06.1912 - 07.06.1954) —
информатиканың дамуына үлкен үлес қосқан ағылшын математигі, логигі,криптографы.
1937 жылы абстрактілі есептеу және логикалық процестерді, принципінде алдын ала жо ғары
дәлдікпен жүзеге асыру мүмкіндігі туды. Алгоритм ұғымын аны қтауда ғы алғаш қыларды ң
бірі. "Тюринг машинасы" болды, ол кейіннен өмірге келген әмбебап-цифрлы есептеу
машиналарының көптеген қасиеттерін бойына жинақтады. Тюринг үйрету машинасын
жасаудың аса маңыздылығын ерекше атап көрсетті, бұл машина келе-келе т әжірибе жина қтап,
сыртқы ортамен істестік барысында өз "мінез-құлқын" жетілдіре түспек.
Ұлы Отан соғысы кезінде Алан Тьюринг Блетчли-паркта орналасқан Үкіметтік Байланыс
Орталығында қызмет атқарды. Тьюринг Жапония, Германия жәнеИталия секілді нацисттік
елдер мен олардың жақтаушыларың құпия жазбаларын, шартты белгілеріні ң ма ғынасын
ашумен айналысқан. Ол Германияның әскери-теңіз флотының хабарламаларыны ң
криптоанализіне жауапты Hut 8 тобын басқарды. Тьюринг криптоанализді ң бір қатар т әсілдерін
ойлап тапты. Соның ішінде, неміс шифраторы Enigma-ны ң құпия жазбаларын шешуді ма қсат
ететін Bombe базасы ойлап табылды
Аланның ата-анасы Чхатрапур қаласында қоныстады. Әкесі — Юлиус
Мэтисон Тьюринг , шотландық ақсүйек тегінің өкілі, Империялық үкіметтік
қызметінде жұмыс атқарды. Анасы — Сара Этель (қыз тегі - Стони), ирландық
протестанттық ақсүйектер отбасынан шыққан. Сара бала күтіп жүргенде,
жұбайлар нәрестелері Лондонда туулып тәрбиеленсін деген ниетпен Англияға
қоныс аударды. Алан Тьюринг 1912 жылы маусымның 23-ші жұлдызында
дүниеге келді. Отбасында Аланнан басқа Джон есімді ағасы болды. Әкесінің
үкіметтік қызметі жалғаса берді, сол себепті жұбайларға жиі Гастинг пен Индия
арасында саяхаттауға тура келді. Ұлдары қызметтен босатылған армиялық
жұптың тәрбиесінде қалатын. Дарындылықтың белгілері Аланның бойынан ерте
байқала бастады.
Алты жасында Алан Тьюринг киелі Михаил атындағы мектептің алғаш
табалдырығын аттады.
Мектеп директоры Аланның зеректілігін бірден атап өтті. 1926 жылы 13 жасар
Алан білім беруімен атақты иемденген Шерборн жеке мектебіне ауысты. Оның
мектептегі алғашқы күні 1926 жылғы көтеріліске сәйкес келіп қалды.
Нәтижесінде, Тьюринг Саутгемптон мен Шерборн арасындағы 100 км-ге жуық
қашықтықты велосипедпен өтіп, жол-жөнекей қонақ үйде түнеді.
Bombe базасы
Соғыстан кейін Тьюринг Ұлттық физикалық зертханада мансабын жалғастырды. Оны ң
жобасы бойынша ең алғашқы жадында АСЕ бағдарламасы са қтал ған компьютер ж ұмысы
жүзеге асырылды. 1948 жылы ғалым Макс Ньюманның есептеуіш зертханасына қосылды.
Осы жұмыс орнында Алан Манчестерлік Компьютерлеріні ң жары ққа шы ғуына өз үлесін
қосты. Кейінірек, Тьюрингтің математикалық биологияға қызы ғушылы ғы оянды. Ол
морфогенездің химиялық негіздемесін насихаттайтын ж ұмыстарын жариялады. Сонымен
қатар, Тьюринг Белоусов-Жаботинский секілді ауыт қып отыратын реакцияларды болжай
білді. Белоусов-Жаботинский реакциясы ғылыми бірлестіктерге 1968 жылы ғана
таныстырылған болатын. 1950 жылы Алан компьютердің жасанды зердесін сынауды
көздейтін Тьюринг тестін ұсынды.
1952 жылы Алан Тьюринг Лабушер енгізген түзетпеге сәйкес “өрескел келіссіздік”
қылмысын жасағаны үшін айыпталды. Лабушер ж өндемесі бойынша, гомосексуальды
еркектер қуғынға ұшырауға тиісті болды. Тьюрингке ынты қтық пен сексуальды әуестенуді
басатын гормоналды терапия немесе бас босатнды ғынан айырылуды жаза ретінде та ңдау
құқығы берілді. Ғалым өз таңдауын терапияда тоқтатты. Алан Тьюринг 1954
жылы цианидпен уланып, көз жұмады. Тергеу жұмыстары аяқталғаннан кейін Тьюринг
өзіне қол жұмсады деген қорытындыға келді. Алайда, оны ң анасы “б ұл кездейсо қ орын
алған жазатайым оқиға” деген пікірді ұстанды. Алан Тьюринг
«Ұлыбританиядағы гомофобияның ең атақты құрбаны» лауазымға ие болды.
Тьюрингтің құрметіне информатика саласындағы ең беделді марапат – Тьюринг премиясы
атауы қойылды.
Машинаның
конфигурациясы
Егер келесі шарттардың біреуі орындалса, онда машина конфигурациясын
конфигурациясына көшіреді дейміз:
1) конфигурациясы түрінде, конфигурациясы түрінде, ал - машинаның
бұйрықтарының біреуі;
2) - түрінде, - түрінде, ал - машинаның бұйрықтарының біреуі;
3) - түрінде, - түрінде және - машинаның бұйрықтарының біреуі;
4) - түрінде, - түрінде және - машинаның бұйрықтарының біреуі;
5) - түрінде, - түрінде және - машинаның бұйрықтарының біреуі.
Егер -ден басталатын бұйрық болмаса, онда машина конфигурациясында тоқтайды деп
атаймыз.
Егер конфигурациясына енетін ішкі жағдай болса, кез келген 0 і m-1 шартын
қанағаттандыратын і үшін машина конфигурациясын конфигурациясына көшірсе, ал
конфигурациясында тоқтаса, онда ақырлы конфигурациялар тізбегі машинаның
есептеуі деп аталады. Және есептеуі -ден басталып, -мен аяқталады дейміз. Т
машинаның алгоритмін келесі түрде анықтаймыз:
(Р) = Q орындалуы үшін конфигурациясынан басталып, =Q теңдігі орындалатын
конфигурациясымен аяқталуы керек.
Құрлысы

Таспа БҚ Басқару құрылғысы

Бастиек

... … A1 ... « « А1 .... An-1 An
An+1
Машина бір мезетте бір ғана қимыл істейді. Егер
машинаның оқу тетігі қарастырылып тұрған квадратта
символы тұрса, ал машинаның ішкі жағдайы болса, онда
ол келесі қимылдардың біреуін істейді:
1. Осы квадраттағы символын өшіріп, символын осы
квадратқа жазады;
2. Оң жақтағы көрші квадратқа көшеді;
3. Сол жақтағы көрші квадратқа көшеді;
4. Тоқтайды.
Машинаның жұмысы

Алдыңғы үш жағдайда машина басқа ішкі жағдайға көшіп, келесі қимылға дайын.
Екінші немесе үшінші қимыл кезінде көрші квадрат жоқ болса, онда керек квадрат пайда
болады деп есептейміз.
Бос клеткада символы бар деп есептейік. Онда кез келген уақытта кез келген клеткада
символ бар. Алдыңғы үш қимылды болашақта бұйрық деп атайтын келесі реттелген
төрттіктермен белгілеуге болады:
(1) , (2) , (3) .
Бұл жерде алдыңғы екі символ - машинаның ішкі жағдайы мен қарастырылып отырған
квадраттағы символ, үшіншісі - қандай символ жазылатындығының немесе оқу тетігіні ң
не солға не оңға жылжуының белгісі, ал төртіншісі қандай ішкі жағдайға көшетінін
көрсетеді.
Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде
құрылған алгоритмді байланыстыра аламыз. Осы алфавиттегі кез келген сөзді солдан
оңға қарай жазамыз. Оқу тетігі ең сол шеткі квадратты қарастырып тұрған кезде
машина ішкі жағдайында жұмысты бастайды. Әр қадамда не символ өшіріп, басқа
символ жазады, не көрші квадраттардың біріне көшеді. Егер машина жұмысын тоқтатса,
онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі.
Келесі екі шартты қанағаттандыратын
ақырлы төрттіктер жиынын Тьюринг
машинасы деп атаймыз:
1. Төрттіктердің кез келгені не , не   не
түрінде болады.
2. Алдыңғы екі символдары бірдей болатын
төрттіктер жоқ.
Машинаның қасиетін анықтайтын терминдер
Әр төрттік бұйрық деп аталады.
Бұйрықтарға енетін   символдары сытрқы
жағдайлар деп аталады. Бұйрықтардағы
символдары ішкі жағдайлар деп аталады.
Егер Р - бос болуы мүмкін, ал Q бос емес
сөз болса және - машинаның ішкі жағдайы
болса, онда машинаның конфигурациясы
деп аталады.
Марковтың нормальды алгоритімдері
Алгоритм ұғымын формальдау үшін орыс математигі
А.А.Марков ассоциативтік есептеудердіқолдануды
ұсынды.Мұнда алгоритм ауыстырымдар жүйесі ретінде
беріледі,олар қандай сиволдардыауыстыру керек екендігін
жане бұл ауыстырулар қандай ретпен жүретіндігін
көрсетеді.Мұндай тәсілді А.А.Марков 50-жылдары
ұсынады,ол нормальды алгоритм ұғымын енгізеді
Ассоциативті есептеудің кейбір ұғымдарын
келтіреміз.А алфавиті берілсін.Оны құрайтын
символдарды әріптер деп атаймыз.Алфавиттің
кез-келген шектелген тізбегін ,осы алфавиттегі
сөзі деп атаймыз.Сөздегі символдар саны оның
ұзындығы деп аталады.Ұзындығы нолге тең сөз
бос сөз деп аталады.
Алгоритмді жазудың мындай жолдары бар:

Табиғи тілдегі жазылуы;
Белгілі бір түйінді сөздер-терминдер;
Графиктік жолмен жазу;
Праграммалау тілінде жазылуы;
Алгоритмдік тілдің жалпы ережесі
Алгоитмдік тілде өрнектелген әрбір алгоритмнің мазмұнды қ сипатын ашатын
атауы,яғни тақырыбы болады.Тақырыпты арнайы бөліп к өрсету үшін оны ң
алдында алг түйінді сөзі жазылады.Алгоритмнің тақырыбынан кейін, жа ңа
жолдан бастап,оның командалары жазылады.Ал алгоритм командаларыны ң
басталуы мен аяқталуын көрсету үшін басы жане соңы түйінді сөздері
пайдаланылады.Команда осы екі түйінді с өздің арасында жазылады да, сол
жазылу реті бойынша орындалады.Алгоритмнің бірінен кейін бірі
орындалатын,белгілі бір нәтиже беретін бірнеше командасыны ң тізбегін
серия деп атайды.Алгоритм тақырыбынан кейінгі бөлігі алгоритмні ң т ұл ғасы
деп аталады,ол басы жане соңы түйінді с өздерімен шектеліп т ұрады.Сонымен
алгоитмнің жалпы өрнетелуі мындай болады:
Алг алгоритмнің атауы
Арг A,B,C,D,X
Мәт Y,R1,R2
Басы
Алгоритмнің жолдары
Соңы
Қортынды
Қорта айтқанда информатиканың негізгі
ұғымдарының бірі болып алгоритм ұғымы
саналады.Алгоритм ұғымы-информатиканың
фундаменталды ұғымының бірі.Осы алгоритмдік
процесстерді детерминделген әмбебап орындаушы ның
көмегімен жақсы жүзеге асыруға болады.Тьюринг
машинасын оқу информатикаға жане математикаға
қызығатын оқушыларға ,сондай-ақ “Информатика”
мамандығы бойынша оқитын студенттер үшінде пайдалы.
Пайдаланылған
әдебиет
1.Https://ru.wikipedia.org/wiki/Алгоритм
2 .Б.Д.Сыдықов “Алгоритм теориясы” Алматы 2012ж.
(21-57б.б)
3.Htt://studopida.net/10_104972_cherch—tyuring-tezis
4.Htt://kinostan.kz/news/view?id=443
Назарларыңызға рахмет!!!

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

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

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

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

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

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

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

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

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

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

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

Пәндер