Негізгі есептегіш алгоритмдер: аыры автоматтар; Тьюринг жне Пост машиналары, оай жне иын шешілетін есептер.

Алгоритм[1], алгорифм (аылшынша: algorіthm, algorіsmus — л-Хорезмиді атынан шыан) — бастапы берілген мліметтермен бір мнде аныталатын нтиже алу шін ай амалды (жмысты) андай ретпен орындау ажеттігін белгілейтін есептерді (мселелерді) шешу (математикалы есеп-исаптар орындау, техникалыобъектілерді жобалау, ылыми-зерттеу жмысын жргізу т.б.) тсілдеріні дл сипаттамасы. Алгоритм — математика мен кибернетиканы негізгі ымдарыны бірі. Агоритмді орындау алгоритмдік процесс деп аталады.

Жалпы Алгоритм деп алдын ала не істеу керек екені дл крсетілген есептеу процесін айтады. Есептеу процесі андай болса да алашы мндерден бастап, сол арылы толы аныталан орытынды шыанша жргізіледі. Алгоритм ымыны алышартына алгоритмдік процеспен атар ммкін болатын алашы деректер жиынтыыны нсауы жне орытынды алуа байланысты жргізілген процесті аяталандыын крсететін ереже енеді. Белгілі бір бастапы деректерді жиынына олданылан Алгоритм тиянаты орытындыа келмеуі немесе есептеу барысы аяталмай тоталуы ммкін. Егер есептеу процесі белгілі бір орытынды алумен аяталса (не аяталмай алса), онда Алгоритм ммкін болатын бастапы деректерге олданылады (не олдануа болмайды) деп йарылады.

Алгоритм — азіргі математикада, оны ішінде электронды есептеуіш машинада олданылатын негізгі ымдарды бірі. Белгілі бір тедеу тбіріні жуы мнін кез келген длдікпен табу оан арналан Алгоритммен есептеледі. Компьютерді ке олданылуына байланысты Алгоритм жаа маынаа ие болды. Берілген есепті шешу барысында орындаушыа біртіндеп андай рекеттер жасау керектігін тсінікті рі дл крсететін нсау да Алгоритм деп аталады. Алогритмді орындаушы — адам, ЭЕМнемесе робот. рбір нсау — бйры. Ал орындаушыны жзеге асыра алатын бйрытар жиыны бйрытар жйесі деп аталады. Мысалы, у = (ax + b) (cx - d) функциясын есептеу ЭЕМ-да мынадай рекеттерден ралады:

1. а-ны x-ке кбейту R1 деп,

2. оан b-ны осу нтижесі R2 деп,

3. с-ны х-ке кбейту R3 деп,

4. сх-тан d-ны алу R4 деп,

5. R2-ні R4-ке кбейту у деп белгіленеді.

Алгоритмні бйрытары бірінен кейін бірі кезекпен орындалады. Бадарлама Алгоритм тілінде жазу, бейнелеу маынасын береді. Компьютерде Алгоритмні сызыты, тарматы, циклді, логикалы, модельдік, параллельдік, тізбекті т.б. трлері олданылады.[2]

Алгоритм асиеттері

Алгоритм ымны мнін аша тсетін оны мынадай асиеттері бар:

1. Алгоритм дискретті информациялармен жасалатын рекеттерді таайындайды жне рнектейді. Алгоритмге атысты рекеттерді брі дискретті болады. Алгоритмні жмысына ажетті материалдар ретінде символды мтіндер жне сандар пайдаланылады.

2. Алгоритм бізді алауымыза арай згертуге болмайтын наты нсау алгоритмде не істеу керектігі алдын-ала айын береді. Мысалы, бір есепті шешуді алгоритмі берілсе онда ойланбай-а алгоритмде андай нсаулар берілсе, сол нсауларды берілу ретімен орындаса, есеп шыады. Алгоритмні осы асиетін оны аныталанды асиеті дейміз. Бл жадай адам сияты емес ойлау абілеті жо рылыларды мысалы, компьютерді кмегімен есептерді шешу ммкіндігіне кепілдік берді. Мндай рылылар алгоритмні жарлытарын ойланбастан формальды орындайды. Сондытан алгоритмді есепті шыаруа ажеттіні брі бір мнді аныталу жне атарушыа тсінікті рі наты болуы тиіс.

