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

Автомат - ақпараттық жүйенің негізгі элементі. Абстрактілі автоматтар БӨЖ

Жасаған: Бақытхан Шуақ

Тобы: ИПҚ-311

Жоспар:

Абстракциялық автоматтар.

ЭЕМ-программалық басқарылатын цифрлы автомат.

Тьюринг машинасы.

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

Автомат деп материалды обьект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.

Сурет 22. Постың абстракциялық машинасы

Пост машина командасының құрлымы келесідегідей: n K m, мұнда n - команданың реттік нөмірі, K - бүркеншікпен орындалатын әрекет, m - орындауға жататын келесі команданың нөмірі. Пост машинасының алты командасы бар.

Бүркеншік таңба бар жерге таңбаны енгізу және керісінше, таңба жоқ жерде оны өшіру керек жағдайларында авариялық (жарамсыз) болады.

Пост машинасы үшін программа деп мына түрдегі бос емес командалар тізімін айтамыз: 1) n-ші орнында n нөмірі бар командасы; 2) әрбір команданың m нөмірі тізімдегі бір команданың нөмірімен сәйкес келеді.

Пост машинасы арқылы оқылатын алгоритмдер қасиетінің көзқарасынан программаны орындау кезінде машинаны тоқтату себептерінің маңызы зор:

1) «тоқта» командасы арқылы тоқтату; мұндай тоқтату нәтижелі деп аталады және алгоритмнің (программаның) дұрыстығын көрсетеді;

2) жарамайтын команданы орындау кезінде тоқтату; бұл жағдайда тоқтату нәтижесіз деп аталады;

3) машина ешқашанда тоқтамайды; бұл және алдындағы жағдайда біз жаңылыс алгоримтменен (программаменен) жұмыс істеп жатырмыз.

Бастапқы деп таспадағы сол жақ таңбаның солға қарай орналасқан бос торға қарсы бүркеншіктін күйін айтамыз.

Пост машинасының жұмыс істеуін қарастырайық. Бүркеншіктін алғашқы күйі берілсін және бос таспаға екі таңба жазу керек дейік: біреуін бүркеншіктін астындағы секцияға, ал екіншісін одан оң жаққа қарай. Оны келесі программамен жасауға болады (команданың оң жағында оның орындалу нәтижесі көрсетілген), сур. 24.

Сурет 24. Пост машинасының программа бөлігінің мысалы

Пост машинасын ЭЕМ - ның жеңілдетілген моделі ретінде қарастыруға болады. Шыңында да ЭЕМ-сы сияқты Пост машинасында мыналар бар:

 толтырылған немесе толтырылмаған ақпараттың бөлінбейтін тасушылары (торлар - биттер) ;

 элементарлы әрекеттер-командалардың шектелген жиыны, оның әрбіреуі бір тақта (қадамда) орындалады.

Екі машинада программа негізінде жұмыс істейді. Бірақта Пост машинасында ақпарат сызықты орналасады және қатар оқылады, ал ЭЕМ-да ақпаратты адрес бойынша оқуға болады; ЭЕМ - ның командалар жиыны, Пост машинасының командаларына қарағанда кеңірек және айқындырақ және т. б.

Тьюринг машинасы - құрылымына бос немесе белгіленген алфавиттің символы бар ұяшықтарға бөлінген шексіз таспамен әрекеттесетін шектеулі анықталған автомат кіретін абстракты автомат.

Тьюринг машинасы

Тьюринг ықтималдық машинасы

Тьюринг ықтималдық машинасы - бір таспасында символдардың кездейсоқ тізбектігі жазылган (әр адымда осы таспадағы бір символ оқылатын) көп таспалық машина.

Тьюринг машинасы Пост машинасына ұқсас, бірақ басқаша жұмыс істейді.

Тьюринг машинасы (ТМ) есептеу таспадан (ұяшықтарға бөлінген және оң жақтан емес, сол жақтан шектелген), оқитын және жазатын бүркеншіктен, таспа созылынқы механизмнен және кейбір ақырғы жиынтыққа жататын q0, q1, . . . , qs дискретті қалып-күйдін бірінде орналасатын операциондық орындаушы құрылғыдан тұрады. Мұнда q0 бастапқы қалып - күйі деп аталады.

Тьюринг машинасының схемасы

Тьюринг машинасының схемасы - ағымдағы әрекетке тәуелді Тьюринг машинасының барлық мүмкін болатын қадамын санау (ақырғы емес қалып-қүй, қабылданатын символ) . Комбинация, әдетте, екі кірісі бар кесте түрінде беріледі, кестенің тор көзінде Тьюринг машинасы қадамының коды (машинаның командалары) болады.