Лекция тезистері
Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші
жүктеу/скачать 382.54 Kb.
|
- Бұл бет үшін навигация:
- 3-тақырып: «Алгоритмдік шығарылмайтын есептер. Есептелетін функциялар»
| Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші
Бұл машинаның Тьюрингтен айырмашылығы – ол өзінің теориясында «машина» емес «алгоритмдік жүйе» деген терминді қолданған. Оның абстрактылы машинасы бірнеше бірдей секцияларға бөлінген, оқу-жазу инесі бар шексіз лентадан тұрады. Әр секция бос немесе толтырылған болуы мүмкін. Лентаға түк жазылмаса секция бос, лентаға жазылып белгі түссе секция толық деп есептеледі. Лента жағдайы процесс уақытында өзгермелі болды. Осы лента жағдайы мен оқу-жазу инесінің орны туралы ақпарат Пост машинасының жағдайын айқындайды. Инені « », метка-белгі М болсын. Секция бос болса, ешбір белгі түспейді. Бір қадам жасағанда ине оңға немесе солға 1 қадам жылжып белгіні салады немесе өшіреді. Программадағы командаларға сәйкес машина 1 жағдайдан келесі жағдайға көшіп отырады. Әрбір команданың структурасы ХКУ болсын, Х – орындалатын команда нөмірі, К – орындалатын әрекет туралы нұсқау, У – келесі команда нөмірі.
Бұл әрекеттерге қойылатын қосымша шарттар: ХМУ командасы бос секцияда орындалмайды ХсУ командасы толық секцияда орындалады У командасының нөмірі программадағы бар команда нөмірімен сәйкес болуы керек. Егер келтірілген шарттар сақталмаса, онда машина нәтижесіз жұмысын аяқтайды. Х стоп командасы нәтижелі орындалады. Себебі, ол өзінің алдындағы әрекеттер орындалып барып солардың нәтижесінде орындалады. Кейде машина тоқтамауы мүмкін, егер командалардың ешқайсысында тоқтау командасына көшу нөмірі болмаса. Пост машинасы оң бүтін сандарды жазуды қарастырады, себебі кез келген сөз цифр түрінде кодталады. Лентада К бүтін саны К+1 келесі белгіленген секцияларда, унарлы санау жүйесі қолданылып жазылады. 0,2,3 сандарыныің жазылуы:
Өзін тексеру сұрақтары 1. Алгоритмдік машиналардың шығуына не себеп болды? 2. Пост және Тьринг машиналарының айырмашылықтары? Ұсынылатын әдебиеттер Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г. Острейковский В.А. Информатика, Москва, 2000 г. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990. 3-тақырып: «Алгоритмдік шығарылмайтын есептер. Есептелетін функциялар» жүктеу/скачать 382.54 Kb. Достарыңызбен бөлісу:
|