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

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

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

ТЬЮРИНГ МАШИНАСЫ ЖӘНЕ МАРКОВТЫҢ
НОРМАЛЬДІ АЛГОРИТМЫ

Орындаған: Абдулина П. Т-311
Тексерген:Рысжанова А.С.

Семей 2015ж
ЖОСПАР
I. Кіріспе бөлім
А) Тьюринг машинасы және Марковтың нормальді алгоритмі
II. Негізгі бөлім
А) Тьюринг машинасының құрылысы және оның тезисі, негіздемесі
Б) Марковтың норальдау принциптері және оның міндеттері
С) Марковтың нормальді алгоритмі және Тьюринг машинасының
композициясы
III.Қорытынды
IV. Әдебиеттер тізімі
АЛАН ТЬЮРИНГТІҢ ЕСЕПТЕУІШ
МАШИНАСЫ
Алан Мэтисон Тьюринг (ағылш. Alan Mathison Turing;
23.06.1912 - 07.06.1954) — информатиканың дамуына үлкен үлес
қосқан ағылшын математигі, логигі, криптографы. 1937
жылы абстрактілі есептеу және логикалық процестерді,
принципінде алдын ала жоғары дәлдікпен жүзеге асыру
мүмкіндігі туды. Алгоритм ұғымын анықтаудағы
алғашқылардың бірі. "Тюринг машинасы" болды, ол кейіннен
өмірге келген әмбебап-цифрлы есептеу машиналарының
көптеген қасиеттерін бойына жинақтады. Тюринг үйрету
машинасын жасаудың аса маңыздылығын ерекше атап көрсетті,
бұл машина келе-келе тәжірибе жинақтап, сыртқы ортамен Алан Мэтисон Тьюринг
(23.06.1912 - 07.06.1954)
істестік барысында өз "мінез-құлқын" жетілдіре түспек. Тьюринг
Белоусов-Жаботинский секілді ауытқып отыратын реакцияларды
болжай білді.
Белоусов-Жаботинский реакциясы ғылыми бірлестіктерге 1968
жылы ғана таныстырылған болатын. 1950 жылы Алан
компьютердің жасанды зердесін сынауды көздейтін Тьюринг
тестін ұсынды. Тьюринг машинасын оқу информатикаға және
математикаға қызығатын оқушыларға, «Информатика»
мамандығында оқитын студенттерге өте пайдалы.
ТЬЮРИНГ МАШИНАСЫ
МАРКОВТЫҢ НОРМАЛЬДАУ АЛГОРИТМІ
Марковтың алгоритмді деп аталатын жүйе не модель берілген алфавитті ң кез-келген кіру жолына колдану ға болатын
құрылымдық тип операциясына негізделген. Бұл модельдің жа қтауда ғы жол үсті монипуляция типтері на қты т үоде
шектелмеген.Грамматика деп а. Екінші моделінде бізді қызы қтыратын жолдармен берілген монипуляциялар ғана
емес, берілген алфавиттен алынған анықталған қатар жиындарыны ң туындылары. Екі модельде т әжіриберлік
бағалануды көрсетеді не осы б өлінің келесі параграфтарында к өрсетілген мысалдармен д әлелденге. Біз зерттеп
отырған жолдарды манипуляциядардың алғашқы формальдау жүйесі к әдімгі Марков алгоритмі береді. Ол формальді
математикалық жүйе бола тұрып, жолдарды қайта құрудың бірінші тілі СОМІТ-тің негізіні ң қолданылатын СНОБОЛ
программалау тілі арасында таң қаларлық ұқсасты қ бар.
Алгоритм ұғымын формальдау үшін орыс математигі А.А.Марков ассоциативтік есептеулерді қолдануды 1953 жылы
ұсынды.Мұнда алгоритм ауыстырымдар жүйесі түрінде беріледі.Олар қандай символдарды ауыстыру керек екендігін
және бұл ауыстырулар қандай ретпен жүретіндігін көрсетеді.М ұндай т әсілді А.А.Марков елуінші жылдары
ұсынды,ол нормальды алгоритм ұғымын енгізді.
Қарапайым (Марковтік) өнім деп u→w түріндегі жазбаны айтады, м ұнда ғы u ж әне w-V’ жолдары, себебі V алфавиті
құрамына «→» жане «.» символдары кірмейді.
А.А.Марков ұсынған алгоритм ұғымын анықтау тәсілі мына т өмендегідей аны қталатын қалыпты алгоритм
ұғымына негізделген. А әріппесі және В алмастырулар ж үйесі берілсін. Кез келген Р с өзі үшін В-да ғы алмастырулар
сол В-дағы өз ретімен алынады. Егер келісті алмастыру табылмаса, үрдіс то қтатылады. Керісінше жа ғдайда келісімді
алмастырулардың біріншісі алынып, оны ң Р-дағы солжа қ б өлігіні ң бірінші кірісі оны ң о ңжа қ б өлігімен
ауыстырылады. Сонаң соң барлық әрекет жаңадан алынған Р1 үшін қайталанады. Егер В ж үйесіні ң со ңғы
алмастыруы қолданылатын болса, үрдіс тоқтатылады. Мұндай ұй ғарымдар жиыны А әріппесімен ж әне В
алмастырулар жиынымен қалыпты алгоритмді аны қтайды. Үрдіс екі жа ғдайда ғана то қтайды: 1) тиімді алмастыру
табылмаған жағдайда; 2) олардың жиынындағы со ңғы алмастыру пайдалыныл ған жа ғдайда. Әрт үрлі қалыпты
алгоритмдер бір-бірінен әріппелері және алмастырулар ж үйесі ар қылы ерекшеленеді. Натурал сандарды (бірлер
жиынымен берілген) қосуды сипаттайтын қалыпты алгоритмге мысал келтірейік.
Мысал : Әріппе Алмастырулар жүйесі
P сөзі: 11+11=111
Р сөзін Марковтың қалыпты алгоритмі арқылы біртіндеп қайта өңдеу мына кезе ңдер ар қылы өтеді:
Р=11+11+111 P5=+1+111111
P1=1+11+111 Р6=++1111111
P2=+1111+111 P7=+1111111
P3= +111+1111 Р8=1111111
P4=+11+11111 P9=1111111

