Зертханалық жұмыс №1 Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу



бет9/21
Дата11.03.2022
өлшемі0.88 Mb.
#456152
1   ...   5   6   7   8   9   10   11   12   ...   21
Зертханалық жұмыс

Зертханалық жұмыс №4
Тақырыбы: Абстрактылы автоматтар. Тьюринг машинасы
(4 апта 2 сағ)


4.1. Жұмыс мақсаты – Тьюринг машинасының құрылымы мен жұмыс істеу принциптерін оқып үйрену.
4.2. Әдістемелік нұсқау
4.2.1. Тьюринг машинасы
Е кі жағы да шексіз лентадан және автоматтан тұратын құрылғыны қарастырамыз. Лента ұяшыққа бөлінген, оған {0, 1, ..., N-1} алфавитінің символдары жазылады, мұндағы "0" символы сондай-ақ бос символды білдіреді. Автомат {q1, ..., qr} күйінің бірінде бола алады және әр уақыт аралығында {R, L, S} қозғалысының біреуін жүзеге асырады: Rбір ұяшыққа оңға орын ауыстыру, L - бір ұяшыққа солға орын ауыстыру, S – орнында қалу. Мұндай құрылғының жұмысын бағдарлама деп аталатын арнайы кесте көмегімен беруге болады.




q1

qi

qr

0










1










.










.










.










a




cDq




.










.










.










N-1










Сол жақ шеткі бағанда {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) Бос тор ешқашан пайда болмайды және машина тоқтамайды.


Достарыңызбен бөлісу:
1   ...   5   6   7   8   9   10   11   12   ...   21




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет