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

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

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

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

Орындаған: Журсынова Д.Т
Тобы: Т-313
Тексерген: Рысжанова А.С.
Жоспар:
І.Кіріспе бөлім
ІІ.Негізгі бөлім
1.Тьюринг машинасы.
2.Тьюринг тезисі және оның негіздемесі.
3. Марковтың нормальды алгоритмы.
4.Нормальдау принциптері және оны ң негіздемесі.
5. Марковтың нормальды алгоритмі және Тьюринг
машинасының композициясы.
ІІІ. Қорытынды бөлім
ІV. Пайдаланылған әдебиеттер
Тьюринг машинасы (TM) - математикалық
абстракция, ортақ түрлердің компьютерлер
білдіретін. Бұл алгоритм ұғымын түсулері 1936
жылы Алан Тюринг ұсынған болатын.
Тьюринг машиналары құрылымы
жасушаларының бөлінеді екі бағытта шексіз
белдеуін, және мемлекеттердің ақырғы саны бар
бақылау құрылғыны қамтиды.

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

Оқитын да, жазатын түбіртек жұмысшы әріппесінің әріптерін оқи да, өшіре де, баспаға
шығара да алады. Таспаның әрбір ұяшығы әр мезет А жиыны әрпімен толтырылған.
-“бос орын” әрпі бәрінен жиі кездеседі. Түбіртек әр мезет таспа ұяшығының бірі-
ағымдағы жұмысшы ұяшық үстінде тұрады. Таспатар механизм түбіртек басының көрші
ұяшығының үстінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ
шетіне шығу жағдайы болуы мүмкін. Ол жағдай, тоқтау туралы бұйрықты машинаның
орындау барысындағы машиналық тоқтау немесе апатты (болмайтын)тоқтау болып
табылады.

ТМ жұмыс реті ( жұмысшы әріппесі мен күйлері бар). Тьюринг машинасы кестесі арқылы
өрнектеледі. Бұл кесте төрт тікжолды және (s+1) (t+1) жолы бар матрица болып табылады.

Мұнда арқылы әріппесі мен таспатартар механизм үшін бүйрықтар жиынын біріктіру
элементі белгіленген. Бұйрықтар жиыны: l-таспаны солға орналастыру, r-таспаны оңға
орналастыру, s-машинаны тоқтату; vіj –a0, a1,...., at әріппесі таңбасын таспа ұяшығына
жазудан, не түбіртекті қозғаудан, не машинаны тоқтатудан тұратын ТМ әрекеті; qіj келесі
күй-жай болып табылады.
ТМ мына ережелер бойынша жұмыс істейді:

Егер ТМ qі күйінде болса, түбіртек жұмысшы ұяшығынан aj таңбасын
оқиды. qі aj таңбаларынан басталатын qі aj vіj qіj жолы кестеде бір-а қ рет
кездеседі. Егер vіj- жұмысшы әріппесінің әрпі болса, онда түбіртек
жұмысшы ұяшықтағыны өшіріп, оған осы әріпті апарып жазады. Егер vіj-
таспатартар механизм үшін r немесе l командасы болса, онда таспа о ңға
немесе солға бір ұяшыққа жылжиды (егер таспаның сол жақ шетіне
шығып кетпесе).
Тюринг машинасы А әріппесінің бір таңбасы бар таспаның белгілі ұяшы ғы
үстін оқып-жазатын түбіртектің орны мен бастапқы күйден (әдетте q0)
тұратын бастапқы конфигурацияның бірінен жұмысын бастайды.
ТМ жұмысшы әріппесінде әртүрлі таңбалардың болуы таспада кезкелген
мәтіндік және сандық ақпаратты көрсетуге мүмкіндік береді, ал ТМ
басқару орталығының әртүрлі күйге ауысуы Тюринг машинасының
жұмыстың аралық нәтижелерін жадында ұстауын модельдейді. ТМ
жұмысы ретін анықтайтын кесте тура мағынада программа емес (оны ң
бұйрықтары кезекпен бірінен соң бірі орындалмайды, таспадағы әлдебір
мәтіннің таңбаларын түрлендіруді өрнектейді). ТМ кестесін жиі Тюринг
машинасының сүлбесі деп атайды немесе ТМ құрылысы мен жұмыс істеу
негізі белгілі болғандықтан Тюринг машинасының өзімен теңдестіре
салады.
• Ұлы Отан соғысы кезінде Алан
Тьюринг Блетчли-паркта
орналасқан Үкіметтік Байланыс
Орталығында қызмет атқарды.
Тьюринг Жапония, Германия
және Италия секілді нацисттік
елдер мен олардың
жақтаушыларың құпия
жазбаларын, шартты
белгілерінің мағынасын ашумен
айналысқан. Ол Германияның
әскери-теңіз флотының
хабарламаларының
криптоанализіне жауапты Hut 8
тобын басқарды. Тьюринг
криптоанализдің бірқатар
тәсілдерін ойлап тапты. Соның
ішінде, неміс шифраторы Enigma-
ның құпия жазбаларын шешуді
мақсат ететін Bombe базасы
ойлап табылды.
Тьюринг машинасының құрамы:
екі жағы шексіз лентадан (олар ұяшыққа
бөлінген)
басқару құралы,осы күйлердің біреуінде
болады
күйлер жиыны. Күйлердің саны шектеулі
және нақты беріледі
•Тьюринг машинасын анықтау үшін мыналар көрсетіледі:
•Сыртқы алфавит
•A= {} - ұяшықтың бос символы
•Ішкі күйлердің алфавиті немесе оны ішкі алфавит деп атаймыз.
•Q = { } , мұндағы - тоқтаудың күйі. Осыған келгенде машина жұмысын
тоқтатады. - бастапқы күй, машина жұмысын бастайды.
•Программа (функционалды схема), ол –команда деп аталатын
өрнектердің жиынтығы. Мынандай әрбір жұп үшін () тек бір ғана
команда болады.
•Ереженің жалпы түрі:
•- жаңа күй, ол кейде қалуы мүмкін.
•Тьюринг машинасын сипаттау үшін бастапқы және соңғы күйді (),
лентадағы бастапқы орналасуды және басқару құрылғысының бас
тиегінің орнын көрсету керек.
Марковтың нормальды алгоритмдері.

Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара
эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі
мақсаты мынада: әртүрлі математикалық есептердің алгоритмдік
шешімділігі мәселесін шешуге жол ашу, яғни есеп шешіміне әкелетін
алгоритм құруға бола ма?- деген сұраққа жауап беру. Біз осы мәселенің
қойылуын және есептердің алгоритмдік шешімділігі теориясының кейбір
нәтижелерін қарастырамыз, бірақ алдымен Пост, Тьюринг машиналары
және Марковтың нормалы алгоритмдері мысалында автоматтар
теориясындағы алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті
функциялар теориясы негіздерін талқылаймыз.
Өздеріне арналған программалардың қасиеттері туралы әртүрлі
тұжырымдауды дәлелдеуге арналған абстракты ( яғни шын емес, тек
қиялда ғана бар) Пост пен Тьюринг машиналарын американды қ математик
Эмил Пост пен ағылшын математигі Аллан Тьюринг бірінен-бірі тәуелсіз
(және іс жүзінде бір уақытта) 1936 ж. ұсынды. Бұл машиналар бастапқы
мәліметтерді “енгізіп”, программалар орындалғаннан со ң нәтижені оқуға
мүмкіндік беретін, толығымен анықталған әмбебап орындаушылар болып
табылады. Пост машинасы аса танымал емес, біра қ Тьюринг машинасына
қарағанда әлдеқайда қарапайым.
Марков алгоритмдерінің таралуы жəне бірігуі.
Марковтың нормаль алгоритмі (МНА) — алгоритм ұғымының формалді
анықтамасын берудің стандарты тəсілдерінің бірі (Тьюринг машинасы сияқты). Бұл
ұғымды көрнекті кеңес математигі А.А.Марков(1903-1979жж.) 1940-жылдарды ң со ңында
енгізген. Марков алгоритмдері туралы сөз болғанда, "алгорифм" деп атау қабылдан ған.
Марковтың қалыпты алгоритмдері. Марковтың қалыпты алгоритмінің
жұмысының сипаттамасы. Марковтың цифрлы алгоритмы Алгоритм ұғымын
тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты пайдалануды
ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық. Әріппе (әрт үрлі
таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы таңбаларды әріптер деп
атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі (олардың сызықты қатары) осы
әріппедегі сөз деп аталады. Әлдебір А әріппесіндегі N және M екі сөзін қарастырайық.
Егер N M-нің бөлігі болса, онда N M-ге енеді дейді. Әлдебір әріппеде алмастырулардың
ақырлы жүйесі берілсін: N–M, S-Т, ..., мұндағы N,M,S,T,... –осы әріппедегі сөздер. Кез
келген N-M алмастыруын әлдебір К сөзіне былай қолдануға болады: егер К-да N-сөзінің
бір немесе бірнеше кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады
және керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады.
Тьюринг Test
Тьюринг тест - компьютерлік сөздің адам мағынасында негізділігін тексеру
үшін бапта «Есептеу техникасы және барлау» (Есептеу техникасы мен
барлау) 1950 жылы Алан Тюринг ұсынған сынақ.
Тьюринг компьютерлер, сайып келгенде, оның тест тапсырады деп
болжануда. Ол 2000 жылы 5-минуттық тест кезінде 1 млрд бит (шамамен
119 МБ) жады бар компьютерлік жағдайларды 30% судьяларын алдауға
қабілетті болады деп сенген. Бұл болжау шындыққа жоқ. (Алайда, IBM PC
386 бірінші байқауы Lebnera компьютерлік бағдарламалық қамтамасыз ету
«PC терапевт» 10 5 судьяларын адастыруы мүмкін, бірақ ол нәтиже
есептеуге болады, ал 1994 жылы бәсекелестік күрделі.) Тьюринг, сондай-
ақ, «ойлау машина» комбинациясы деп болжаған бұл оксюморон,
қарастырылмайды, және компьютерлік оқыту (ең заманауи ғалымдар
келісесіз қарағанда) қуатты құру маңызды рөл атқаратын болады.
Қорытынды:
• Тьюринг машинасы – белгілі бір есептерді шығару ға арнал ған қата ң
математикалық құрылым, математикалық аппарат. Тьюринг машинасының
есептеу техникасынан ерекшелігі оның еске са қтау құрыл ғысы шексіз
лентадан тұруында, ал есептеу техникасыны ң еске сақтау құрыл ғысы
қаншалықты үлкен көлемді болса да шектеулі. Сондықтан Тьюринг
машинасын лентасы шексіз болғандықтан есептеу техникасы т үрінде
қолдануға болмайды.
• Марковтың нормальды алгоритміне қойылатын талаптар: алгоритм
қарапайым орындалатын саны шектеулі ережелерден тұруы тиіс, я ғни
жазбалардың шектеулі болуы талабын қанағаттандыруы тиіс; алгоритм
шектеулі қадамнан соң есепті шешуі тиіс, яғни әрекеттерді ң шектеулі болу
талабын қанағаттандыруы тиіс
Пайдаланған әдебиеттер:
А.Шәріпбаев «Информатика» , Алматы, 1992
Жақыпбекова Г.Т Информатика оқыту әдістемесі.-Шымкент, 2011,646
О. Камардинова «Есептеуіштер техника және программалау» Алматы,
2010ж
А.Бочкин. Методика преподавания информатики. Минск, Вышэйшая
школа, 2011-430
Фалин Н.М. Автомобиль Тьюринг//Информатика.- №26.-
2005. - s.12-15
А.Шәріпбаев «Информатика» , Алматы, 1992
О. Камардинов «Информатика», Алматы,2006

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

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

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

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

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

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

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

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

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

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

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

Пәндер