«Информатиканың теориялық негіздері»
Дәріс №12-13. Тақырыбы: Алгоритмдер теориясының негіздері
жүктеу/скачать 363.46 Kb.
|
| Дәріс №12-13. Тақырыбы: Алгоритмдер теориясының негіздері
Пост машинасы лентадан және кареткадан (оқушы және жазушы) тұрады. Лента шексіз және көлемдері бірдей секцияларға бөлінген. Лентаның әр секциясына өңделетін екілік информацияның бір символын жазуға болады. Екілік алфавиттің бір символы лентада "V" белгісімен көрсетіледі, келесісі – бос орын. Егер секцияға "V" белгісі жазылса, демек секция белгіленген, ал егер секцияда "V" белгісі жоқ болса онда ол белгіленбеген немесе бос деп саналады. Пост машинасы командасының форматы: nKm, мұндағы: n – ағымдағы команда нөмірі, K – Пост машинасы командалар жүйесінің командасы, m - сілтеме немесе келесі қадамда орындалатын команда нөмірі. Машина Тьюринг машинасы ақпаратты лентадан, кареткадан (считывающая и записывающая головка), лентаны тартатын механизмнен және операцияны орындайтын құрылғыдан тұрады. Лентаның сол жағы бекітілген, ал оң жағы шексіз. Лента мөлшерлері бірдей секцияларға бөлінген. Әр секцияға Тьюринг машинасының сыртқы алфавитінің бір символын жазуға болады. Каретка лента бойымен оңға және солға жылжый алады. Қозғалмаған жағдайда каретка лентаның бір секциясында орналасады. Каретка орналасқан секция ағымдағы секция деп аталады. Бір қадам жасағанда каретка бір секцияға оңға немесе солға жылжыйды. Сонымен бірге каретка ағымдағы секцияның мазмұнын анықтай алады және сыртқы алфавиттің бір символын жазып, немесе жазылған символды өшіре алады. Операцияны орындайтын құрылғы Тьюринг машинасының ішкі алфавиті немесе ішкі қалып-күй болып саналатын Q = {q0, q1,...qM} дискретті жағдайлардың бірінде болуы мүмкін. Тьюринг машинасының жұмыс реті кесте түрінде беріледі. Кестенің біріші жолының әр бағанасына ішкі алфавиттің әріптері жазылады, ал бірінші бағананың әр жолына сыртқы алфавиттің символдары жазылады. Тьюринг машинасының комадасының форматы: aKq мұндағы: a – ағымдағы ұяшықтың жаңа мәні (осы ұяшыққа жазылатын сыртқы алфавиттің жаңа символы), жүктеу/скачать 363.46 Kb. Достарыңызбен бөлісу:
|