Өзін-өзі тексеру сұрақтары немесе тесттер:
1. Абстракциялық автоматтар.
2. ЭЕМ-программалық басқарылатын цифрлы автомат.
3. Пост машинасы.
Әдебиет: [1],[2],[4]
9 апта
Дәріс №1.
Тақырыбы: Тьюринг машинасы
Сағат 1
Мақсаты: Тақырып бойынша студенттерге Тьюринг машинасы туралы толық мәлімет беру.
Тьюринг машинасы үш бөліктен тұрады: лентадан, оқитын-жазатын головкадан және логикалық құрылғыдан ( 7.1 суретті қара).
Лента сырқы жады ретінде болады; ол шектелмеген (шексіз) болып есептелінеді – бұл Тьюринг машинасының моледьді құрылғы екенін көрсетеді, себебі ешқандай шынайы құрылғының шексіз көлемді жадысы болмайды.
7.1. сурет. Тьюринг машинасының схемасы.
Пост машинасындағыдай, лента жеке бөліктерге бөлінген, бірақ, Тьюринг машинасында головка қозғалмайды, ал лента оған қатысты оңға және солға қозғалады. Басқа айырмашылығы ол екілік алфавитте емес, кандай-да бір кез-келген A = { , a1…a n} шекті алфавитте жұмыс істейді – бұл алфавит сыртқы алфавит деп аталады. Онда бос белгі деп аталатын арнайы символы ерекшеленіп тұр, оны қандай-да бір ұяшыққа жіберу ондағы белгіні өшіріп, ұяшықты бос қалдырады. Лентаның әр ұяшығына бір ғана символ жазылады. Лентада сақталған ақпарат сыртқы алфавиттің бос белгісінен басқа белгілерінің шектелген тізбегімен бейнеленеді.
Головка әрқашан лента ұяшықтарының бірінің үстінде орналасады. Жұмыс тактілермен (қадамдармен) жүреді. Головкаларымен орындалатын командалар жүйесі қарапайым: әр такті сайын ол шолынулы ұяшықтағы ai белгісін aj белгісіне ауыстырады. Мұнда келесі сәйкестіктер болуы мүмкін:
j = i – бұл шолынулы ұяшықта ештеңе өзгермегенін білдіреді;
i 0, j = 0 – ұяшықта сақтаулы белгі бос белгіге ауыстырылғанын, яғни өшірілгенін білдіреді;
i =0, j 0 - ұяшықта сақтаулы бос белгі бос емес белгіге (алфавиттегі j белгісіне) ауыстырылғанын білдіреді, яғни белгі қою орындалады;
i j 0 - бір белгіні екіншісімен ауыстыруды білдіреді.
Осылайша, Тьюринг машинасында ақпараттарды өңдеудің ең қарапайым командалары жүзеге асырылады. Бұл өңдеудің командалар жүйесі тура сол сияқты қарапайым лентаның орын ауыстыруының командалар жүйесімен толықтырылады: бір ұяшық солға, бір ұяшық оңға және орнында қалу, яғни шолынулы ұяшықтың адресі команданы орындау нәтижесінде немесе 1-ге ауысады, немесе өзгеріссіз қалады. Бірақ, шыныда лента жылжығанмен, әдетте головканың секцияға қатысты жылжуы қарастырылады – сондықтан лентаның оңға жылжуы командасы R («Right») арқылы, ал солға жылжу командасы L («Left») арқылы, жылжудың болмауы - S («Stop») арқылы бейнеленеді. Ары қарай головканың жылжуы туралы айтамыз да, R, L және S командаларын оның қозғалысы деп білеміз. Бұл командалардың қарапайымдылығы қандай-да бір ұяшықтың мазмұнына барғымыз келсе, ол жеке бір ұяшыққа жылжу командасының тізбегі арқылы ізделінетінін білдіреді. Әрине бұл өңдеу процесін біршама ұзартады, оның есесіне ұяшықтарды нөмірлеу және адрес бойынша өту командасынан арылуымызға көмектеседі, яғни, шынайы қарапайым қадамдардың санын азайтады, бұл теориялық тұрғыдан өте маңызды.
Тьюринг машинасында ақпаратты өңдеу және таңбаны жазу командасын беру, сол сияқты лентаны жылжыту логикалық құрылғы (ЛҚ) арқылы орындалады. ЛҚ шекті жиын құрып, Q ={q1…qm, z} арқылы бейнеленетін қалыптардың бірінде бола алады, z қалпы жұмыстың аяқталғанына сәйкес келеді, ал q1 бастапқы қалып болып табылады. Q таңбасы R, L, S таңбаларымен бірге машинаның ішкі алфавтін құрады. ЛҚ екі кіру каналына (ai, qi) және үш шығу каналына (ai+1, qi+1, Di+1) (суретке қара) ие:
Схеманы келесі түрде түсіну керек: i тактісінде ЛҚ-ның бір кірісіне сол мезетте шолынулы (ai,) ұяшығынан белгі беріледі, басқа кірісіне сол мезеттегі ЛҚ-ның қалпын (qi)-ді бейнелейтін белгі беріледі. Алынған (ai, qi) белгілерінің үйлесуіне және бар өңдеу ережелеріне байланысты ЛҚ жаңа (ai+1) белгісін дайындап, бірінші шығыс каналынан шолынулы ұяшыққа бағыттайды, головканың орын ауыстыру командасын (R, L және S-ден Di+1-ді) береді, сол сияқты келесі басқару белгісін (qi+1 ) шақыру командасын береді. Осылайша, Тьюринг машинасы жұмысының қарапайым қадамы (такт) келесіден тұрады: головка шолынулы ұяшықтан символды оқиды, және өзінің қалпына және оқылған символға байланысты қандай символ жазу (немесе өшіру) керектігі және қандай қозғалыс орындау керектігі жазылған команданы орындайды. Мұнда головка да жаңа қалыпқа өтеді. Мұндай машинаның функционалдану схемасы келесі 7.2 суретте көрсетілген.
Сурет 7.2. Тьюринг машинасының функционалдану схемасы
Осы схемада жадыны сыртқы және ішкі жадыға бөлу бейнеленген. Сыртқы жады шексіз лента түрінде көрсетілген – ол сыртқы алфавитттің символдарымен кодталған ақпаратты сақтауға арналған. Ішкі жады ағымдағы тактідегі келесі команданы сақтауға арналған екі ұяшық түрінде көрсетілген: Q-де ЛҚ-дан келесі қалып (qi+1) беріліп, сақталады, ал D-да – жылжу командасы (Di+1). Q-дан кері байланыс линиясы бойынша qi+1 ЛҚ-ға түседі, ал D-дан команда қажет кезінде лентаны бір позиция оңға немесе солға жылжытатын орындаушы механизмге түседі.
Тьюринг машинасы жұмыс істейтін жалпы ережені келесі жазба түрінде көрсетуге болады: qiaj qi’aj ’Dk, яғни, qi қалпында головканың aj символын шолуынан кейін ұяшыққа aj’ символын жазады, головка qi’ қалпына өтеді, ал лента Dk жылжуын жасайды. Әрбір qiaj комбинациясы үшін тура бір түрлендіру ережесі бар (ереже тек қана z үшін жоқ, себебі бұл қалыпқа түскенде машина тоқтайды). Бұл логикалық блоктың мынадай функцияны жүзеге асыратынын білдіреді: әрбір qiaj қос кіру синалына бір және тек бір qi’aj’Dk үштік сигналын сәйкестендіреді – бұл машинаның логикалық функциясы деп аталып, әдетте кесте (машинаның функционалды схемасы) түрінде көрсетіледі, олардың бағандары қалыптардың символдарымен белгіленеді, ал жолдары сыртқы алфавит белгілерімен бейнеледнеді. Егер сыртқы алфавит таңбалары n, ал ЛҚ-ның қалыптарының саны m болса, онда түрлендіру ережелерінің жалпы саны n ·m болады.
Нақты Тьюринг машинасы A и Q жиындарының элементтерін көрсетумен, және сол сияқты ЛҚ-ны жүзеге асыратын логикалық функциялармен , яғни түрлендіру ережелерінің жиынтығымен беріледі. Әртүрлі A, Q жиындары мен логикалық функциялар шексіз көп болатыны түсінікті, яғни Тьюринг машинасы да сол сияқты шексіз көп.
Тьюринг машинасының функционалдануын талдамас бұрын тағы бір ұғым енгізейік.
Достарыңызбен бөлісу: |
