Сайтқа презентация қосу

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

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

Жоспар
Кіріспе Алгоритм турталы түсінік Негізгі бөлім 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

       

Назарларыңызға рахмет!!!


Пән: Автоматтандыру, Техника



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


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

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

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

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

Email: info@stud.kz

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

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