3. Бір алгоритмні зін бірнеше есепті шешімін табу шін пайдалану ммкіндігі, яни бастапы деректер мндеріні жиынына пайдаланылу ммкіндігі бар. Алгоритмні мндай асиетін кпшілікке бірдейлік, басаша айтанда, жалпылы асиеті деп атайды.

4. рбір алгоритм белгілі бір бастапы деректерді болуын талап етеді жне іздеген нтижені алуа жеткізеді. Мысалы, екі санды осу алгоритмнде осылыштар бастапы деректерге, ал осынды нтижеге жатады. Осылайша, алгоритмдегі рекеттерді белгілі бір санны орындалуынан кейін ажетті нтиже алу ммкіндігі алгоритімні нтижелілігі деп аталады.

Алгоритмді талдау

Алгоритмдерді талдауды негізгі дістері:

1. Сздік-формулалы (табии тілдерде);

2. рылымды немесе блок-схемалар;

3. Арнайы алгоритмдік тілдерді олдану;

4. Граф-схемалар кмегімен (граф – р сызы екі нктені осатын, нктелер мен сызытар жиынтыы). Нктелер шыдар деп аталады, сызытар – абыралар;

5. Петри торыны кмегімен.

Бадарламаны жасау алдында кбінесе сздік-формулалы жне блок-схемалы дістер олданылады. Кейде ассемблер сияты тменгі дегейдегі тілдерде бадарламаны жасау алдында, бадарлама алгоритмін кейбір жоары дегейдегі бадарламалау тіліні конструкцияларын олдана отырып жазады. Крделі бадарламалы жйелер алгоритмдеріні бадарламалы сипаттамаларын олдану ыайлы. Мысалы, ОЖ жмыс істеу принциптерін сипаттау шін Алгола сас жоары дегейдегі бадарламалау тілі олданылды

Сздік-формулалы дісте алгоритм рекеттер тізбегін анытайтын, рамында формулалары бар мтіндік трде жазылады. Мысалы, келесі рнекті мнін анытау ажет болсын: у=2а-(х+6).Сздік-формулалы дістпен бл есепті алгоритмі келесі трде жазылуы ммкін:

1. а жне х мндерін енгізііз.

2. х жне 6-ны осу.

3. а на 2-ге кбейту.

4. 2а –дан (х+6) осындысын азайту.

5. рнекті есептелген нтижесі ретінде у-ті шыару.

Блок-схемада бадарламадаы барлы тарматар, циклдар жне ішкі бадарламалар болуы ажет.

Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (англ. Emil Leon Post), которая отличается от машины Тьюрингабольшей простотой. Обе машины алгоритмически «эквивалентны» и были придуманы для уточнения понятия «алгоритм». В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима также в форме последовательности команд для машины Поста.

Содержание

[скрыть]

• 1Принцип работы

• 2Примеры: сложение и вычитание натуральных чисел P, Q

• 3См. также

o 3.1Другие абстрактные исполнители и формальные системы вычислений

• 4Литература

Принцип работы[править | править вики-текст]

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (см. пример ниже). Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0, либо помеченной меткой 1. За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:

i K j

где i — номер команды, K — действие каретки, j — номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

V j - поставить метку, перейти к j-й строке программы.

X j - стереть метку, перейти к j-й строке программы.

j - сдвинуться влево, перейти к j-й строке программы.

j - сдвинуться вправо, перейти к j-й строке программы.

? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

! – конец программы (стоп).

В команде «стоп» переход на следующую строку не указывается.

