Э. А. Абдыкеримова информатиканың теориялық негіздері
Дәріс №4. Автомат ақпараттық жҥйенің негізгі элементі ретінде
жүктеу/скачать 476,55 Kb.
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
- Бұл бет үшін навигация:
- ЭЕМ - бағдарламалық басқарылатын цифрлы автомат
- Тьюринг машинасы
- Тьюринг машинасының жҧмыс істеу принципі, сипаттамасы
Дәріс №4. Автомат ақпараттық жҥйенің негізгі элементі ретінде.Абстрактылы автоматтар Дәріс жоспары: ЭЕМ - бағдарламалық басқарылатын цифрлы автомат Тьюринг машинасы Пост машинасы ЭЕМ - бағдарламалық басқарылатын цифрлы автоматАбстрактылы (яғни тек адам қиялында ғана болатын) Пост және Тьюринг машиналары бағдарламалардың қасиеттері туралы әр тҥрлі тҧжырымдарды дәлелдеу ҥшін ойлап шығарылды. Бҧл бір-біріне тәуелсіз екі есептеу машиналарының моделін (практикада бір уақытта) 1937 жылы Алан Тьюринг ҧсынды. Бҧл машиналар толық детерминделген әмбебап орындаушылар болып табылады. Олар алғашқы деректерді енгізіп, бағдарлама орындалғаннан кейін нәтижені оқуға мҥмкіндік береді. Тьюринг машинасына қарағанда Пост машинасы қарапайым болғанымен кең таралмаған. Тьюринг машинасыБҧл елестегі машина - яғни ―қағаз бетіндегі‖ машина немесе машинаның математикалық моделі. Тьюринг машинасы - таза абстракция және ешқашан жасалмаған. Оның пайдасы тҥрлі есептер шешімінің алгоритмі бар немесе жоқ екендігін дәлелдеуге болады. Машина белгілі бір алгоритмді орындайтын болғандықтан, бҧл машинаға алгоритмнің қасиеттерінен талаптар қойылады. Біріншіден, машина толықтай детерминенделген (есептеулер нақты және жалпы тҥсінікті) болуы қажет және тапсырылған ережелер жҥйесі негізінде әрекет етуі керек. Екіншіден, ―бастапқы мәліметтерді‖ енгізуге мҥмкіндік беруі қажет. Ҥшіншіден, берілген машинаның жҧмыс жасау ережелерінің жҥйесі және шешілетін есептердің класы машина жҧмысы нәтижесін оқи алатындай болып келістірілуі керек. Тьюринг тезисі кез-келген алгоритмді Тьюринг машинасына салып шешуге болатынға негізделген. Тьюринг машинасының жҧмыс істеу принципі, сипаттамасыБір ленталы Тьюринг машинасын кибернетикалық қҧрылғы ретінде қарастырады және ол келесі элементтерден тҧрады: ҧяшықтарға бӛлінген шексіз лента; лента ҧяшықтарында болатын символдарды оқи алатын басқарушы головка; Тьюринг машинасының жағдайын кӛрсететін ішкі алфавит символы бар жадының ҧяшығы. лента бойымен головканың қозғалысын қамтамасыз ететін басқарудың механикалық қҧрылғысы тек оқуға болатын Тьюринг машинасының бҧйрықтарынан тҧратын функционалды схема - жады аймағы. Әдетте, Тьюринг машинасы схемалық тҥрде мынадай тҥрде кӛрсетіледі:
Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, ол бірнеше ҧяшыққа бӛлінген. Жҧмыс барысында машина бар ҧяшықтарға жаңа ҧяшықтарды қоса алады, сондықтан лента екі жағынан да шексіз деп айтуға болады. Лентаның әрбір ҧяшығы кӛп жағдайдың бірінде болуы мҥмкін. Бҧл жағдайларды біз а0, а1,...,аm символдарымен немесе басқа символдармен белгілейміз. Осы символдар лента ҧяшықтарында жазылған. Мҧндай символдардың жиынтығы машинаның сыртқы алфавиті деп, ал лентаның ӛзі машинаның сыртқы жадысы деп аталады. Егер ҧяшық бос болса, ол жерде шарты символы орналасқан деп есептейміз. Машинаның жҧмысы кезінде лентаның ҧяшықтары ӛздерінің жағдайын ӛзгертуі де, ӛзгертпеуі де мҥмкін. Жаңа қосылатын барлық ҧяшықтар бос болады. Сонымен, егер қандай да бір уақытта лентаның r ҧяшығы болса және машинаның сыртқы алфавиті мынадай символдардан тҧрса а0, а1, ...,аm, онда лентаның жағдайы былай жазылады: aі0, аі1, ...,аіm. аі1-солдан бастап орналасқан бірінші ҧяшықтың жағдайы, аі2- екіншісінің жағдайы, т.с.с. жүктеу/скачать 476,55 Kb. Достарыңызбен бөлісу:
|