Ы., Баймұсаева А. Б. Информатиканың теориялық негіздері
Пост машинасы. Пост машинасы - шексіз таспадан және жылжыма бөліктен тұратын абстракты машина. Таспа белгіленген немесе бос ұяшықтарға бөлінеді
жүктеу/скачать 314.17 Kb.
|
Пост машинасы. Пост машинасы - шексіз таспадан және жылжыма бөліктен тұратын абстракты машина. Таспа белгіленген немесе бос ұяшықтарға бөлінеді.Абстракциялық Пост пен Тьюринг машиналары программа қасиеттері туралы әр түрлі пайымдауларды дәлелдеу үшін керек. Оларды 1936 жалы американ математигі Эмил Пост пен ағылшын математигі Аллан Тьюринг ұсынған. Бұл машиналар бастапқы мәліметтерді «енгізуге», және программа орындалғаннан кейін нәтижені «оқуға» мүмкіндік беретін, толық детерминирленген болып табылатын әмбебап орындаушыларды білдіреді. Пост машинасы Тьюринг машинасынан қарағанда қарапайымдылау. Ол арқылы ЭЕМ үшін программа құрудың бірінші дағдыларын үйретуге болады. Пост абстракциялық машинасы бірдей ұяшықтарға бөлінген үздіксіз таспа мен бүркеншіктен тұрады. Таспаның әрбіреуі бос немесе «V» таңбасымен толтырылуы мүмкін. Бүркеншік бір ұяшыққа сол жаққа немесе бір ұяшыққа оң жаққа таспа бойымен жылжи алады, егер бұл таңба алдын ала болмаса, онда таспа ұяшығына таңбаны енгізе алады, егер болса, оны өшіре алады немесе ұяшықта таңбаның бар болуын тексере алады. Таспаның ұяшықтары таңбамен толтырылған туралы ақпарат машина жұмысының процесі кезінде өзгере алатын таспаның күйін сипаттайды. Әрбір уақыт аралығында бүркеншік («–») таспаның бір ұяшығының үстінде орналасады. Таспа күйімен қоса бүркеншіктін орналасу орны туралы ақпарат Пост машинасының жағдайын сипаттайды, сур. 22. Сурет 22. Постың абстракциялық машинасы Пост машина командасының құрлымы келесідегідей: n K m, мұнда n – команданың реттік нөмірі, K – бүркеншікпен орындалатын әрекет, m – орындауға жататын келесі команданың нөмірі. Пост машинасының алты командасы бар. Оны 23-суреттен көруге болады.
Сурет 23. Пост машинасының командалары Бүркеншік таңба бар жерге таңбаны енгізу және керісінше, таңба жоқ жерде оны өшіру керек жағдайларында авариялық (жарамсыз) болады. Пост машинасы үшін программа деп мына түрдегі бос емес командалар тізімін айтамыз: 1) n-ші орнында n нөмірі бар командасы; 2) әрбір команданың m нөмірі тізімдегі бір команданың нөмірімен сәйкес келеді. Пост машинасы арқылы оқылатын алгоритмдер қасиетінің көзқарасынан программаны орындау кезінде машинаны тоқтату себептерінің маңызы зор: 1) «тоқта» командасы арқылы тоқтату; мұндай тоқтату нәтижелі деп аталады және алгоритмнің (программаның) дұрыстығын көрсетеді; 2) жарамайтын команданы орындау кезінде тоқтату; бұл жағдайда тоқтату нәтижесіз деп аталады; 3) машина ешқашанда тоқтамайды; бұл және алдындағы жағдайда біз жаңылыс алгоримтменен (программаменен) жұмыс істеп жатырмыз. Бастапқы деп таспадағы сол жақ таңбаның солға қарай орналасқан бос торға қарсы бүркеншіктін күйін айтамыз. Пост машинасының жұмыс істеуін қарастырайық. Бүркеншіктін алғашқы күйі берілсін және бос таспаға екі таңба жазу керек дейік: біреуін бүркеншіктін астындағы секцияға, ал екіншісін одан оң жаққа қарай. Оны келесі программамен жасауға болады (команданың оң жағында оның орындалу нәтижесі көрсетілген), сур. 24. Пост машинасын ЭЕМ – ның жеңілдетілген моделі ретінде қарастыруға болады. Шыңында да ЭЕМ-сы сияқты Пост машинасында мыналар бар: · толтырылған немесе толтырылмаған ақпараттың бөлінбейтін тасушылары (торлар – биттер); · элементарлы әрекеттер-командалардың шектелген жиыны, оның әрбіреуі бір тақта (қадамда) орындалады. Екі машинада программа негізінде жұмыс істейді. Бірақта Пост машинасында ақпарат сызықты орналасады және қатар оқылады, ал ЭЕМ–да ақпаратты адрес бойынша оқуға болады; ЭЕМ – ның командалар жиыны, Пост машинасының командаларына қарағанда кеңірек және айқындырақ және т.б. Сурет 24. Пост машинасының программа бөлігінің мысалы жүктеу/скачать 314.17 Kb. Достарыңызбен бөлісу:
|