После программы запуска возможны варианты:

• работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

• работа может закончиться командой Stop;

• работа никогда не закончится.

 

Тьюринг машинасы- –бл абстрактты орындаушы (абстрактты есептеу машинасы), 1936 жылы алгоритм ымын формальдау шін Алан Тьюринг сынды. абстрактты орындаушы (абстрактты есептеу машинасы). Тьюринг машинасы –аырлы автоматты кеейтілген трі, баса орындаушыларды адамдап есептеу процесін жзеге асырып имитациялай алады (ту ережелерін беру арылы арапайым), адамдар аса арапайым.

 

Тьюринг машинасыны рамы: екі жаы шексіз лентадан (олар яшыа блінген) басару ралы,осы кйлерді біреуінде болады кйлер жиыны. Кйлерді саны шектеулі жне наты беріледі

Басару ралы лентада сола, оа жылжи алады, лентаа андай да бір аырлы алфавитті символдарын жазады не оиды. Бос символ болады, ол лентаны кірістік деректер жазылмаан,алан яшытарына жазылады. Басару ралы ту ережесі бойынша жмыс істейді. ту ережесі Тьюринг машинасында жзеге асатын алгоритм. туді рбір ережесі Тьюринг машинасына аымдаы кймен аымдаы яшытаы символа байланысты, осы клеткаа жаа символ жазуды, жаа кйге туге немесе бір клеткаа оа немесе сола жылжуа бйры береді.

Тьюринг машинасын анытау шін мыналар крсетіледі: Сырты алфавит A= {} - яшыты бос символы Ішкі кйлерді алфавиті немесе оны ішкі алфавит деп атаймыз. Q = { } , мндаы - тотауды кйі. Осыан келгенде машина жмысын тотатады. - бастапы кй, машина жмысын бастайды. Программа (функционалды схема), ол –команда деп аталатын рнектерді жиынтыы. Мынандай рбір жп шін () тек бір ана команда болады. Ережені жалпы трі: - жаа кй, ол кейде алуы ммкін. -ны орнына жазылатын жаа символ Тьюринг машинасын сипаттау шін бастапы жне соы кйді (), лентадаы бастапы орналасуды жне басару рылысыны бас тиегіні орнын крсету керек.

Тьюринг машинасыны кейбір кйлері терминалды деп белгіленеді, бл кйге ту жмысты аяталмаанын, яни алгоритмні тотаанын білдіреді. Бір ана ережеден тратын Тьюринг машинасы аныталан (детерминирленген) Тьюринг машинасы деп аталады, ал егер екі немесе одан да кп командасы болатын «лента символы — кй» жбы бар болса, мндай Тьюринг машинасы аныталмаан (детерминирленбеген) деп аталады.

Жартылай шексіз лентада жмыс істейтін Тьюринг машинасы. Мндай машинаны Тьюринг машинасына згерту оай,

ол шін яшытарды айта нмірлейді, кйлерді санын 2 еселейді, басару рылысыны озалысын реттейді.

* белгісі Тьюринг машинасыны сздігінде

саталмайды, штрихталан зонада шекараа жеткендігін білдіреді, ал бастапы кй жартылай шексіз лентада ай жерде трса, мнда да сол жерде трады. Машина штрихталмаан зонада жмыс істейді. Еер жмыс кезінде ‘*’ символы кезіксе, оу-жазу бастиегі зона шекарасына жеткені. Лентаны «*» сол жаындаылар бл машинада арастырылмайды. Жаа Тьюринг машинасыны бастапы кйі бастапы машинадаыдай жата орналасады.Тменде жартылай шексіз лентада жмыс істейтін Тьюринг машинасы жмысыны схемасы берілген:

