Пост машинасы. Пост машинасы - шексіз таспадан және жылжыма бөліктен тұратын абстракты машина. Таспа белгіленген немесе бос ұяшықтарға бөлінеді

Пост машинасы. Пост машинасы - шексіз таспадан және жылжыма бөліктен тұратын абстракты машина. Таспа белгіленген немесе бос ұяшықтарға бөлінеді.

Пост абстракциялық машинасы бірдей ұяшықтарға бөлінген үздіксіз таспа мен бүркеншіктен тұрады. Таспаның әрбіреуі бос немесе «V» таңбасымен толтырылуы мүмкін. Бүркеншік бір ұяшыққа сол жаққа немесе бір ұяшыққа оң жаққа таспа бойымен жылжи алады, егер бұл таңба алдын ала болмаса, онда таспа ұяшығына таңбаны енгізе алады, егер болса, оны өшіре алады немесе ұяшықта таңбаның бар болуын тексере алады. Таспаның ұяшықтары таңбамен толтырылған туралы ақпарат машина жұмысының процесі кезінде өзгере алатын таспаның күйін сипаттайды.

Әрбір уақыт аралығында бүркеншік («–») таспаның бір ұяшығының үстінде орналасады. Таспа күйімен қоса бүркеншіктін орналасу орны туралы ақпарат Пост машинасының жағдайын сипаттайды, сур. 22.

Сурет 22. Постың абстракциялық машинасы
Пост машина командасының құрлымы келесідегідей: n K m, мұнда n – команданың реттік нөмірі, K – бүркеншікпен орындалатын әрекет, m – орындауға жататын келесі команданың нөмірі.

Пост машинасының алты командасы бар. Оны 23-суреттен көруге болады.

Команда	Командаға дейін лентаның күйі	Командадан кейін лентаның күйі
1. Бүркеншікті оң жақтағы бір ұяшыққа жылжыту n ® m
2. Бүркеншікті сол жақтағы бір ұяшыққа жылжыту n ¬ m
3.Бүркеншік орналасқан ұяшыққа таңбаны енгізу, n M m
4. Бүркеншік орналасқан ұяшықтан таңбаны өшіру, n С m
5.Бүркеншік орналасқан ұяшықта таңбаның бар болуын тексеру; егер таңба болмаса, басқару m1 командасына беріледі, керсінше m2 -ге
6. Машинаны тоқтату n Тоқта n

Пост машинасы үшін программа деп мына түрдегі бос емес командалар тізімін айтамыз: 1) n-ші орнында n нөмірі бар командасы; 2) әрбір команданың m нөмірі тізімдегі бір команданың нөмірімен сәйкес келеді.

Пост машинасы арқылы оқылатын алгоритмдер қасиетінің көзқарасынан программаны орындау кезінде машинаны тоқтату себептерінің маңызы зор:

1) «тоқта» командасы арқылы тоқтату; мұндай тоқтату нәтижелі деп аталады және алгоритмнің (программаның) дұрыстығын көрсетеді;

2) жарамайтын команданы орындау кезінде тоқтату; бұл жағдайда тоқтату нәтижесіз деп аталады;

3) машина ешқашанда тоқтамайды; бұл және алдындағы жағдайда біз жаңылыс алгоримтменен (программаменен) жұмыс істеп жатырмыз.

Бастапқы деп таспадағы сол жақ таңбаның солға қарай орналасқан бос торға қарсы бүркеншіктін күйін айтамыз.

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

Пост машинасын ЭЕМ – ның жеңілдетілген моделі ретінде қарастыруға болады. Шыңында да ЭЕМ-сы сияқты Пост машинасында мыналар бар:

· толтырылған немесе толтырылмаған ақпараттың бөлінбейтін тасушылары (торлар – биттер);

· элементарлы әрекеттер-командалардың шектелген жиыны, оның әрбіреуі бір тақта (қадамда) орындалады.