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

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

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

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

Орындаған: Бейсебаева
Мадина
Т-311 топ
Жоспары:
I.Кіріспе бөлім
1.Алан Тьюрингтің өмірбаяны
II.Негізгі бөлім
1. Тьюрингтің алгоритмдік
машинасы
2. Марковтың нормальды
алгоритмы
III.Қорытынды бөлім
1.Қорытынды
2.Пайдаланған ақпарат көздері
Туған жері:
Лондон, Англия
Қайтыс болған жері:
Вилмслоу, Чешир, Англия
Ғылыми аясы:
= математика, логика,
криптография, информатика
Жұмыс орны:
Кембридж университеті
Ұлыбританияның Ұлттық физика
зертханасы
Мемлекеттік байланыс орталығы
Манчестер университеті
Альма-матер:
Корольдік колледж, Кембридж
Принстон университеті
Атақты шәкірттері:
Робин Ганди
Несімен белгілі:
Тьюринг машинасы, Тьюринг тесті
Алан Тьюрингтің өмірбаяны
Алан Мэтисон Тьюринг (ағылш. Alan Mathison Turing;
23.06.1912 - 07.06.1954) — информатиканың дамуына
үлкен үлес қосқан ағылшын математигі, логигі,
криптографы. 1937 жылы абстрактілі есептеу және
логикалық процестерді, принципінде алдын ала
жоғары дәлдікпен жүзеге асыру мүмкіндігі туды.
Алгоритм ұғымын анықтаудағы алғашқылардың бірі.
"Тюринг машинасы" болды, ол кейіннен өмірге келген
әмбебап-цифрлы есептеу машиналарының көптеген
қасиеттерін бойына жинақтады. Тюринг үйрету
машинасын жасаудың аса маңыздылығын ерекше атап
көрсетті, бұл машина келе-келе тәжірибе жинақтап,
сыртқы ортамен істестік барысында өз "мінез-құлқын"
жетілдіре түспек. 1952 жылы Алан Тьюринг Лабушер
енгізген түзетпеге сәйкес “өрескел келіссіздік”
қылмысын жасағаны үшін айыпталды. Лабушер
жөндемесі бойынша, гомосексуальды еркектер қуғынға
ұшырауға тиісті болды. Тьюрингке ынтықтық пен
сексуальды әуестенуді басатын гормоналды терапия
немесе бас босатндығынан айырылуды жаза ретінде
таңдау құқығы берілді. Ғалым өз таңдауын терапияда
тоқтатты. Алан Тьюринг 1954 жылы цианидпен уланып,
Ұлы Отан соғысы кезінде Алан Тьюринг Блетчли-паркта
орналасқан Үкіметтік Байланыс Орталығында қызмет атқарды.
Тьюринг Жапония, Германия және Италия секілді нацисттік елдер
мен олардың жақтаушыларың құпия жазбаларын, шартты
белгілерінің мағынасын ашумен айналысқан. Ол Германияның
әскери-теңіз флотының хабарламаларының криптоанализіне
жауапты Hut 8 тобын басқарды. Тьюринг криптоанализдің
бірқатар тәсілдерін ойлап тапты. Соның ішінде, неміс
шифраторы Enigma-ның құпия жазбаларын шешуді мақсат ететін
Bombe базасы ойлап табылды.
Тьюринг машинасы –бұл абстрактты орындаушы (абстрактты
есептеу машинасы), 1936 жылы алгоритм ұғымын формальдау
үшін Алан Тьюринг ұсынды. абстрактты орындаушы
(абстрактты есептеу машинасы). Тьюринг машинасы –ақырлы
автоматтың кеңейтілген түрі, басқа орындаушыларды
қадамдап есептеу процесін жүзеге асырып имитациялай алады
(өту ережелерін беру арқылы қарапайым), қадамдар аса
қарапайым.
Тьюринг машинасының құрамы:
1 ) екі жағы шексіз лентадан (олар ұяшыққа бөлінген)
2) басқару құралы,осы күйлердің біреуінде болады
3) күйлер жиыны. Күйлердің саны шектеулі және нақты
беріледі
Басқару құралы лентада солға, оңға жылжи алады, лентаға
қандай да бір ақырлы алфавиттің символдарын жазады не
оқиды. Бос символ болады, ол лентаның кірістік деректер
жазылмаған,қалған ұяшықтарына жазылады.
.Басқару құралы өту ережесі бойынша жұмыс істейді. Өту
ережесі Тьюринг машинасында жүзеге асатын алгоритм. Өтудің
әрбір ережесі Тьюринг машинасына ағымдағы күймен ағымдағы
ұяшықтағы символға байланысты, осы клеткаға жаңа символ
жазуды, жаңа күйге өтуге немесе бір клеткаға оңға немесе
солға жылжуға бұйрық береді.
Тьюринг машинасының кейбір күйлері терминалды деп
Тьюринг машинасының
үлгілері
Тьюринг бойынша толықтық.
Тьюринг машинасында басқа машиналарды (Пост
машинасын, Марковтың нормальды алгоритмдерін) және
кірістік деректерді қандай да бір алгоритм арқылы
шығыстық деректерге түрлендіретін компьютердің
программаларын имитациялауға болады. Ол сызықты
жады бар қарапайым есептеу машинасы, формальды
ережелер бойынша кірістік деректерді элементар (яғни әр
әрекет тек жадтың бір ұяшығын ғана өзгертеді және
әрекеттер саны ақырлы) әрекеттер тізбегі арқылы
түрлендіреді.
Тьюринг машинасы бір ұяшықтан тұратын жадысы бар
машина болғандықтан, оның әрекеттері қарапайым және
мүмкін әрекеттердің саны шектеулі. Тьюринг машинасы
қарапайым болса да, онда басқа машинада
есептелінетіндердің барлығын есептеуге болады. Бірақ ол
есептеулер қарапайым әрекеттердің тізбегі болу керек.
Осы қасиетті толықтық деп аталады.
Тьюринг машинасын имитациялай алатын абстрактты
орындаушыларды Тьюринг бойынша толық деп атайды.
Унарлық санау жүйесінде сандарды көбейтуге арналған
Тьюринг машинасының мысалы.
Машина келесі ережелер бойынша жұмыс
істейді:
Ережелер
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
Төменде жартылай шексіз пентада жұмыс
істейтін Тьюринг машинасы жұмысының
схемасы берілген.