Марковтың қалыпты алгоритмін кез келген алгоритм берілуіні ң әмбебап т үрі
ретінде қарастыруға болады. Қалыпты алгоритмдер әмбебапты ғы қалыптастыру
принципі арқылы жарияланады: кез келген ақырлы А әріппесінде кез келген
алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм құру ға
болады.Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында тек
А әріппесінің әріптерін пайдаланатын болсақ, А әріппесінде берілген алгоритмге
эквивалент қалыпты алгоритм құрылмайды. Дегенмен, А әріппесін ке ңейту ар қылы
(оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм құру ға болады. Б ұл
жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданылатын болса да
құрылған алгоритмді А әріппесі бойынша алгоритм дейді. Егер N алгоритмі А
әріппесінің кейбір кеңейімінде берілген болса, онда N А әріппесі бойынша қалыпты
алгоритм дейді.
МАШИНАНЫҢ ҚҰРЫЛЫМЫ
Тьюринг машинасы 3 бөліктен тұрады: лентадан, о қитын-жазатын б өлшектен
және логикалық құрылғыдан.

Лента сыртқы жады қызметін атқарады; ол шексіз деп есептеледі - мұның өзі Тьюринг
машинасы модельді құрылғы екенін көрсетеді, өйткені ешбір құрылғы шексіз өлшемді жадыдан
тұрмайды. Лента жеке ұяшықтарға бөлінген, оған (0,1,…,N-1) алфавитінің символдары
жазылады. Тьюринг машинасында бөлшек қозғалмайды, ал лента оған қатыстыоңға не солға
қозғалады. Екінші бір ерекшелігі ол екілік емес қандайда да бір шектелген алфавитінде-сыртқы
алфавитте жұмыс істейді.Онда арнайы символ –бос таңба болады. Оны қандайда да бір ұяшы ққа
орналастырса, ондағы таңбаны өшіреді жіне ұяшықты бос етеді.Лентаның әрбір ұяшығына тек
бір символ жазылуы мүмкін.Лентада сақталаты ақпарат сыртқы алфавитті ң бос та ңбадан өзгеше
таңбалардың шектелген тізбегімен кескінделеді.Автомат(q1,..,qr) күйінің бірінде бола алады
және әр уақыт аралығында (R,L,S) қозғалысының біреуін жүзеге асырады:R-бір ұяшыққао ңға
орын ауыстыру,L-бір ұяшыққа солға орын ауыстыру, S-орнында қалу.Мұндай құрылғының
жұмысын баңдарлама деп аталатын арнайы кесте көмегімен беруге болады.Сол жақ шеткі
бағанда (0,1,…,N-1) (машинаның сыртқы алфавиті)алфавитінің символдары орналасады. (q1,..,qr)
жиыны-машинаның ішкі алфавиті.Бұл кестенің кейбір торларыбос болуы мүмкін. Бұл кесетні ң
q1 qi qr машинаның командалары жазылады, яғни cDq үштік символдары,
мұндағы с-машинаның сыртқы алфавитінңің символы, q-
0 машинаның ішкі алфавитінің символы және D-козғалысын
сиапаттайтын алфавиттің символы, яғни (R,L,S) жиынан.Егер қандай
a cDq да бір уакыт аралығында автоматтың бастиегі лентада а символын
бақылайды және автомат qі күйінде болады, онда машина а номерлі
.
. жолдың qі номерлі бағанның қиылысындағы команданы орындау
. керек. Егер белгіленген торда cDq командасы болса, онда машина
N-1 ағымдағы ұяшыққа с символын жазу керек, q күйіне өтіп D-
козғалысын жүзеге асыру керек. Егер белгіленген тор бос
А q z болса,онда машина тоқтайды. Тьюринг машинасы көмегімен унарлы
∆ z1S z∆S санға 1-ді қосу керек. Сыртқы алфавит А=() жиынымен берілуі
мүмкін, мұндағы1 толтырылған секцияға, ал ∆-бос танбаға
1 q1R z1S келеді,толтырылған бірінің артынан бірі орналасады.

Ішкі алфавит Q=(q,z) жиынымен беріледі, мұндағы q- логикалық құрылғының ж ұмыс к үйіне,
ал z-тоқтатуға сәйкес келеді.Барлық түрлендірулер ережесінің жиынтығы төмендегі функ-дық
схема түрінде көрсетілуі мүмкін.
Баған және жолдарын білдіретін танбалар логикалық құрылғынын ішкі параметрлерін
аныктайтындай, ал олардың қиылысуындағы ұяшықта сырткы команда тұратын функ-дық схема
кесте түрінде құырлады. Дербес жагдайда егер машинаның бастиегі лентаның 1 танбасы бар
секциясын бақыласа және машина (q) жұмыс күйінде болса, онда онын берілген тактідегі ж ұмыс
нәтижесі берілген секцияда бірді қайталау және бір секцияға о ңға өту болып табылады-б ұл
команда былай жазылады q1R. Егер бақыланатын секцияда ∆ болса, онда ∆ 1-ге ауыстырылады,
лентанын ығысуы болмайды және машина токтайды – z1S.
Тьюринг машинасының құрылысы акырлы
автоматқа ұқсас. Автомат келесі схемада жұмыс
істейді. Бірінші кіріс лентадағы символдар
кезекпен саналады. Содан кейін цикл кайталанады.
Тұтас лентақнделгеннен кейін жұмыс аякталады.
Тьюринг машинасының саны әр уакытта әр түрлі
күйде болады. Машинаның жұмысы бастапқы
күйден басталып, жіберілу күйінде (суретте Ү
болып белгіленеді), немесе (N) қайтарылу күйінде
анықталады. Тьюринг машинасының акырлы
автоматтан айырмашылығы, оның лентаның кез-
келген жеріне орналастырылатын, санайтын және
жазба жазба жазатын ерекшелігі бар.

(1, →(N, →,R)
(3,→) →(1, →,R)
(4,→) →(3, →,R)
(3,→) →(1, C,R)
(3,→) →(Y, C,R)
Машинаның құрылымына кіреді
а) шексіз таспа (ұяшықтарға бөлінген).Әрбір ұяшыққа тек бір ғана әріп жазылуы
мүмкін.
б) оқып - жазушы құрылғы.Оқып - жазушы құрылғының шолу жасау, ұяшыққа
жазылған әріпті оқу,ұяшыққа әріпті жазу,жылжу мүмкіндіктері бар.
в) басқару құрылғысы – машинаның программасы көмегімен машина ж ұмысын
басқарады.
г) машинаның бір конфигурациясынан басқасына өтулерін аны қтайтын
машинаның программасы.Егер шолу жасалған ұяшы қ пен машинаны ң жа ғдайы
белгілі болса, онда машинаның конфигурациясы белгілі деп аталады.

