Бір ленталы Тьюринг машинасын кибернетикалық құрылғы ретінде қарастырады және ол келесі элементтерден тұрады

жүктеу/скачать 0.57 Mb. бет 1/2 Дата 09.10.2023 өлшемі 0.57 Mb. #480217

Бір ленталы Тьюринг машинасын кибернетикалық құрылғы ретінде қарастырады және ол келесі элементтерден тұрады: - ұяшықтарға бөлінген шексіз лента; - лента ұяшықтарында болатын символдарды оқи алатын басқарушы головка; - Тьюринг машинасының жағдайын көрсететін ішкі алфавит символы бар жадының ұяшығы. - лента бойымен головканың қозғалысын қамтамасыз ететін басқарудың механикалық құрылғысы - тек оқуға болатын Тьюринг машинасының бұйрықтарынан тұратын функционалды схема - жады аймағы. Әдетте, Тьюринг машинасы схемалық түрде мынадай түрде көрсетіледі: Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, ол бірнеше ұяшыққа бөлінген. Жұмыс барысында машина бар ұяшықтарға жаңа ұяшықтарды қоса алады, сондықтан лента екі жағынан да шексіз деп айтуға болады. Лентаның әрбір ұяшығы көп жағдайдың бірінде болуы мүмкін. Бұл жағдайларды біз а0, а1,...,аm символдарымен немесе басқа символдармен белгілейміз. Осы символдар лента ұяшықтарында жазылған. Мұндай символдардың жиынтығы машинаның сыртқы алфавиті деп, ал лентаның өзі машинаның сыртқы жадысы деп аталады. Егер ұяшық бос болса, ол жерде l шарты символы орналасқан деп есептейміз. Машинаның жұмысы кезінде лентаның ұяшықтары өздерінің жағдайын өзгертуі де, өзгертпеуі де мүмкін. Жаңа қосылатын барлық ұяшықтар бос болады. Сонымен, егер қандай да бір уақытта лентаның r ұяшығы болса және машинаның сыртқы алфавиті мынадай символдардан тұрса а0, а1, ...,аm, онда лентаның жағдайы былай жазылады: aі0, аі1, ...,аіm. аі1-солдан бастап орналасқан бірінші ұшықтың жағдайы, аі2-екіншісінің жағдайы, т.с.с. Басқару головкасы. Бұл лентаның бетімен қозғалатын және белгілі бір уақытта лентаның белгілі бір ұяшығында тұрады. Кейде керісінше басқару головкасы қозғалмайды, оған сәйкес лента қозғалады деп есептеледі. Ондай кезде головкаға лентаның ұяшығының біреуі әлде келесісі кіреді деп есептеледі. Егер лентаның ұяшығы головкада болса, машина бұл ұяшықты оқып немесе қабылдап жатыр деп есептеледі. Машинаның ішкі жадысы - әрбір қараған уақытта белгілі бір жағдайда болатын құрылғы. Ішкі жадының жағдайының саны машинамен есептеліп отырады. Ішкі жадының жағдайын мынадай символдармен көрсетеміз S0, S1,…, Sn, олар машинаның сыртқы алфавитіне кірмейді. Ішкі жадының жағдайының символдарының жиынтығы машинаның ішкі алфавиті деп аталады. Ішкі жадының жағдайын көбінесе машинаның ішкі жағдайлары деп атайды. Бұл жағдайлардың біреуі бастапқы деп аталады, бұл жағдайдан машина өз жұмысын бастайды, ол S0 жағдайы болсын. Тағы да бір арнайы жағдай - аяқтаушы соңғы жағдай. Соңғы жағдайды көрсететін символ стоп-символ деп аталады. Стоп-символ W өрнектеледі. Егер қандай да бір уақытта машинаның ішкі жадысы W келсе, ол жұмысын тоқтатқан болып есептеледі. Машинаның Sі қандай да бір ішкі жағдайында ешқандай өзгеріс болмауы мүмкін, олай болса, машина шексіз жасайды деп есептеледі. Машина ерекше механизммен жабдықталған деп есептеледі. Ол қабылданатын ұяшық пен ішкі жады жағдайына қарай ішкі жады жағдайын, ұяшық орнын өзгерте алады деп есептеледі. Машинаның (Тьюринг) ағымдағы жағдайы немесе оның конфигурациясы деп ағымдағы ұяшық аj және ішкі жады S1 жағдайларының жиынтығын айтамыз. Тьюринг машинасының командасы, яғни машина жұмысы бір жағдайдан белгілі бір уақытта механикалық құрылғының бір такті жұмысынан соң жаңа бір жағдайға өтуіне негізделген, содан соң тағы бір такті жұмысынан жаңа бір жағдайға өтуі т.с.с. Егер машина Sі ішкі жағдайында аі символды лентаның ұяшығын қабылдап, ішкі жады жағдайын келесіге Sb аударып сонымен бірге қабылданған ұяшықтың мазмұнын аr символына аударып, ал басқару головкасы (H) орнында тұрып, бір ұяшыққа оңға қарай (R), солға қарай (L) қозғалса, онда машина мынадай команда орындап жатыр деп айтады: Sі аі аs Sb H Sі аі аs Sb R Sі аі аs Sb L Машина орындай алатын барлық командалардың жиынтығы бағдарлама деп аталады. Машина жұмысы шарт бойынша толықтай оның ішкі жадысының S және қабылданатын ұяшықтың aj жағдайымен анықталатын болғандықтан, барлық Sі aj (і=1, …, n; j=0, 1, …, m) үшін машина бағдарламасы тек қана бір aіaj сөзінен басталатын командадан тұруы қажет. Сонымен {a0, a1, …, an} символды және { S0, S1, …, Sm } жағдайдағы машина бағдарламасы максимум (n+1)(m+1) командаларынан тұрады. Бағдарламада мынадай жолдардың өңделуі мүмкін емес, бірақ формалды түрде олардың болуы қате болып саналмайды. Тьюринг машинасының қарапайым түрінде кейбір алгоритмдерді құру қиындық туғызады.Мысалы, аралық мәліметтерді бір жерде сақтау немесе бірнеше элемент топтарының символын салыстыру және т.б. Кей жағдайда қосымша лентаның болуы немесе сөздерді бірнеше лентаға орналастыру дұрыс шешім қабылдауға көмектеседі. Көпленталы машина әрбір лентаға арналған алфавитке ие. Машинадағы ленталар бір-бірінен тәуелсіз қозғалады. Алайда машина лентасының жағдайы бірдей, ол жағдай басқару механизмі болып табылады. Бір ленталы машинаны қарастырғанда лента қозғалмайды, ал головка берілген бағытта қозғалады деп есептелді. Бірақ көп ленталы машинаны қарастырғанда бұл жағдай ыңғайлы емес. Себебі ленталар бір-бірінен тәуелсіз, ал бір басқару механизмінде түрлі бағыттағы қозғалысты көрсету қиын. Сонымен басқару механизмі қозғалмайды, ал ленталар оңға, солға бір-бірінен тәуелсіз қозғалады деп есептеледі. Көп ленталы машинаның бағдарламасы - шешімге қарай келесі жазба тәртібі қолданылады: Sі{a,b,c}→{a',b',c'}{R,L,H}Sj Тьюринг белгілі бір U есептеу машинасының құрылысының мүмкіндігін көрсетті, U машинасы универсалды деп аталу себебі онда түрлі есептеулерді жасауға болады. Тьюринг машинасының ерекшелігі сәйкес келетін кодтау жолымен кез- келген есептеуді берілген Тьюринг машинасында орындай алуында. Кодтау жеңіл болуы керек. Тьюринг машинасының бағдарламасының кодталуы Тьюрингтің универсалды машинасы ТУМ лентасында берілген Тьюринг машинасының ТМ код номері жазылады. ТУМ осы код номерін оқып, оның лентасында бағдарламасы жазылған машинаның барлық жұмысын атқаруы қажет. Осыған сәйкес мұндай машиналарға белгілі бір әдіспен жазылған кіріспе сөз қажет. Мүмкін белгілердің саны көп болғандықтан, барлық символдар басқа белгілердің ретімен кодталады. Егер А машинасы m символға ие Aі және n ішкі жағдайға Sj ие болса, кодты былай көрсету керек: Aі = 1…1 (A1=1, A2=11, A3=111 және т.б.) Sj = 2…2 (S1=2, S2=22, S3=222 және т.б.) R = 3 L = 33 H = 333 Мұндай жағдайда машина жұмысының бағдарламасын белгілі бір санмен жазуға болады. Жазбаның екі нұсқасы бар: 1. Команданың бөлу белгісі болмайды. Мұндай жағдайда командаларды мынадай форматта жазу қажет Aold Sold Anew R Snew сонда бірінен соң бірі орналасқан екі командалар элементар анализатормен бөлінеді. 2. Команда бөлгіші бар. Мысалы Х саны оны 4 саны кодтаймыз. жүктеу/скачать 0.57 Mb. Достарыңызбен бөлісу: