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

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

Тақ ырыбы: Тьюринг машинасы. Тьюринг тезисі жә не оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері жә не оның негіздемесі. Марковтың нормальды алгоритмі жә не Тьюринг машинасының композициясы.
Тексерген: Рысжанова А.С Орындағ ан: Бейсебаева Мадина Т-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 аз қ атемен жауап қ айтаратын алгоритмдер класын BPP класы деп атайды.

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

Пост абстракты машинасы, жазатын немесе оқ итын тү біртек арқ ылы не ен жазылып, не ен оқ ылатын жеке секцияларғ а (ұ яшық тарғ а) бө лінген ақ ырсыз таспа болып табылады. Таспа (немесе тү біртек) командағ а байланысты бір адым солғ а немесе оңғ а ауыс қ имыл жасай алады. Таспа ә рқ ашан тү біртектің қ арсы алдында секция (ұ яшық ) тұ ратындай етіп тоқ тайды. Абстракты автомат командалары ә детте келесі ә рекеттердің бірінен тұ рады Таспаның кү йі Командадан кейін Команда Тү біртектің оңғ а қ озғ алуы  Тү біртектің солғ а қ озғ алуы  М енін жазу m  С енін ө шіру m  Басқ аруды беру  Тоқ тау стоп n

Пайдаланғ ан ақ парат к ө здері: 1.http:// studopedia.net/10_104972_cherch--tyuring-t 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..

НАЗАРЛАРЫҢ ЫЗҒ А РАХМЕТ!


Пән: Физика


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


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

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

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

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

Email: info@stud.kz

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

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