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

“ Программалау тілдері. ”

Тақырыбы: “ Тьюринг машинасы ”.

Тексерген: Рысжанова А. C.

Орындаған: Абдолла А. С. Т-313

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-дан команда қажет кезінде лентаны бір позиция оңға немесе солға жылжытатын орындаушы механизмге түседі.

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

Конфигурацияны келесі түрде жазуға болды: a1qiaj…ak, бұл k символдан тұратын сөзде j нөмірлі секция шолынуда, және бұл кезде басқарушы құрылғы qi қалыпта тұр дегенді білдіреді. Машина конфигурациясы сыртқы алфавиттің символдарының кез-келген санынан тұратыны және тек бір ғана ішкі алфавит символынан тұратыны түсінікті. Көбінесе конфигурацияны 1 qi 2 түрде жазады, мұндағы 1 - лентадағы головканың сол жағында тұрған сөз, 2 - лентадағы головканың оң жағындағы тұрған сөз, шолынулы таңбаны қоса есептегенде. 1 -дің сол жағында және 2 -нің оң жағында лента бос. 7. 1 суретте бейнеленген конфигурацияны келесі түрде жазуға болады: a1 a2 qa3a 4ak, ал 7. 2 суреттегі - 1q.

Жұмысты бастамас бұрын бос лентаға А алфавитінде жазылған, шекті бастапқы сөзі жазылады; головка сөзінің бірінші символының үстіне орнатылады, ЛҚ қалпына келтіріледі (яғни, бастапқы конфигурация түрде болады) . Әрбір конфигурацияда тек қана бір түрлендіру ережесі жүзеге асатындықтан, бастапқы конфигурация машинаның барлық келесі жұмысын, яғни, жұмысты тоқтатқанға дейінгі барлық конфигурациялар тізбегін бірмәнді анықтайды.

Бастапқы конфигурацияға байланысты оқиғаның өрбуінің екі нұсқасы бар:

Тактілердің шекті санынан кейін тоқтау командасы бойынша машина тоқтайды; бұл кезде лентада шығатын ақпаратқа сәйкес соңғы конфигурация қалады;

Тоқтау болмайды.

Бірінші жағдайда, осы машинаның бастапқы ақпаратқа қолданылатыны туралы айтылады, ал екінші жағдайда - жоқ. Машина нәтиже алуды қамтамасыз ететін барлық кіру конфигурацияларының жиынтығы шешілетін есептер класын құрады. Әрине, Тьюринг машинасын шешілетін классқа кірмейтін есептерге қолдану мәнсіз болады. Екінші жағынан, көптеген жағдайларда шешілетін есептер класын басқа Тьюринг машиналарын құру арқылы кеңейтуге болады.

Мысал 1.

Көпразрядты бүтін сан n-нің ондық санау жүйесіндегі жазылуы бар; n+1 мәнін есептеуді қамтамасыз ететін Тьюринг машинасын құру керек.

A={0, 1, …, 9, } сыртқы алфавитін қолданамыз, мұнда символы бос белгіге сәйкес келеді. Ішкі алфавит алдыңғы есептегідей екі қалыптан тұрады - жұмыс қалпы (q) және тоқтау (z) (Q={q, z}) . Бастапқы сөз n, сол сияқты нәтиже - n+1 - ондық санау жүйесінде жазылады, және де цифрлар көрші ұяшықтарда бір-бірден, бос орынсыз жазылады. Функционалдық схема кесте түрінде көрсетіледі (қолайлылық үшін жол q қалпына, ал бағандар - сыртқы алфавит таңбаларына сәйкес келеді) :

z1S

z2S

z3S

z4S

z5S

z6S

z7S

z8S

z9S

q0L

z1S

Айталық, бастапқы конфигурациясы 21q9 болсын.

Такт 1 q9 q0L, яғни 9 таңбасы 0-ге ауысады да, головка ондықтар бірлігіне жылжиды - аралық конфигурация 2q10.

Такт 2 q1 z2S, яғни 1 таңбасы 2-ге ауысады да соңғы конфигурациямен 2z20 тоқтау болады, яғни, 219+1 қосынды нәтижесі алынды.

Аталық, бастапқы конфигурация 99q9 болсын.

Такт 1 q9 q0L, яғни, 9q90 аралық конфигурациясы құрылады.

Такт 2 q9 q0L - q900 аралық конфигурациясы құрылады.

Такт 3 q9 q0L -q 000 құрылады.

Такт 4 q z1S - z1000 туындайды және жұмыс тоқтатылады.

Осылайша, сипатталған алгоритм кез-келген бүтін сан мен бірлікті қосуды қамтамасыз етеді. Осылайша бірлікті емес, қандай-да бір бүтін m санын қосу үшін осы алгоритмді m рет қайталау кажеттігі түсінікті. Бүтін сандарды көбейту де санды өзіне-өзін қосуға келтіруге болады. Осыдан, Тьюринг машинасы маңызды қасиетке ие - қолда бар машиналарды біріктіру арқылы жаңа машина құру мүмкіндігі - мұндай амал композиция деп аталады.

Марковтың қалыпты алгоритмдері

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

Тағы да қандай-да бір А алфавитін қарастырайық. Анықтамалар енгізейік:

Сөз - бұл алфавит таңбаларының кез-келген шекті тізбегі. Сөздегі символдар саны оның ұзындығы деп аталады. Ұзындығы нольге тең сөз бос деп аталады.

s сөзі q сөзінің ішкі сөзі деп аталады, егер q-ді q=rst түрінде көрсетуге болса, мұндағы r және t сол алфавиттегі кез-келген сөздер (соның ішінде бос сөздер де болады) .

Енді алгоритм ұғымын анықтауға болады (қатаң емес) :

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

Web-сайттардың қазіргі заманғы динамикалық мазмұнын жобалаудың құралдары

ДК қолданбалы программалық қамтамасыздандырылу

Алгоритм күрделілігі

JAVA ТІЛІНДЕГІ ОБЪЕКТІЛІ – БАҒЫТТАЛҒАНПРОГРАММАЛАУ

Объектілі бағытталған программалаудың негізгі артықшылығы модульдік программалаумен салыстырғанда модульдер арасында жіберілген ақпарат көлемінің азаюы және модуларалық байланыстар санының қысқаруы

DELPHI және Visual Basik тілдері

Программалық жабдықтар

Аналитикалық машина

Паскаль программалау тілдері

Бағдарламалау тілі