Марков алгоритмдеріні таралуы жне бірігуі. Марковты нормаль алгоритмі (МНА) — алгоритм ымыны формалді анытамасын беруді стандарты тсілдеріні бірі (Тьюринг машинасы сияты). Бл ымды крнекті кеес математигі А.А.Марков(1903-1979жж.) 1940-жылдарды соында енгізген. Марков алгоритмдері туралы сз боланда, "алгорифм" деп атау абылданан. Марковты алыпты алгоритмдері. Марковты алыпты алгоритміні жмысыны сипаттамасы. Марковты цифрлы алгоритмы Алгоритм ымын трпаттандыру шін Россия математигі А.А. Марков ассоциативтік исапты пайдалануды сынды. Ассоциативтік исапты кейбір ымдарын арастырайы. ріппе (ртрлі табаларды аырлы жиынтыы) бар болсын. Оны раушы табаларды ріптер деп атаймыз. ріппе ріптеріні кез келген аырлы тізбегі (оларды сызыты атары) осы ріппедегі сз деп аталады. лдебір А ріппесіндегі N жне M екі сзін арастырайы. Егер N M-ні блігі болса, онда N M-ге енеді дейді. лдебір ріппеде алмастыруларды аырлы жйесі берілсін: N–M, S-Т, ..., мндаы N,M,S,T,... –осы ріппедегі сздер. Кез келген N-M алмастыруын лдебір К сзіне былай олдануа болады: егер К-да N-сзіні бір немесе бірнеше кірістері болса, онда оларды кез келгенін М-мен алмастыруа болады жне керісінше, егер М-ні кірісі бар болса, онда оны N-мен алмастыруа болады.

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

Пост машинасы: i-2,i-1,i,i+1,i+2 Пост абстракты машинасы, жазатын немесе оитын тбіртек арылы не ен жазылып, не ен оылатын жеке секциялара (яшытара) блінген аырсыз таспа болып табылады.

Пост абстракты машинасы. Таспа (немесе тбіртек) командаа байланысты бір адым сола немесе оа ауыс имыл жасай алады. Таспа рашан тбіртекті арсы алдында секция (яшы) тратындай етіп тотайды. Абстракты автомат командалары детте келесі рекеттерді бірінен трады: Команда

Тбіртекті оа озалуы Тбіртекті сола озалуы М енін жазу m С енін шіру m Басаруды беру Тотау стоп n Пост машинасында апарат сызы бойынша орналасады да, бірінен со бірі оыла береді, ал ЭЕМ-де апаратты адресі бойынша оуа болады; ЭЕМ командаларыны жиынтыы лде- айда ке рі Пост машинасы командаларына араанда айын, т.с.с.

Таспаны к йі

командадан кейін

орытынды:

Тьюринг машинасы – белгілі бір есептерді шыаруа арналан ата математикалы рылым, математикалы аппарат. Бл аппарат машина деп аталу себебі оны рамдас блігіні жне функцияларыны есептеу техникасына сауында. Тьюринг машинасыны есептеу техникасынан ерекшелігі оны еске сатау рылысы шексіз лентадан труында, ал есептеу техникасыны еске сатау рылысы аншалыты лкен клемді болса да шектеулі. Сондытан Тьюринг машинасын лентасы шексіз боландытан есептеу техникасы трінде олдануа болмайды. Марковты нормальды алгоритміне ойылатын талаптар: алгоритм арапайым орындалатын саны шектеулі ережелерден труы тиіс, яни жазбаларды шектеулі болуы талабын анааттандыруы тиіс; алгоритм шектеулі адамнан со есепті шешуі тиіс, яни рекеттерді шектеулі болу талабын анааттандыруы тиіс; алгоритм барлы ммкін болатын бастапы деректер шін біреу ана болуы керек, яни мбебапты талабын анааттандыруы тиіс; алгоритм ойылан есепті дрыс шешімін табуы керек, яни дрыс болу талабын анааттандыруы тиіс. Бл анытамаларда рекетті орындаушы крсетілуі тиіс жне ол орындайтын «арапайым» операциялара не жататыны натылануы тиіс. Алгоритмді ртрлі формада бейнелеуге , яни беруге болады.

Тьюринг машинасы- –бл абстрактты орындаушы (абстрактты есептеу машинасы), 1936 жылы алгоритм ымын формальдау шін Алан Тьюринг сынды. абстрактты орындаушы (абстрактты есептеу машинасы). Тьюринг машинасы –аырлы автоматты кеейтілген трі, баса орындаушыларды адамдап есептеу процесін жзеге асырып имитациялай алады (ту ережелерін беру арылы арапайым), адамдар аса арапайым.

Тьюринг машинасыны рамы: екі жаы шексіз лентадан (олар яшыа блінген) басару ралы,осы кйлерді біреуінде болады кйлер жиыны. Кйлерді саны шектеулі жне наты беріледі

Басару ралы лентада сола, оа жылжи алады, лентаа андай да бір аырлы алфавитті символдарын жазады не оиды. Бос символ болады, ол лентаны кірістік деректер жазылмаан,алан яшытарына жазылады. Басару ралы ту ережесі бойынша жмыс істейді. ту ережесі Тьюринг машинасында жзеге асатын алгоритм. туді рбір ережесі Тьюринг машинасына аымдаы кймен аымдаы яшытаы символа байланысты, осы клеткаа жаа символ жазуды, жаа кйге туге немесе бір клеткаа оа немесе сола жылжуа бйры береді.

Тьюринг машинасын анытау шін мыналар крсетіледі: Сырты алфавит A= {} - яшыты бос символы Ішкі кйлерді алфавиті немесе оны ішкі алфавит деп атаймыз. Q = { } , мндаы - тотауды кйі. Осыан келгенде машина жмысын тотатады. - бастапы кй, машина жмысын бастайды. Программа (функционалды схема), ол –команда деп аталатын рнектерді жиынтыы. Мынандай рбір жп шін () тек бір ана команда болады. Ережені жалпы трі: - жаа кй, ол кейде алуы ммкін. -ны орнына жазылатын жаа символ Тьюринг машинасын сипаттау шін бастапы жне соы кйді (), лентадаы бастапы орналасуды жне басару рылысыны бас тиегіні орнын крсету керек.

Тьюринг машинасыны кейбір кйлері терминалды деп белгіленеді, бл кйге ту жмысты аяталмаанын, яни алгоритмні тотаанын білдіреді. Бір ана ережеден тратын Тьюринг машинасы аныталан (детерминирленген) Тьюринг машинасы деп аталады, ал егер екі немесе одан да кп командасы болатын «лента символы — кй» жбы бар болса, мндай Тьюринг машинасы аныталмаан (детерминирленбеген) деп аталады.

Жартылай шексіз лентада жмыс істейтін Тьюринг машинасы. Мндай машинаны Тьюринг машинасына згерту оай,

ол шін яшытарды айта нмірлейді, кйлерді санын 2 еселейді, басару рылысыны озалысын реттейді.

* белгісі Тьюринг машинасыны сздігінде

саталмайды, штрихталан зонада шекараа жеткендігін білдіреді, ал бастапы кй жартылай шексіз лентада ай жерде трса, мнда да сол жерде трады. Машина штрихталмаан зонада жмыс істейді. Еер жмыс кезінде ‘*’ символы кезіксе, оу-жазу бастиегі зона шекарасына жеткені. Лентаны «*» сол жаындаылар бл машинада арастырылмайды. Жаа Тьюринг машинасыны бастапы кйі бастапы машинадаыдай жата орналасады.Тменде жартылай шексіз лентада жмыс істейтін Тьюринг машинасы жмысыны схемасы берілген:

