Пост машинасы

Презентация қосу

Автомат – ақпараттық
жүйенің негізгі элементі.
Абстрактілі автоматтар
БӨЖ
Жасаған: Бақытхан Шуақ
Тобы: ИПҚ-311
1. Абстракциялық
автоматтар.
2. ЭЕМ-
программалық
Жоспа басқарылатын
р: цифрлы автомат.
3. Тьюринг
машинасы.
4. Пост машинасы.
Автомат деп материалды
обьектiлердiң, энергияның немесе
акпараттың турленуi болатын
белгiлi бiр амалдар тiзбегiн
адамның қатысуынсыз орындайтын
құрылғыны атайды. Адамның
қатысуынсыз» деген кезде
амалдың орыналуы кезінде анық
адамның басқаруы болмайды
деген ұғым айтылып тұр. Дегенмен
шын мәнісінде басқару жүргізіледі,
бірақ адамның алдын-ала құрып,
құрылғыға енгізген программасы
арқылы. Бұдан әрі тек дискретті
формада көрсетілген ақпаратты
автоматты түрде өңдеуге арналған
құрылғыларды ғана қарастырамыз.
Құрылғы сыртқы ортамен ақпарат
алмасатындықтан оның ақпарат енгізілетін
енгізу каналы болу керек, сол сияқты
түрлендіру нәтижесі берілетін шығару
каналы болу қажет. Бұдан басқа, құрылғыда
оның ағымдағы қалпы бекітілетін жадысы
болу керек; жалпы жағдайда өңдеу
нәтижесі енгізілген әрекеттер мен
құрылғының ішкі қалпы арқылы
анықталады. Айталық, енгізілетін ақпаратты
көрсету үшін қанадай-да бір шекті Х
алфавиті (енгізу алфавиті) қолданылсын, ал
шығарылатын ақпаратты көрсету үшін Ү
шекті алфавиті (шығару алфавиті)
қолданылсын.

Алфавиттің шектілігіне талап ақпаратты
өңдеу уақытының шектілігіне байланысты.
Ішкі қалпы ішкі алфавит деп есептеуге
болатын дискретті жиынтықты құрайды – Q
деп белгілейміз.
Кіру сигналдарының келіп түсуі және құрылғы
қалыптарының қайта қосулары үзіліссіз емес, ал белгілі
уақыт мезеттерінде, яғни, дискретті түрде жүргізіледі деп
есептейік. Егер мезеттердің тізбегі еркін болса, онда
құрылғы элементтерінің жұмысын асинхронды
ұйымдастырған деп айтады, мысалы, телефон нөмірін
немесе құлыптың кодын теру. Дегенмен, күрделі
құрылғыларда синхронды ұйымдастыру қолданылады, яғни
мұнда сигналдардың келіп түсү мезеттері мен шығарылуы,
сол сияқты ішкі қалыптарды қайта қосу бірінен кейін бірі
такт деп аталатын бекітілген уақыт deltat = Const
аралығында жүргізіледі. Бұл мезеттер арнайы құрылғы
арқылы беріледі – тактілік генератор (немесе
синхроимпульстық генератор). Уақыт бірлігіне тактілік
импульстар саны тактілік жиілік деп аталады – ол
құрылғының әрекетжылдамдығын анықтайтын маңызды
факторлардың бірі болып табылады. Такт шекараларын
бейнелейтін t0, t1, t2,… уақыт мезеттерін (t0 жұмыстың
басталу мезетіне сәйкес келеді) енгізуге болады.
• Ішкі қалыптарының жиыны,
енгізу және шығару
сигналдары сол сияқты енгізу
сигналдры келіп түсетін, ішкі
қалыптары өзгеретін және
шығу сигналдары берілетін
уақыт мезеттерінің жиынтығы
дискретті болатын құрылғылар
дискретті құрылғылар деп
аталады.

