Э. А. Абдыкеримова
Тьюринг машинасының жҧмыс істеу принципі, сипаттамасы
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
| Тьюринг машинасының жҧмыс істеу принципі, сипаттамасы
Бір ленталы Тьюринг машинасын кибернетикалық қҧрылғы ретінде қарастырады және ол келесі элементтерден тҧрады: - ҧяшықтарға бӛлінген шексіз лента; - лента ҧяшықтарында болатын символдарды оқи алатын басқарушы головка; - Тьюринг машинасының жағдайын кӛрсететін ішкі алфавит символы бар жадының ҧяшығы. - лента бойымен головканың қозғалысын қамтамасыз ететін басқарудың механикалық қҧрылғысы - тек оқуға болатын Тьюринг машинасының бҧйрықтарынан тҧратын функционалды схема - жады аймағы. Әдетте, Тьюринг машинасы схемалық тҥрде мынадай тҥрде кӛрсетіледі: 1 i a 2 i a ik a ir a Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, ол бірнеше ҧяшыққа бӛлінген. Жҧмыс барысында машина бар ҧяшықтарға жаңа ҧяшықтарды қоса алады, сондықтан лента екі жағынан да шексіз деп айтуға болады. Лентаның әрбір ҧяшығы кӛп жағдайдың бірінде болуы мҥмкін. Бҧл жағдайларды біз а 0 , а 1 ,...,а m символдарымен немесе басқа символдармен белгілейміз. Осы символдар лента ҧяшықтарында жазылған. Мҧндай символдардың жиынтығы машинаның сыртқы алфавиті деп, ал лентаның ӛзі машинаның сыртқы жадысы деп аталады. Егер ҧяшық бос болса, ол жерде шарты символы орналасқан деп есептейміз. Машинаның жҧмысы кезінде лентаның ҧяшықтары ӛздерінің жағдайын ӛзгертуі де, ӛзгертпеуі де мҥмкін. Жаңа қосылатын барлық ҧяшықтар бос болады. Сонымен, егер қандай да бір уақытта лентаның r ҧяшығы болса және машинаның сыртқы алфавиті мынадай символдардан тҧрса а 0 , а 1 , ...,а m , онда лентаның жағдайы былай жазылады: a і0 , а і1 , ...,а іm . а і1 -солдан бастап орналасқан бірінші ҧяшықтың жағдайы, а і2 - екіншісінің жағдайы, т.с.с. Басқару головкасы. Бҧл лентаның бетімен қозғалатын және белгілі бір уақытта лентаның белгілі бір ҧяшығында тҧрады. Кейде керісінше басқару головкасы қозғалмайды, оған сәйкес лента қозғалады деп есептеледі. Ондай кезде головкаға лентаның ҧяшығының біреуі әлде келесісі кіреді деп есептеледі. Егер лентаның ҧяшығы головкада болса, машина бҧл ҧяшықты оқып немесе қабылдап жатыр деп есептеледі. Машинаның ішкі жадысы - әрбір қараған уақытта белгілі бір жағдайда болатын қҧрылғы. Ішкі жадының жағдайының саны машинамен есептеліп отырады. Ішкі жадының жағдайын мынадай символдармен кӛрсетеміз S 0 , S 1 ,…, S n , олар машинаның сыртқы алфавитіне кірмейді. Ішкі жадының жағдайының символдарының жиынтығы машинаның ішкі алфавиті деп аталады. Si 36 Ішкі жадының жағдайын кӛбінесе машинаның ішкі жағдайлары деп атайды. Бҧл жағдайлардың біреуі бастапқы деп аталады, бҧл жағдайдан машина ӛз жҧмысын бастайды, ол S 0 жағдайы болсын. Тағы да бір арнайы жағдай - аяқтаушы соңғы жағдай. Соңғы жағдайды кӛрсететін символ стоп-символ деп аталады. Стоп-символ ӛрнектеледі. Егер қандай да бір уақытта машинаның ішкі жадысы келсе, ол жҧмысын тоқтатқан болып есептеледі. Машинаның S і қандай да бір ішкі жағдайында ешқандай ӛзгеріс болмауы мҥмкін, олай болса, машина шексіз жасайды деп есептеледі. Машина ерекше механизммен жабдықталған деп есептеледі. Ол қабылданатын ҧяшық пен ішкі жады жағдайына қарай ішкі жады жағдайын, ҧяшық орнын ӛзгерте алады деп есептеледі. Машинаның (Тьюринг) ағымдағы жағдайы немесе оның конфигурациясы деп ағымдағы ҧяшық а j және ішкі жады S 1 жағдайларының жиынтығын айтамыз. Тьюринг машинасының командасы, яғни машина жҧмысы бір жағдайдан белгілі бір уақытта механикалық қҧрылғының бір такті жҧмысынан соң жаңа бір жағдайға ӛтуіне негізделген, содан соң тағы бір такті жҧмысынан жаңа бір жағдайға ӛтуі т.с.с. Егер машина S і ішкі жағдайында а і символды лентаның ҧяшығын қабылдап, ішкі жады жағдайын келесіге S b аударып сонымен бірге қабылданған ҧяшықтың мазмҧнын а r символына аударып, ал басқару головкасы (H) орнында тҧрып, бір ҧяшыққа оңға қарай (R), солға қарай (L) қозғалса, онда машина мынадай команда орындап жатыр деп айтады: S і а і а s S b H S і а і а s S b R S і а і а s S b L Машина орындай алатын барлық командалардың жиынтығы бағдарлама деп аталады. Машина жҧмысы шарт бойынша толықтай оның ішкі жадысының S және қабылданатын ҧяшықтың a j жағдайымен анықталатын болғандықтан, барлық S і a j (і=1, …, n; j=0, 1, …, m) ҥшін машина бағдарламасы тек қана бір a і a j сӛзінен басталатын командадан тҧруы қажет. Сонымен {a 0 , a 1 , …, a n } символды және { S 0 , S 1 , …, S m } жағдайдағы машина бағдарламасы максимум (n+1)(m+1) командаларынан тҧрады. Бағдарламада мынадай жолдардың ӛңделуі мҥмкін емес, бірақ формалды тҥрде олардың болуы қате болып саналмайды. Тьюринг машинасының қарапайым тҥрінде кейбір алгоритмдерді қҧру қиындық туғызады. Мысалы, аралық мәліметтерді бір жерде сақтау немесе бірнеше элемент топтарының символын салыстыру және т.б. Кей жағдайда қосымша лентаның болуы немесе сӛздерді бірнеше лентаға орналастыру дҧрыс шешім қабылдауға кӛмектеседі. Кӛпленталы машина әрбір лентаға арналған алфавитке ие. Машинадағы ленталар бір-бірінен тәуелсіз қозғалады. Алайда машина лентасының жағдайы бірдей, ол жағдай басқару механизмі болып табылады. Бір ленталы машинаны қарастырғанда лента қозғалмайды, ал головка берілген бағытта қозғалады деп есептелді. Бірақ кӛп ленталы машинаны қарастырғанда бҧл жағдай ыңғайлы емес. Себебі ленталар бір-бірінен тәуелсіз, ал бір басқару механизмінде тҥрлі 37 бағыттағы қозғалысты кӛрсету қиын. Сонымен басқару механизмі қозғалмайды, ал ленталар оңға, солға бір-бірінен тәуелсіз қозғалады деп есептеледі. Кӛп ленталы машинаның бағдарламасы - шешімге қарай келесі жазба тәртібі қолданылады: S і {a,b,c}→{a',b',c'}{R,L,H}S j Тьюринг белгілі бір U есептеу машинасының қҧрылысының мҥмкіндігін кӛрсетті, U машинасы универсалды деп аталу себебі онда тҥрлі есептеулерді жасауға болады. Тьюринг машинасының ерекшелігі сәйкес келетін кодтау жолымен кез- келген есептеуді берілген Тьюринг машинасында орындай алуында. Кодтау жеңіл болуы керек. Тьюринг машинасының бағдарламасының кодталуы Тьюрингтің универсалды машинасы ТУМ лентасында берілген Тьюринг машинасының ТМ код номері жазылады. ТУМ осы код номерін оқып, оның лентасында бағдарламасы жазылған машинаның барлық жҧмысын атқаруы қажет. Осыған сәйкес мҧндай машиналарға белгілі бір әдіспен жазылған кіріспе сӛз қажет. Мҥмкін белгілердің саны кӛп болғандықтан, барлық символдар басқа белгілердің ретімен кодталады. Егер А машинасы m символға ие A і және n ішкі жағдайға Sj ие болса, кодты былай кӛрсету керек: A і = 1…1 (A 1 =1, A 2 =11, A 3 =111 және т.б.) S j = 2…2 (S 1 =2, S 2 =22, S 3 =222 және т.б.) R = 3 L = 33 H = 333 Мҧндай жағдайда машина жҧмысының бағдарламасын белгілі бір санмен жазуға болады. Жазбаның екі нҧсқасы бар: 1. Команданың бӛлу белгісі болмайды. Мҧндай жағдайда командаларды мынадай форматта жазу қажет A old S old A new R S new сонда бірінен соң бірі орналасқан екі командалар элементар анализатормен бӛлінеді. 2. Команда бӛлгіші бар. Мысалы Х саны оны 4 саны кодтаймыз. жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|