Зертханалық жұмыс №1 Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу
жүктеу/скачать 0.88 Mb.
|
- Бұл бет үшін навигация:
- 4.2. Әдістемелік нұсқау 4.2.1. Тьюринг машинасы Е кі жағы да шексіз лентадан және автоматтан тұратын құрылғыны қарастырамыз. Лента ұяшыққа бөлінген, оған {0, 1, ..., N-1}
- {0, 1, ..., N-1}
- {R, L, S}
| Зертханалық жұмыс №4
Тақырыбы: Абстрактылы автоматтар. Тьюринг машинасы (4 апта 2 сағ) 4.1. Жұмыс мақсаты – Тьюринг машинасының құрылымы мен жұмыс істеу принциптерін оқып үйрену. 4.2. Әдістемелік нұсқау 4.2.1. Тьюринг машинасы Е кі жағы да шексіз лентадан және автоматтан тұратын құрылғыны қарастырамыз. Лента ұяшыққа бөлінген, оған {0, 1, ..., N-1} алфавитінің символдары жазылады, мұндағы "0" символы сондай-ақ бос символды білдіреді. Автомат {q1, ..., qr} күйінің бірінде бола алады және әр уақыт аралығында {R, L, S} қозғалысының біреуін жүзеге асырады: R – бір ұяшыққа оңға орын ауыстыру, L - бір ұяшыққа солға орын ауыстыру, S – орнында қалу. Мұндай құрылғының жұмысын бағдарлама деп аталатын арнайы кесте көмегімен беруге болады.
Сол жақ шеткі бағанда {0, 1, ..., N-1} (машинаның сыртқы алфавиті)алфавитінің символдары орналасады. {q1, ..., qr} жиыны – машинаның ішкі алфавиті. Бұл кестенің кейбір торлары бос болуы мүмкін. Бұл кестенің торларына машинаның командалары жазылады, яғни cDq үштік символдары, мұндағы c - машинаның сыртқы алфавитінің символы, q - машинаның ішкі алфавитінің символы және D – қозғалысын сипаттайтын алфавиттің символы, яғни {R, L, S} жиынынан. Қандай да бір уақыт аралығында автоматтың бастиегі лентада a символын бақылайды және автомат qi күйінде болады, онда машина a номерлі жолдың және qi номерлі бағанның қиылысындағы команданы орындау керек. Егер белгіленген торда cDq командасы болса, онда машина ағымдағы ұяшыққа c символын жазу керек, q күйіне өтіп D қозғалысын жүзеге асыру керек. Егер белгіленген тор бос болса, онда машина тоқтайды. Тьюрингмашинасының конфигурациясы деп qaтүріндегі тізбекті айтамыз, мұндағы a- лентаның құрамы, q– бастиектің ағымдағы күйі, ал оның позициясы және аралығындағы бақыланатын ұяшықты көрсетеді (суретті қара). сөзін қысқарту үшін ax жазамыз. Алғашқы конфигурация әрқашанда q0 түрінде болады деп саналады, яғни бастиек бұл конфигурацияда әруақытта лентаның сол жақ шетіне ығыстырылады. Бағдарламаны қолдану нәтижесінде 2 жағдай болуы мүмкін: 1) Белгілі бір уақытта бос команда пайда болады (немесе бос тор) және машина тоқтайды; 2) Бос тор ешқашан пайда болмайды және машина тоқтамайды. жүктеу/скачать 0.88 Mb. Достарыңызбен бөлісу:
|