• Дискретті құрылғылардың
мысалы телефонның теру
дискісі, кодты құлып,
калькулятор, электрондық
табло және компьютер болып
• Кірісіне берілген информацияны өңдейтін
және түрлендіретін цифрлық құрылғыны
цифрлық автомат деп атайды.
• Қарапайым цифрлық автоматтың графикалық
шартты бейнесі суретте көрсетілген.
Автоматтың кірістеріне Х1, Х2, …, ХN екілік
ЭЕМ – айнымалылардың комбинациясы беріледі де
программал шығыстарынан У1, У2, …. УM екілік
айнымалылардың комбинациясын алады.
ық Цифрлық автоматтың кірістері мен
басқарылат шығыстарына екілік 0 мен 1 логикалық
ын цифрлы сигналдары әсер етеді. Екілік сигналдармен
белгілі амалдар орындайтын цифрлық
автомат автоматты құрастырудың мақсаты – берілген
түрлендіруді орындау үшін тиісті элементтер
мен оларды бір – бірімен жалғастырудың
тәсілдерін таңдап алу болып табылады. Бұл
мәселелерді математикалық логика немесе
логика алгебрасы шешеді. Егер де
автоматтың шығысындағы сөз У тек оның
кірісіндегі сөзге Х сәйкес анықталатын болса,
онда мұндағы құрылғы жадысыз автомат
Комбинациялық схемалардан басқа
жадылы автоматтар да болады,
олардың есте сақтау элементтері
автоматтың ішкі күйін ұзақ уақыт бойы
сақтап тұра алады. Сондықтан бұлар
да шығыстағы сөз У кірістегі
сигналдардың Х комбинациясымен
ғана емес, сонымен бірге автоматтың
сигналдар келіп түскенге дейінгі
ондағы сақталған ішкі күйіне С – ға да
байланысты болады.Мұндай автоматты
Мили автоматы деп атайды.
ЭЕМ – ның құрылымдық
схемасы
Пост
машинасы.
Пост машинасы - шексіз
таспадан және жылжыма
бөліктен тұратын абстракты
машина. Таспа белгіленген
немесе бос ұяшықтарға бөлінеді.
Абстракциялық Пост пен Тьюринг
машиналары программа қасиеттері
туралы әр түрлі пайымдауларды
дәлелдеу үшін керек. Оларды 1936
жалы американ математигі Эмил
Пост пен ағылшын математигі Аллан
Тьюринг ұсынған. Бұл машиналар
бастапқы мәліметтерді «енгізуге»,
және программа орындалғаннан
кейін нәтижені «оқуға» мүмкіндік
беретін, толық детерминирленген
болып табылатын әмбебап
орындаушыларды білдіреді. Пост
машинасы Тьюринг машинасынан
қарағанда қарапайымдылау. Ол
Эмиль Леон арқылы ЭЕМ үшін программа
Пост құрудың бірінші дағдыларын
үйретуге болады.
Пост абстракциялық машинасы
бірдей ұяшықтарға бөлінген үздіксіз
таспа мен бүркеншіктен тұрады.
Таспаның әрбіреуі бос немесе «V»
таңбасымен толтырылуы мүмкін.
Бүркеншік бір ұяшыққа сол жаққа
немесе бір ұяшыққа оң жаққа таспа
бойымен жылжи алады, егер бұл
таңба алдын ала болмаса, онда
таспа ұяшығына таңбаны енгізе
алады, егер болса, оны өшіре алады
немесе ұяшықта таңбаның бар
болуын тексере алады. Таспаның
ұяшықтары таңбамен толтырылған
туралы ақпарат машина
жұмысының процесі кезінде өзгере
алатын таспаның күйін сипаттайды.
Әрбір уақыт аралығында бүркеншік («–»)
таспаның бір ұяшығының үстінде орналасады.
Таспа күйімен қоса бүркеншіктін орналасу
орны туралы ақпарат Пост машинасының
жағдайын сипаттайды, сур. 22.
–

V V V V V V V V

Сурет 22. Постың абстракциялық машинасы
Пост машина командасының құрлымы келесідегідей: n K m, мұнда n – команданың
реттік нөмірі, K – бүркеншікпен орындалатын әрекет, m – орындауға жататын келесі
команданың нөмірі. Пост машинасының алты командасы бар.
Команда Командаға дейін Командадан кейін
лентаның күйі лентаның күйі
– –
1. Бүркеншікті оң жақтағы
V V V V V V
бір ұяшыққа жылжыту n
m
2. Бүркеншікті сол жақтағы – –

бір ұяшыққа жылжыту n V V VVV V V V V V

m
3.Бүркеншік орналасқан – –

