Бір ленталы Тьюринг машинасын кибернетикалық құрылғы ретінде қарастырады және ол келесі элементтерден тұрады
жүктеу/скачать 0,57 Mb.
|
1 2
Байланысты:Бір ленталы Тьюринг машинасын кибернетикалық құрылғы ретінде қарастырады және ол келесі элементтерден тұрады
| Дәріс
Тақырып.Пост машинасы Абстрактылы Пост машинасы шексіз лента түрінде болады, ол жеке ұяшықтарға бөлінген, оған белгіні енгізеді немесе бастиек көмегімен белгіні жазады немесе оқиды.
Абстрактылы Пост машинасы Лента немесе бастиек командаға байланысты бір қадам солға немесе оңға жылжиды. Лента бастиек қарама-қарсы ұяшыққа орналасатындай тоқтайды. Абстрактылы автоматтың құрамына төмендегі әрекеттердің біреуі кіреді: Әрбір команданың өзінің інөмірі болады. Стрелка жылжу бағытын көрсетеді. Команда соңындағы екінші j саны жөнелту (жіберу) деп аталады. Басқаруды беру командасында екі жөнелту болады. Сондықтан абстрактылы автомат екі қасиетке ие: 1) бірінші орында нөмір 1 команда, екінші орында 2 нөмірі және т.с.с 2) кез-келген командадан жөнелту бағдарлама командасы алынады. Лентаны солға немесе оңға жылжытқаннан кейін бастиек ұяшықтың қалып күйін оқиды (бос немесе белгі жазылған). Бос секциялар немесе белгіленген секциялар туралы ақпарат лентаның қалып күйін немесе автоматтың қалып күйін құрады. Автоматтың бағдарламасы деп командалардың бос емес шектелген тізімін айтамыз. Абстрактылы автоматтың жұмыс істеуі үшін бағдарлама және бастапқы күйін беру керек, яғни бастиектің орны мен лента ұяшықтарының күйін беру керек. Әрбір команда бір қадамда орындалады, одан кейін жөнелтуде көрсетілген нөмірлі команданың орындалуы басталады. Егер команда екі жөнелтуден тұрса, егер бүркеншік бос ұяшықта тұрса, онда жоғарғы жөнелту орындалады. Егер бүркеншік белгісі бар ұяшықта тұрса, онда төменгі жөнелту орындалады. Басқаруды беру командасының орындалуы автоматтың күйін өзгертпейді (белгілердің бірде біреуі жойылмайды, қойылмайды және лента қозғалыссыз қалады). Автоматты іске қосқанда төмендегі жағдайлардың біреуі болуы мүмкін: 1) автомат орындалмайтын командаға жетті (белгіні бос емес ұяшыққа жазу, бос ұяшықтағы белгіні өшіру); бұл жағдайда орындалу аяқталады, автомат тоқтайды, нәтижесіз тоқтату болады. 2) автомат тоқта командасына жетті, бағдарлама орындалды деп есептеледі, нәтижелі тоқтату болады. 3) автомат нәтижелі тоқтатуға да, нәтижесіз тоқтатуға да жетпейді, шексіз жұмыс істеледі. Пост машинасының типтік бағдарламасын орындау кезіндегі автомат жұмысын қарастырамыз. Бастиектің бастапқы күйі берілген және бос лентаға екі белгі жазу керек. Пост машинасында қолданылатын сандар позициялық емес. Дәріс жүктеу/скачать 0,57 Mb. Достарыңызбен бөлісу:
|
1 2