Тьюрингтің ықтималдық машинасында лентадағы күйден және
лентаның мәндерінен бірнеше күйге өтудің мүмкіндігі болады.
Бұл машина өтудің нұсқасын қандай да бір ықтималдықпен
таңдайды (монета лақтыру) және анықталмаған
(недетерминированная) Тьюринг машинасына ұқсас.
Тьюрингтің ықтималдық машинасында полиномды уақыт
ішінде жұмысын аяқтап 1/3 аз қатемен жауап қайтаратын
Марковтың нормальды алгоритмы
Бірінен-бірі тәуелсіз тарихи пайда болған бұл
тәсілдер, соңыра өзара эквивалентті болып шықты.
Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты
мынада: әртүрлі математикалық есептердің алгоритмдік
шешімділігі мәселесін шешуге жол ашу, яғни есеп
шешіміне әкелетін алгоритм құруға бола ма?- деген
сұраққа жауап беру. Біз осы мәселенің қойылуын және
есептердің алгоритмдік шешімділігі теориясының кейбір
нәтижелерін қарастырамыз, бірақ алдымен Пост,
Тьюринг машиналары және Марковтың нормалы
алгоритмдері мысалында автоматтар теориясындағы
алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті
функциялар теориясы негіздерін талқылаймыз.
Өздеріне арналған программалардың қасиеттері
туралы әртүрлі тұжырымдауды дәлелдеуге арналған
абстракты ( яғни шын емес, тек қиялда ғана бар) Пост
пен Тьюринг машиналарын американдық математик Эмил
Пост пен ағылшын математигі Аллан Тьюринг бірінен-бірі
тәуелсіз (және іс жүзінде бір уақытта) 1936 ж. ұсынды.
Бұл машиналар бастапқы мәліметтерді “енгізіп”,
программалар орындалғаннан соң нәтижені оқуға
Пост абстракты машинасы, жазатын немесе оқитын түбіртек
арқылы не ен жазылып, не ен оқылатын жеке секцияларға
(ұяшықтарға) бөлінген ақырсыз таспа болып табылады.
Таспа (немесе түбіртек) командаға байланысты бір адым
солға немесе оңға ауыс қимыл жасай алады. Таспа әрқашан
түбіртектің қарсы алдында секция (ұяшық) тұратындай етіп
тоқтайды. Абстракты автомат командалары әдетте келесі
әрекеттердің
Команда біріненТаспаның
тұрады күйі Командадан кейін
Түбіртектің оңға
қозғалуы

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

М енін жазу m

С енін өшіру m

Басқаруды беру

Тоқтау стоп n
Пайдаланған ақпарат көздері:
1.http://
studopedia.net/10_104972_cherch--
tyuring-tezisi.html

2.https://kk.wikipedia.org/wiki/
Алан_Тьюринг
3.http://
kk.convdocs.org/docs/index-7752.
html

4.http://sabakka.ucoz.kz/load/
aza_sha_referattar/matematika/al..
НАЗАРЛАРЫҢЫЗҒА
РАХМЕТ!

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

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

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

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

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

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

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

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

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

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

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

Пәндер