ұяшыққа таңбаны енгізу, V V V V V
nMm
4. Бүркеншік орналасқан – –
ұяшықтан таңбаны өшіру, V V V V V V V
nСm
5.Бүркеншік орналасқан – –

ұяшықта таңбаның бар V V V V V V V
болуын тексеру; егер таңба
болмаса, басқару m1
командасына беріледі,
керсінше m2 -ге
m1
n
m2
6. Машинаны тоқтату n – –
V V V V V V V V
Тоқта n
Бүркеншік таңба бар жерге таңбаны енгізу және керісінше, таңба
жоқ жерде оны өшіру керек жағдайларында авариялық (жарамсыз)
болады.
Пост машинасы үшін программа деп мына түрдегі бос емес
командалар тізімін айтамыз: 1) n-ші орнында n нөмірі бар командасы; 2)
әрбір команданың m нөмірі тізімдегі бір команданың нөмірімен сәйкес
келеді.
Пост машинасы арқылы оқылатын алгоритмдер қасиетінің
көзқарасынан программаны орындау кезінде машинаны тоқтату
себептерінің маңызы зор:
1) «тоқта» командасы арқылы тоқтату; мұндай тоқтату нәтижелі деп
аталады және алгоритмнің (программаның) дұрыстығын көрсетеді;
2) жарамайтын команданы орындау кезінде тоқтату; бұл жағдайда
тоқтату нәтижесіз деп аталады;
3) машина ешқашанда тоқтамайды; бұл және алдындағы жағдайда біз
жаңылыс алгоримтменен (программаменен) жұмыс істеп жатырмыз.
Бастапқы деп таспадағы сол жақ таңбаның солға қарай орналасқан
бос торға қарсы бүркеншіктін күйін айтамыз.
Пост машинасының жұмыс істеуін қарастырайық. Бүркеншіктін
алғашқы күйі берілсін және бос таспаға екі таңба жазу керек дейік: біреуін
бүркеншіктін астындағы секцияға, ал екіншісін одан оң жаққа қарай. Оны
келесі программамен жасауға болады (команданың оң жағында оның
орындалу нәтижесі көрсетілген), сур. 24.