Тьюринг машинасының 3 алфавиті бар:
1.Бос символмен берілген сыртқы алфавит –А É {L}.
2.Ішкі алфавит немесе жағдайлар алфавиті Q={q ₀,q ₁,….,qn }. q ₀ жа ғдайы
қорытынды жағдай, q₁–бастапқы жағдай, q₂,q₃,….qn – жұмыс жа ғдайлар деп
аталады.
3.Қозғалыстар алфавиті S={-1,0,+1}.
ЧЁРЧА—ТЬЮЮ РИНГТІҢ ТЕЮЗИСІ
Бұл тезис математикалық теорема болып есептелінбейді.Ол д әллелдене алмайды, тек кана д ұрыс болуы м үмкін.
Чёрча—Тьююрингтің Тею зисі - информатика, кибернетика, т.б. ғылыми облыстарда фундаментальды қ бекіткен. Б ұл
тезисті Алонзо Чёрча пен Аланом Тьюринг 1930-жылдарды ң ортасында ұсынды. Оларды ң айтуынша.
Алгоритмдерді жүзеге асыратын барлық механизмдер, негізінен бір-біріне ұқсас болып келеді. Тезисті ң
тұжырымдауынша,программаға колданатын белгілі бір әдіс м үлдем жо қ. Б ұл бір жа,ынан шынды қ сиякты.
Мысалы, егер сізге екі санды көбейтіңіз деп сұраса, онда сіз м үмкін қарапайым алгоритмді қолдануыныз м үмкін,
ол программаланған болады. Ал егер осы сандарды к өбейткіштерге жіктеуді с ұраса, онда сіз о ған арнайы әдісті
қолданасыз, ол әрине прграммамен жазылған болушы еді.
Ең бастысы, ондай алгоритмдік проблеманы адам шеше алатын, біра қ компьютер шеше алмайтын арнайы әдіс
жоқ. Бірақ бұл керісінше де бола алады. Кез-келген компьютерлік программаны адам өз қолына алып ж әне
ондағы нұсқаулықты қақ бетке қарындашпен орындауы мүмкін. Біра қ, өте маңыздысы, осы Черча-тьюринг
тезистің пайымдауынша, жартылай рекурсивтік функция ая қталып, ол программала ған болуы м үмкін. Осы
тезистің центрлік ортасы деп осы есептеуіштің то қтатылуы. Физикалы қ т ұр ғыда Черча-Тьюринг тезисті ң
ұйғаруынша, кез-келген функцияны физикалық құрылғымен, мүмкін Тьюринг машинасымен есептеле алынады.
МАРКОВТЫҢ НОРАЛЬДАУ ПРИНЦИПТЕРІ ЖӘНЕ
ОНЫҢ МІНДЕТТЕРІ
Алгоритм ұғымын тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты
пайдалануды ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық. Әріппе (әртүрлі
таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы таңбаларды әріптер деп атаймыз.
Әріппе әріптерінің кез келген ақырлы тізбегі (олардың сызықты қатары) осы әріппедегі с өз деп
аталады. Әлдебір А әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса,
онда N M-ге енеді дейді. Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N–M, S-Т, ...,
мұндағы N,M,S,T,... –осы әріппедегі сөздер. Кез келген N-M алмастыруын әлдебір К сөзіне былай
қолдануға болады: егер К-да N-сөзінің бір немесе бірнеше кірістері болса, онда оларды ң кез
келгенін М-мен алмастыруға болады және керісінше, егер М-нің кірісі бар болса, онда оны N-мен
алмастыруға болады.
Р1 және Р2 сөздері әлдебір ассоциативтік қисапта сыбайлас аталады, егер олардың біреуі
екіншісінен мүмкін алмастыруды бір ғана қолданғанда түрлендірілетін болса.
Р,Р1,Р2,...,М cөздерінің тізбегі Р сөзінен М сөзіне әкелетін дедуктивті тізбек аталады, егер осы
тізбектің қатар тұрған екі сөзінің әрқайсысы сыбайлас болса.
Егер Р-дан М-ге тізбек және кері тізбек бар болса, онда Р және М сөздері эквивалентті аталады.
Мысал: Әріппе Алмастырулар
{а,в,с,d,e} ac-ca; abac-abace
аd-da; eca-ae
bc-cb; eda-be
bd-db; edb-be
abcde және acbde сөздері-сыбайлас (bc-cb алмастыру) abcde-cadbe сөздері эквивалентті.
Алгоритмді жазудың мынандай жолдары бар:
1) Табиғи тілдегі жазылуы
2) Белгілі бір түйінді сөздер – терминдер арқылы қыс қаша тізбекті
түрде жазу,мұны қарапайым алгоритмдік тіл деп атайды.
3) Графиктік жолмен(блок – схема арқылы) жазу
4) Программалау тілдеріндегі жазылуы