Марков алгоритмдеріні таралуы жне бірігуі. Марковты нормаль алгоритмі (МНА) — алгоритм ымыны формалді анытамасын беруді стандарты тсілдеріні бірі (Тьюринг машинасы сияты). Бл ымды крнекті кеес математигі А.А.Марков(1903-1979жж.) 1940-жылдарды соында енгізген. Марков алгоритмдері туралы сз боланда, "алгорифм" деп атау абылданан. Марковты алыпты алгоритмдері. Марковты алыпты алгоритміні жмысыны сипаттамасы. Марковты цифрлы алгоритмы Алгоритм ымын трпаттандыру шін Россия математигі А.А. Марков ассоциативтік исапты пайдалануды сынды. Ассоциативтік исапты кейбір ымдарын арастырайы. ріппе (ртрлі табаларды аырлы жиынтыы) бар болсын. Оны раушы табаларды ріптер деп атаймыз. ріппе ріптеріні кез келген аырлы тізбегі (оларды сызыты атары) осы ріппедегі сз деп аталады. лдебір А ріппесіндегі N жне M екі сзін арастырайы. Егер N M-ні блігі болса, онда N M-ге енеді дейді. лдебір ріппеде алмастыруларды аырлы жйесі берілсін: N–M, S-Т, ..., мндаы N,M,S,T,... –осы ріппедегі сздер. Кез келген N-M алмастыруын лдебір К сзіне былай олдануа болады: егер К-да N-сзіні бір немесе бірнеше кірістері болса, онда оларды кез келгенін М-мен алмастыруа болады жне керісінше, егер М-ні кірісі бар болса, онда оны N-мен алмастыруа болады.

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

Пост машинасы: i-2,i-1,i,i+1,i+2 Пост абстракты машинасы, жазатын немесе оитын тбіртек арылы не ен жазылып, не ен оылатын жеке секциялара (яшытара) блінген аырсыз таспа болып табылады.

Пост абстракты машинасы. Таспа (немесе тбіртек) командаа байланысты бір адым сола немесе оа ауыс имыл жасай алады. Таспа рашан тбіртекті арсы алдында секция (яшы) тратындай етіп тотайды. Абстракты автомат командалары детте келесі рекеттерді бірінен трады: Команда

Тбіртекті оа озалуы Тбіртекті сола озалуы М енін жазу m С енін шіру m Басаруды беру Тотау стоп n Пост машинасында апарат сызы бойынша орналасады да, бірінен со бірі оыла береді, ал ЭЕМ-де апаратты адресі бойынша оуа болады; ЭЕМ командаларыны жиынтыы лде- айда ке рі Пост машинасы командаларына араанда айын, т.с.с.

Таспаны к йі

командадан кейін

орытынды:

Тьюринг машинасы – белгілі бір есептерді шыаруа арналан ата математикалы рылым, математикалы аппарат. Бл аппарат машина деп аталу себебі оны рамдас блігіні жне функцияларыны есептеу техникасына сауында. Тьюринг машинасыны есептеу техникасынан ерекшелігі оны еске сатау рылысы шексіз лентадан труында, ал есептеу техникасыны еске сатау рылысы аншалыты лкен клемді болса да шектеулі. Сондытан Тьюринг машинасын лентасы шексіз боландытан есептеу техникасы трінде олдануа болмайды. Марковты нормальды алгоритміне ойылатын талаптар: алгоритм арапайым орындалатын саны шектеулі ережелерден труы тиіс, яни жазбаларды шектеулі болуы талабын анааттандыруы тиіс; алгоритм шектеулі адамнан со есепті шешуі тиіс, яни рекеттерді шектеулі болу талабын анааттандыруы тиіс; алгоритм барлы ммкін болатын бастапы деректер шін біреу ана болуы керек, яни мбебапты талабын анааттандыруы тиіс; алгоритм ойылан есепті дрыс шешімін табуы керек, яни дрыс болу талабын анааттандыруы тиіс. Бл анытамаларда рекетті орындаушы крсетілуі тиіс жне ол орындайтын «арапайым» операциялара не жататыны натылануы тиіс. Алгоритмді ртрлі формада бейнелеуге , яни беруге болады.