Тьюринг машинасының жұмыс істеу принципі, сипаттамасы

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

- ұяшықтарға бөлінген шексіз лента;

- лента ұяшықтарында болатын символдарды оқи алатын басқарушы головка;

- Тьюринг машинасының жағдайын көрсететін ішкі алфавит символы бар жадының ұяшығы.

- лента бойымен головканың қозғалысын қамтамасыз ететін басқарудың механикалық құрылғысы

- тек оқуға болатын Тьюринг машинасының бұйрықтарынан тұратын функционалды схема - жады аймағы.

Әдетте, Тьюринг машинасы схемалық түрде мынадай түрде көрсетіледі: Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, ол бірнеше ұяшыққа бөлінген. Жұмыс барысында машина бар ұяшықтарға жаңа ұяшықтарды қоса алады, сондықтан лента екі жағынан да шексіз деп айтуға болады. Лентаның әрбір ұяшығы көп жағдайдың бірінде болуы мүмкін. Бұл жағдайларды біз а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 саны кодтаймыз.

Дәріс

Тақырып.Пост машинасы

Абстрактылы Пост машинасы шексіз лента түрінде болады, ол жеке ұяшықтарға бөлінген, оған белгіні енгізеді немесе бастиек көмегімен белгіні жазады немесе оқиды.

Абстрактылы Пост машинасы

Лента немесе бастиек командаға байланысты бір қадам солға немесе оңға жылжиды. Лента бастиек қарама-қарсы ұяшыққа орналасатындай тоқтайды. Абстрактылы автоматтың құрамына төмендегі әрекеттердің біреуі кіреді:

Әрбір команданың өзінің інөмірі болады. Стрелка жылжу бағытын көрсетеді. Команда соңындағы екінші j саны жөнелту (жіберу) деп аталады.

Басқаруды беру командасында екі жөнелту болады. Сондықтан абстрактылы автомат екі қасиетке ие:

1) бірінші орында нөмір 1 команда, екінші орында 2 нөмірі және т.с.с

2) кез-келген командадан жөнелту бағдарлама командасы алынады.

Лентаны солға немесе оңға жылжытқаннан кейін бастиек ұяшықтың қалып күйін оқиды (бос немесе белгі жазылған). Бос секциялар немесе белгіленген секциялар туралы ақпарат лентаның қалып күйін немесе автоматтың қалып күйін құрады. Автоматтың бағдарламасы деп командалардың бос емес шектелген тізімін айтамыз. Абстрактылы автоматтың жұмыс істеуі үшін бағдарлама және бастапқы

күйін беру керек, яғни бастиектің орны мен лента ұяшықтарының күйін беру керек. Әрбір команда бір қадамда орындалады, одан кейін жөнелтуде көрсетілген нөмірлі команданың орындалуы басталады. Егер команда екі жөнелтуден тұрса, егер бүркеншік бос ұяшықта тұрса, онда жоғарғы жөнелту орындалады. Егер бүркеншік белгісі бар ұяшықта тұрса, онда төменгі жөнелту орындалады. Басқаруды беру командасының орындалуы автоматтың күйін өзгертпейді (белгілердің бірде біреуі жойылмайды, қойылмайды және лента қозғалыссыз қалады). Автоматты іске қосқанда төмендегі жағдайлардың біреуі болуы мүмкін:

1) автомат орындалмайтын командаға жетті (белгіні бос емес ұяшыққа жазу, бос ұяшықтағы белгіні өшіру); бұл жағдайда орындалу аяқталады, автомат тоқтайды, нәтижесіз тоқтату болады.

2) автомат тоқта командасына жетті, бағдарлама орындалды деп есептеледі, нәтижелі тоқтату болады.

3) автомат нәтижелі тоқтатуға да, нәтижесіз тоқтатуға да жетпейді, шексіз жұмыс істеледі.

Пост машинасының типтік бағдарламасын орындау кезіндегі автомат жұмысын қарастырамыз. Бастиектің бастапқы күйі берілген және бос лентаға екі белгі жазу керек.

Пост машинасында қолданылатын сандар позициялық емес.

Дәріс