Сурет 24. Пост машинасының программа бөлігінің мысалы
Пост машинасын ЭЕМ – ның жеңілдетілген моделі
ретінде қарастыруға болады. Шыңында да ЭЕМ-сы сияқты
Пост машинасында мыналар бар:
толтырылған немесе толтырылмаған ақпараттың
бөлінбейтін тасушылары (торлар – биттер);
элементарлы әрекеттер-командалардың шектелген
жиыны, оның әрбіреуі бір тақта (қадамда) орындалады.
Екі машинада программа негізінде жұмыс істейді.
Бірақта Пост машинасында ақпарат сызықты орналасады
және қатар оқылады, ал ЭЕМ–да ақпаратты адрес бойынша
оқуға болады; ЭЕМ – ның командалар жиыны, Пост
машинасының командаларына қарағанда кеңірек және
айқындырақ және т.б.
Тьюринг машинасы
Тьюринг машинасы - құрылымына бос немесе
белгіленген алфавиттің символы бар ұяшықтарға
бөлінген шексіз таспамен әрекеттесетін шектеулі
анықталған автомат кіретін абстракты автомат.
Тьюринг ықтималдық
машинасы — бір
Тьюринг таспасында
ықтималд символдардың
ық кездейсоқ тізбектігі
машинас жазылган (әр адымда
ы осы таспадағы бір
символ оқылатын) көп
таспалық машина.
Тьюринг машинасы Пост
машинасына ұқсас, бірақ
басқаша жұмыс істейді.
Тьюринг машинасы (ТМ) есептеу
таспадан (ұяшықтарға бөлінген
және оң жақтан емес, сол
жақтан шектелген), оқитын
және жазатын бүркеншіктен,
таспа созылынқы механизмнен
және кейбір ақырғы жиынтыққа
жататын q0, q1, ..., qs дискретті
қалып-күйдін бірінде
орналасатын операциондық
орындаушы құрылғыдан тұрады.
Мұнда q0 бастапқы қалып - күйі
деп аталады.
Тьюринг машинасының
схемасы — ағымдағы әрекетке
тәуелді Тьюринг машинасының
барлық мүмкін болатын қадамын
Тьюринг санау (ақырғы емес қалып-қүй,
машинасының қабылданатын символ).
схемасы Комбинация, әдетте, екі кірісі бар
кесте түрінде беріледі, кестенің
тор көзінде Тьюринг машинасы
қадамының коды (машинаның
командалары) болады.
Тьюринг машинасының схемасы
мысалын қарастырайық. Ондық
санау жүйесіндегі n санына бірлікті
қосу алгоритмі.
n санның ондық жазуы берілсін (n
натурал санның ондық санау
жүйесіндегі өрнектелуі); n+1
санның ондық жазуын алу керек.
Айқын, ТМ-ның сыртқы әліпбиі
0,1,2,3,4,5,6,7,8,9 он цифрдан және
бос орын_ символынан тұру керек.
Бұл цифрларды ұяшыққа бір бірден
жазады (қатар, қалдырусыз).
Машинаның q1 және q2екі ішкі
қалып – күйі бар болса жеткілікті
екен.
qi
Бастапқы мезетте бүркеншік
ai q1 q2
санның цифрларының бірінің
0 0 П q1 1 C q2
үстінде, ал машина q1 қалып-
1 1 П q1 2 C q2
күйінде орналасқан деп болжайық.
2 2 П q1 3 C q2
Онда есеп екі кезеңмен шығарлуы
3 3 П q1 4 C q2
мүмкін: бүркеншіктін жылжуы
4 4 П q1 5 C q2
санның бірлік цифрына (q1 ішкі
5 5 П q1 6 C q2
қалып-күйінде) және осы цифрды
6 6 П q1 7 C q2
үлкен бірлікке ауыстыру (1 келесі
7 7 П q1 8 C q2
разрядқа көшіруді есепке ала
отырып, егер 9 болса, q2 ішкі 8 8 П q1 9 C q2
9 9 П q1 0 C q2
қалып-күйінде). ТМ сәйкес
_ _ Л q1 1 C q2
схемасы келесі түрде болады:
Қазіргі күнде дейін әртүрлі алгоритмдер ішкі және сыртқы
әліпбимен, командалар жиынымен айрықшаланатын әртүрлі Тьюринг
машиналарында жүзеге асырылады деп есептелген. Бірақта, кез келген
Тьюринг машинасының кез келген алгоритмін орындай алатын
әмбебап Тьюринг машинасын құруға болады. Бұл әмбебап машинаның
сыртқы әліпбидің символы түрінде кез келген Тьюринг машинасының
программасын және сырт пішінің кодтау жолымен іске асады.
Кодтаудың өзі келесі түрмен орындалу керек:
1) әртүрлі символдар әртүрлі кодтық топтарымен ауыстырылуы
керек, бірақ бірдей символ қай жерде кездессе де, сол кодтық топпен
ауыстырылуы қажет;
2) кодтық жазулардың жолдары жеке кодтық топтарға бөлінуі
керек;
3) Л, П, С командаларына сәйкес келетін кодтық топтарды тануға,
сыртқы әліпбидің символдары мен ішкі қалып-күйлеріне сәйкес
келетін кодтық топтарды айыра білуге мүмкіншілік болу керек.
Автомат – ақпараттық
жүйенің негізгі элементі. Автомат
нәтижесінде материалды
қорытынд объектілердің, энергияның немесе
ы ақпараттың түрленуі болатын белгілі
бір амалдар тізбегін адамның
қатысуынсыз орындайтын құрылғыны
атайды.
Назарларыңызға
рахмет!

Ұқсас жұмыстар

Тьюринг машинасы және Пост машинасы

Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері және оның негіздемесі. Марковтың нормальды алгоритмі және Тьюринг машинасының композициясы

Тьюринг машинасы. Тьюринг тезисі жә не оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері жә не оның негіздемесі. Марковтың нормальды алгоритмі жә не Тьюринг машинасының композициясы

Тьюринг тезисі және оның негіздемесі

Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі

Марковтың нормальды алгоритмі

Программалау тілдері туралы ақпарат

Постимпрессион изм өнері

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ ҚАРУЛЫ КҮШТЕРІНҢ ӘСКЕРИ ЖАРҒЫЛАРЫ

Қазпочта АҚ туралы

Пәндер