Алгоритмдер теориясының міндеттеріне есептің алгоритмдік шешімі болмауын формальды т үрде
дәлелдеу, алгоритм күрделілігін асимптотикалық талдау, күрделілік кластарына с әйкес
алгоритмдерді жіктеу, алгоритмдер сапасын салыстырмалы түрде бағалаудың өлшемдерін жасау
және т.б. жатады. Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі
міндеттері:
«Алгоритм» ұғымын формальдау және формальды алгоритмдік жүйелерді (есептеулер модельдерін)
зерттеу;
Есептің алгоритмдік шешімі болмайтынын дәлелдеу;
Алгоритмдердің дұрыстығы мен эквиваленттілігін формальды түрде дәлелдеу;
Есептерді классификациялау, күрделілігі бар кластарды анықтау және зерттеу;
Есептің күрделілігінің теориялық төменгі бағасын дәлелдеу;
Тиімді алгоритмдерді құру әдістерін табу;
Итерациялық алгоритмдердің күрделілігін асимптотикалық талдау;
Рекурсивті алгоритмдерді зерттеу және талдау;
Алгоритмдердің қиындығының нақты функцияларын табу;
Алгоритмдердің классификациясын жасау;
Есептер мен алгоримдердің сыйымдылығы бойынша күрделілігін (жад ресурстары бойынша) зерттеу;
Алгоритмдердің ресурстық тиімділігін салыстырмалы түрде бағалаудың критерийлерін және оларды
салыстырмалы талдаудың әдістерін жасау.
Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық
аспектілерде қолданылады.
МАРКОВТЫҢ НОРМАЛЬДІ АЛГОРИТМІ ЖӘНЕ
ТЬЮРИНГ МАШИНАСЫНЫҢ КОМПОЗИЦИЯСЫ
G қысқартылмаған грамматикасы және Т+тізбекшесі
берілсін. L(G) қатыстығын тексеру үшін V+ -тенбарлы қ
тізбекше жиынын құру жеткілікті, олар ұзынды ғы бойынша
асып кетеді және осы тізбектелген тізбектерден құру, м ұнда
тізбектер қайталанбайды, ұзындығы бойынша реттелген
және бірінші тізбек әрқашан S, ал соңы. Тек оларды ң әр
қайсысы тексеру қалып отыр, ол G нәттиже емес пе. М ұндай
тексеру қадамның ақырғы санында аяқталады.Егер нәтиже
табылса, онда L(G) ал кері жағдайда жоқ. Осыдан кез-келген
рекурсивті саналған, бірақ рекурсивті емес тіл 0 типті, біра қ
бір типті тіл емес екенін шығады. 1 типті грамматикалар ға
сызықты шектелмеген автоматтар эквивалентті, олар һзімен
келесі жүйені анықтайды. УУ Q күйінің соңғы санымен
мұнда q0-ң бастапқы күйі мен FQ – соңғы күйі алынған.
Ұяшықтарға бөлінген лента, оларға # арнайы шектелген маркермен қосыл ған (T
⋃N) символдар жазылады жәнеесептеледі. 0 типті грамматика-жалпы грамматика.
Бұларда тек қана бір ғана
→,≠шектеу � →�,�≠� ережелерінде. 0 типті тілдер рекурсивті
болмайды. Тьюринг машиналары- бұл жетілік (Q,∑,R,L,B,t,q0),м ұнда Q-к үйді ң
ақырлы жиыны,∑-кіріс алфавиті,,R және L - «оң» және«сол» символдар.
Нормаль алгоритмдердің композициясы
Берілген алгоритмнен жаңа алгоритм құру процесі композиция делінеді.
1) Алгоритмнің суперпозициясы. А мен В алгоритмдеріні ң суперпозициясында А алгоритміні ң шы ғыс с өзі В
алгоритмінің кіріс сөзі ретінде қарастырылады. Н əтижені C(p)=B(A(p)) ар қылы өрнектеуге болады. Суперпозиция
кез-келген саны шекті алгоритмдер үшін орындалады.
2) Х алфавитіндегі А,В алгоритмдеріні ң бірігуі деп сол алфавитке қатысты С алфавитін айтады. М ұнда А ж əне В
алгоритмдерінің анықталу облыстарының қиылысуында ғы кез-келген р с өзі A(p) ж əне B(p) қатар орналас қан
сөздеріне түрлендіріледі. Ал басқа сөздер үшін бұл алгоритм аны қталма ған.
Мысалы, X={a,b} алфавиті, A={ab→ba}, B={ba→ab} алгоритмдері ж əне оларды ң аны қталу облыстарыны ң
қиылысуында жатқан аba сөзі берілсін. Нəтиже A(aba)=baa, B(aba)=aab, C(aba)=baaaab түрінде алынады.
3) Алгоритмнің тармақталуы А,В жəне С алгоритмдеріні ң композициясын құрайды. Композиция н əтижесі D
болсын. D алгоритмінің анықталу облысы А,В жəне С үш алгоритміні ң аны қталу облыстарымен 4 беттеседі.Осы
қиылысуда жатқан кез келген р сөзі үшін егер де C(p)=e болса, онда D(p)=A(p) ж əне D(p)=B(p) орындалады.
Мұндағы е– бос жол.
4) Итерация амалы А, В алгоритмдерінің композициясы ар қылы өрнектеледі. Композиция н əтижесі С алгоритмі
арқылы беріледі. Қандай да бір р кіріс сөзінен C(p) шы ғыс с өзі А алгоритмін бірнеше рет тізбектей қолдану
арқылы В алгоритмінен алынады.
Мысалы, X={a,b} алфавиті, A={ab→ba}, B={bbbaa→ab} алгоритмдері берілсін. Демек, C(ababb)=ab н əтижесі
келесі түрде алынады: ababb→baabb→babab→bbaab→bbaba→bbbaa→ab.
1-4 композицияларды нормаль алгоритмдерге қолдануда нормаль алгоритмдер алынады. Кез-келген алгоритмні ң
жұмысын орындайтын универсал алгоритм құру есебіні ң маңызы зор.
Алгорифмдердің композициясы. Марков алгоритмдерді ң таралуы ж әне бірігуі. Бас қарушы алгоритм. Марковты ң
тармақталатын алгоритмі. Есептелінетін функциялар. Егер өзіне эквивалент қалыпты алгоритм құру ға болатын
болса, онда қандай да бір алгоритмді қалыптандырылымды, ал кері жа ғдайда бей қалыптандырылымды деп атау ға
келісейік. Қалыптандыру принципін енді бас қаша айтуға болады: қандай алгоритм болмасын қалыптандырымды.
Бұл негізді қатаң дәлелдеу мүмкін емес, себебі кез келген алгоритм ұғымы қата ң аны қталма ған ж әне қазіргі
кезде белгілі алгоритмдердің бәрі де қалыптандырылымды, ал енді белгілі алгоритмдерден жа ңа алгоритмдер
құруға мүмкіндік беретін алгоритмдер композициясыны ң тәсілдері оларды қалыптындырылатын алгоритмдер
тобы шеңберінен шығармайтындығына негізделген.
Төменде қалыпты алгоритмдерді композициялау тәсілдері келтірілген.
І Алгоритмдер суперпозициясы. А мен В екі алгоритмді суперпозициялау барысында бірінші алгоритмні ң шы ғыс
сөзі екінші В алгоритмінің кіріс сөзі ретінде қарастырылады, суперпозиция н әтижесі С мына т үрде беріледі:
С(р)=В(А(р))
ІІ Алгоритмдерді біріктіру. А мен В алгоритмдеріні ң бір әріппеде біріктірілуі деп, А мен В алгоритмдеріні ң
анықталу облыстарының қиылысын қамтитын кез келген р с өзін қатар жазылған А(р)ж әне В(р) с өздеріне
түрлендіретін сол әріппедегі С алгоритмін айтамыз.
ІІІ Алгоритмдердің тармақталуы. Алгоритмдердің тарма қталуы үш А,В ж әне С алгоритмдеріні ң композициясын
білдіреді; сонымен бірге D алгоритміні ң аны қталу облысы үш бірдей А,В,С алгоритмдеріні ң аны қталу
облыстарының қиылысы болып табылады, ал осы қиылыстағы кез келген р с өзі үшін D(р)=А(р), егер С(р)=е;
D(р)=В(р), егер С(р)=е, мұндағы е- бос жол.
ІV Алгоритмдер итерациясы. Итерация (қайталану) дегеніміз,кез келген р кіріс с өзі үшін с әйкес С(р) с өзі В
алгоритмі түрлендіретін сөз пайда болғанға дейін біртіндеп А алгоритмін бірнеше рет қолдану н әтижесінде
алынатын А мен В екі алгоритмінің С композициясы. Марковты ң қалыпты алгоритмдері теориялы қ құрастыру
құралы ғана емес, ол жасанды интеллект жүйесін жасау барысындағы та ңбады қ т үрлендірулер тілі ретінде
қолданылатын арнайы программалау тілінің негізі де. Түрлендіру м үмкіндігіне қарай Марковты ң қалыпты
алгоритмі Тьюринг машиналаларына пара-пар екендігіні ң қатаң д әлелденбеген.
Пайдаланылған әдебиеттер тізімі
1) Б.Д.Сыдықов “Алгоритм теориясы”, Алматы 2012ж.
2) К. В. Воронцов «Лекции по алгоритмическим композициям», 2012 г
3) В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая «Машина Тьюринга и алгоритмы
Маркова» (Учебно-методическое пособие), Москва, 2006
4) Э.А.Абдыкеримова.Информатиканың теориялық негіздері
5) О.Камардинов “Информатика”, Алматы 2010ж.
6) http://flatik.ru/teyuring-mashinalari
7) http://12fan.ru/613484772.html
8) http://refdt.ru/docs/640/index-4562.html?page=4
9)
https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1
%8C%D0%BD%D1%8B%D0%B9_%
D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
10) http://flatik.ru/teyuring-mashinalari
11) https://kk.wikipedia.org/wiki/%D0%90%D0%BB%D0%B0%D0%BD_%
D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3
12) http://studopedia.info/2-12634.html
Қорытынды

