Э. А. Абдыкеримова
a 1 , …, a n } символды және
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
|
a 1 , …, a n } символды және { S 0 , S 1 , …, S m } жағдайдағы машина бағдарламасы максимум (n+1)(m+1) командаларынан тҧрады. Бағдарламада мынадай жолдардың ӛңделуі мҥмкін емес, бірақ формалды тҥрде олардың болуы қате болып саналмайды. Тьюринг машинасының қарапайым тҥрінде кейбір алгоритмдерді қҧру қиындық туғызады . Мысалы, аралық мәліметтерді бір жерде сақтау немесе бірнеше элемент топтарының символын салыстыру және т.б. Кей жағдайда қосымша лентаның болуы немесе сӛздерді бірнеше лентаға орналастыру дҧрыс шешім қабылдауға кӛмектеседі. Кӛпленталы машина әрбір лентаға арналған алфавитке ие. Машинадағы ленталар бір-бірінен тәуелсіз қозғалады. Алайда машина лентасының жағдайы бірдей, ол жағдай басқару механизмі болып табылады. Бір ленталы машинаны қарастырғанда лента қозғалмайды, ал головка берілген бағытта қозғалады деп есептелді. Бірақ кӛп ленталы машинаны қарастырғанда бҧл жағдай ыңғайлы емес. Себебі ленталар бір-бірінен тәуелсіз, ал бір басқару механизмінде тҥрлі 37 бағыттағы қозғалысты кӛрсету қиын. Сонымен басқару механизмі қозғалмайды, ал ленталар оңға, солға бір-бірінен тәуелсіз қозғалады деп есептеледі. Кӛп ленталы машинаның бағдарламасы - шешімге қарай келесі жазба тәртібі қолданылады: S і {a,b,c}→{a',b',c'}{R,L,H}S j Тьюринг белгілі бір U есептеу машинасының қҧрылысының мҥмкіндігін кӛрсетті, U машинасы универсалды деп аталу себебі онда тҥрлі есептеулерді жасауға болады. Тьюринг машинасының ерекшелігі сәйкес келетін кодтау жолымен кез- келген есептеуді берілген Тьюринг машинасында орындай алуында. Кодтау жеңіл болуы керек. Тьюринг машинасының бағдарламасының кодталуы Тьюрингтің универсалды машинасы ТУМ лентасында берілген Тьюринг машинасының ТМ код номері жазылады. ТУМ осы код номерін оқып, оның лентасында бағдарламасы жазылған машинаның барлық жҧмысын атқаруы қажет. Осыған сәйкес мҧндай машиналарға белгілі бір әдіспен жазылған кіріспе сӛз қажет. Мҥмкін белгілердің саны кӛп болғандықтан, барлық символдар басқа белгілердің ретімен кодталады. Егер А машинасы m символға ие A і және n ішкі жағдайға Sj ие болса, кодты былай кӛрсету керек: A і = 1…1 (A 1 =1, A 2 =11, A 3 =111 және т.б.) S j = 2…2 (S 1 =2, S 2 =22, S 3 =222 және т.б.) R = 3 L = 33 H = 333 Мҧндай жағдайда машина жҧмысының бағдарламасын белгілі бір санмен жазуға болады. Жазбаның екі нҧсқасы бар: 1. Команданың бӛлу белгісі болмайды. Мҧндай жағдайда командаларды мынадай форматта жазу қажет A old S old A new R S new сонда бірінен соң бірі орналасқан екі командалар элементар анализатормен бӛлінеді. 2. Команда бӛлгіші бар. Мысалы Х саны оны 4 саны кодтаймыз. жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|