Тьюринг машинасы – белгілі бір есептерді шы ғару ға арнал ған қата ң
математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп
аталу себебі оның құрамдас бөлігінің және функцияларыны ң есептеу
техникасына ұқсауында. Тьюринг машинасыны ң есептеу техникасынан
ерекшелігі оның еске сақтау құрылғысы шексіз лентадан т ұруында, ал есептеу
техникасының еске сақтау құрылғысы қаншалықты үлкен к өлемді болса да
шектеулі. Сондықтан Тьюринг машинасын лентасы шексіз бол ғанды қтан
есептеу техникасы түрінде қолдану ға болмайды.
Марковтың нормаль алгоритмі (МНА) – алгоритм ұғымыны ң формальды
анықтамасын берудің стандартты тәсілдерінің бірі (Тьюринг машинасы
сияқты).Марковтың қалыпты алгоритмін кез келген алгоритм берілуіні ң
әмбебап түрі ретінде қарастыру ға болады. Қалыпты алгоритмдер
әмбебаптығы қалыптастыру принципі арқылы жарияланады: кез келген
ақырлы А әріппесінде кез келген алгоритм үшін о ған пара-пар А әріппесі
бойынша қалыпты алгоритм құру ға болады.
НАЗАРЛАРЫҢЫЗҒА
РАХМЕТ!!!

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

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

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

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

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

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

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

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

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

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

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

Пәндер