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

Жоспар
І.Кіріспе
II.Негізгі бөлім
1. Тьюринг машина сыртқы және ішкі алфавиттері
2. Командалары
3. Пост машинасы
4. Графиктері
III.Пайдаланған әдебиттер
IV.Қортынды
Кіріспе
ТЬЮРИНГ МАШИНАЛАРЫ
Тьюринг машиналары.Сыртқы және ішкі альфавиттер, командалар, бағдарламалар. Тьюринг машинасының жұмысының сипаттамасы.
Егер алгоритм түзу құрылымын қарастырса, онда оларды түзудің үш негізгі типін: сызықтық, тармақталатын, циклдік-ерекшелеуге болады.
Орындаушы командалардың орналасу ретіне қарай бірінен кейін бірін орындайтын алгоритм сызықтық деп аталады.
Орындаушының әрекеті қандай да бір шарттардың орындалу нәтижесімен анықталатын алгоритм тармақталатын деп аталады.
Кейбір жеке командаларды немесе командалар тобын орындағанда бірнеше рет қайталанатын алгоритм циклдік деп аталады.
Көптеген алгоритмдер осы құрылымдардың бәрін өзіне біріктіреді.
Жоғарыда сипатталған алгоритм анықтамалары интуитивті деп аталады, себебі олар адам түсінігіне есепке алады. Бірақ математиканың өзінің есептерін шешу үшін алгоритм ұғымын анықтап алу қажеттігі пайда болды. Алгоритмнің математикалық анықтамасы ХХ ғасырдың отызыншы жылдарының ортасында үш типті модельдерде алынды:
Есептелгіш (рекурсивті) функциялар теориясы;
Ақырлы, ақырсыз автоматтар теориясы;
Марковтың нормалы алгоритмдері.
Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты мынада: әртүрлі математикалық есептердің алгоритмдік шешімділігі мәселесін шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма?- деген сұраққа жауап беру. Біз осы мәселенің қойылуын және есептердің алгоритмдік шешімділігі теориясының кейбір нәтижелерін қарастырамыз, бірақ алдымен Пост, Тьюринг машиналары және Марковтың нормалы алгоритмдері мысалында автоматтар теориясындағы алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті функциялар теориясы негіздерін талқылаймыз.
Өздеріне арналған программалардың қасиеттері туралы әртүрлі тұжырымдауды дәлелдеуге арналған абстракты ( яғни шын емес, тек қиялда ғана бар) Пост пен Тьюринг машиналарын американдық математик Эмил Пост пен ағылшын математигі Аллан Тьюринг бірінен-бірі тәуелсіз (және іс жүзінде бір уақытта) 1936 ж. ұсынды. Бұл машиналар бастапқы мәліметтерді “енгізіп”, программалар орындалғаннан соң нәтижені оқуға мүмкіндік беретін, толығымен анықталған әмбебап орындаушылар болып табылады. Пост машинасы аса танымал емес, бірақ Тьюринг машинасына қарағанда әлдеқайда қарапайым.
Пайдаланған әдебиеттер

1. Жақыпбекова Г.Т. Информатиканы оқыту эдістемесі.-Шымкент, 2003, 646

2. О. Камардинов «Есептеуіш техника және программалау» Алматы, 1997ж

3. А.Бочкин. Методика преподавания информатики. Минск, Вышэйшая школа, 1998-430
        
        Жоспар
І.Кіріспе
II.Негізгі бөлім
* Тьюринг машина сыртқы және ішкі алфавиттері
* Командалары
* Пост ... ... ... МАШИНАЛАРЫ
Тьюринг машиналары.Сыртқы және ішкі альфавиттер, командалар, бағдарламалар. Тьюринг машинасының жұмысының сипаттамасы. ... ... түзу ... ... онда ... ... үш ... типін: сызықтық, тармақталатын, циклдік-ерекшелеуге болады.
Орындаушы командалардың орналасу ... ... ... ... ... ... ... сызықтық деп аталады.
Орындаушының әрекеті қандай да бір шарттардың орындалу нәтижесімен анықталатын алгоритм тармақталатын деп ... жеке ... ... ... ... ... ... рет қайталанатын алгоритм циклдік деп аталады.
Көптеген алгоритмдер осы құрылымдардың бәрін өзіне біріктіреді.
Жоғарыда сипатталған ... ... ... деп ... ... олар адам түсінігіне есепке алады. Бірақ математиканың өзінің есептерін шешу үшін алгоритм ұғымын анықтап алу қажеттігі пайда болды. ... ... ... ХХ ... ... ... ... үш типті модельдерде алынды:
Есептелгіш (рекурсивті) функциялар теориясы;
Ақырлы, ақырсыз автоматтар теориясы;
Марковтың нормалы алгоритмдері.
Бірінен-бірі тәуелсіз тарихи пайда ... бұл ... ... өзара эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты мынада: әртүрлі математикалық есептердің ... ... ... шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма?- деген сұраққа жауап беру. Біз осы мәселенің қойылуын және ... ... ... теориясының кейбір нәтижелерін қарастырамыз, бірақ алдымен Пост, Тьюринг машиналары және ... ... ... ... ... ... алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті функциялар теориясы негіздерін талқылаймыз.
Өздеріне арналған программалардың ... ... ... ... ... ... ... ( яғни шын емес, тек қиялда ғана бар) Пост пен ... ... ... ... Эмил Пост пен ... ... ... Тьюринг бірінен-бірі тәуелсіз (және іс жүзінде бір уақытта) 1936 ж. ... Бұл ... ... ... ... ... ... соң нәтижені оқуға мүмкіндік беретін, толығымен анықталған әмбебап орындаушылар болып табылады. Пост машинасы аса ... ... ... ... ... ... әлдеқайда қарапайым.
Пост машинасы
i-2
i-1
i
i+1
i+2
Пост абстракты машинасы, жазатын немесе оқитын түбіртек арқылы не ен жазылып, не ен ... жеке ... ... бөлінген ақырсыз таспа болып табылады.
1.16. сур. Пост абстракты машинасы.
Таспа (немесе түбіртек) командаға байланысты бір адым ... ... оңға ауыс ... ... алады. Таспа әрқашан түбіртектің қарсы алдында секция (ұяшық) тұратындай етіп ... ... ... ... ... келесі әрекеттердің бірінен тұрады:
Команда
Таспаның күйі
командадан кейін
Түбіртектің оңға қозғалуы
Түбіртектің ... ...
М енін жазу m
С енін ... ... ... стоп ... команданың өз нөмірі бар: і. Жебеше қозғалыс бағытын көрсетеді. Команданың соңында тұрған екінші j саны ... деп ... ... беру командасында екі жөнелткіш болуы мүмкін. Сондықтан да абстракты автомат ... екі ... ... ... ... ... ... тізімде әрқашан 1-нөмірлі команда тұрады,
екінші орында ... және т.б;
2) кез ... ... ... ... ... командаларының тізімінде орналасқан.
Таспаны солға немесе оңға қозғағаннан кейін түбіртек секцияның (бос немесе ен жазылған) күй-жайын ... ... ... бос, ... ... ... ... таспа күйін немесе автомат күйін бейнелейді. Автомат программасы деп командалардың ақырлы бос емес ... ... ... ... үшін бағдарламаны және бастапқы
күй-жайды, яғни түбіртектің орнын және таспа ұяшықтарының ... беру ... ... ... бір ... орындалады, сонан соң нөмірі жөнелткіште көрсетілген команда орындала бастайды. Егер бұл ... екі ... ... және ... ... бос ұяшық болса, онда жоғарғы жөнелткіш нөмірі бар команда орындалады. Егер түбіртек астында ені бар ұяшық ... онда ... ... нөмірі бар команда орындалады. Басқаруды беру командасының орындалуы автомат күйін (ендердің ешбірі жойылмайды да ... және ... ... қалады). Автоматты іске қосқанда мына жағдайдың бірі орын алуы мүмкін:
автомат орындалмайтын команданы (енді бос емес ұяшыққа жазу, бос ұяшықта енді ... ... ... ... ... ... тоқталады, автомат тоқтайды, нәтижесіз тоқтау болады;
автомат стоп командасына дейін жетті, программа орындалды деп есептелінеді, нәтижелі тоқтау ... ... де, ... де ... ... жұмыс толассыз жүре береді (автомат ілініп қалды).
Пост машинасының ... ... ... барысындағы автомат жұмысын қарастырып көрейік. Түбіртектің бастапқы күйі берілсін және бос таспада екі ен салу ... ... күйі
M 2
M ... ... ... ... үшін ... өту командасын қалай пайдалануға болатынын көрсетейік. Таспада қатарынан бірнеше еннен тұратын жазба бар және ... ең ... оң жақ ... үстінде тұрсын. Түбіртекті солға бірінші бос орынға дейін жылжыту қажет.
Бастапқы күйі
1
2
3
стоп 3
1-жол
п. ... ... ... 3
стоп
Шартты өту командасы циклдық үрдістерді ұйымдастырудың негізгі құралдарының бірі болып табылады, мысалы бос шаршыдан жоғары орналасқан түбіртектен оң жақ ... сол жақ) ... енді табу ... ... ... ( немесе оңынан ) бос шаршы табу, егер ол еннен ... ... ... және т. ... Пост ... ... ... автоматтарда сандарға әртүрлі амалдар қолдануға болады. Ол үшін абстракты автоматта сандарды ... ... ... автоматты бейнелеу ен салынған секциялар (ұяшықтар) тізбегі арқылы жүзеге асырылады. Бұл тізбек массив деп аталады, ал ондағы ... ... ... ...
n ... ... ... n+1 массиві арқылы беру мақұлданған. Мысалы, 6,3 және 2 сандары автоматтық бейнелері арқылы суретте былай берілген:
Пост машинасында пайдаланылатын ... жазу ... ... емес ... ... ...
Кез келген санға бір қосудың программасын жасайық. Ол ұшін Пост машинасы үшін мына ... ие ... ... жазу ... ... таспаға жазылған кезкелген п саны үшін программа п+1 санын таспаның кез келген жеріне жазып, нәтижелі тоқтауы керек.
Таспада бір ғана сан ... және ... осы ... жататын ен салынған шаршының бірінен жоғары орналасқан болсын. Есепті шешу үшін түбіртекті бірінші бос ... ... ... ... орын ауыстыруға, сонан соң ен салуға болады.
Программа келесі түрде ... ... ... 4
4.
стоп 4
4.
стоп 4
Бастапқы күй-жай санатында кез келген күйі ... ... Онда ... ... ... ... бірінде орналасады (яғни сандар жиынтығынан жоғары). Бұл жағдайда программа күрделілене түседі. Түбіртекті өткен мысалда қарастырылған күйге келтіретін, "санды іздеу блогы"- екі ... ... ... ... ... қосу ... болатын санның сол жағында бірнеше шаршы қашықтықта орналасқан болсын.
Төменде бірді оңына да солына да қосатын программалардың ... ... ... ... ... 6
6.
6.
Стоп 6
Бірінші жағдайда түбіртекті санның солжақ шеткі еніне орын ауыстырудың қажеті жоқ. Абстракты ... ... ... ... ... ... де іске асыруға болады. Мысалы, екі санды қосып көрейік. Жалпы қойылымда бұл есеп былай тұжырымдалады: бір-бірінен кезкелген қашықтықта таспаға ... а мен в ... қосу ... құрастыру керек. Автоматтың бастапқы күйі суретте көрсетілген:
Программа жазу ... ... ... массивті оңжақ массивпен бірігіп кеткенше оңға қарай жылжыта беру ... ... ... ең ... енді ең ... ... бос секцияға (төменде көрсетілген программаның № 1 және №7 командалары) көшіру (өшіру) арқылы ... ... (№ 5 және №6 ... ... а+в+2 болады. Яғни бір артық енді ( №4 команда) ... ... ... ... түбіртек жаңа пайда болған қосындының сол жағында тұр.
1.
C 2
4.
C 5
7.
M 8
10.
2.
5.
8.
11.
3.
6.
9.
12.
стоп
Санның түбіртектің ... ма, ... ма ... ... ... шарттардың аса күрделілігі жағдайында санды іздеудің мынандай принципін қолдануға болады:
Түбіртекті оңға, солға қозғай отырып, түбіртектің бастапқы ... ... ... ен сала ... ... санды табамыз сонан соң белгілі қосу программасын қолданамыз. Бұл жағдайда түбіртектің сан ендерінің бірінің үстінде тұрған- тұрмағандығы тексеріледі. Егер ... ... онда есеп ... ... ... ... оң жағындағы секцияның және одан кейінгінің бостығы тексеріледі. Егер екеуі де бос ... онда ... бір адым ... ... ен ... ... соң осындай амал сол жақтан орындалады да түбіртек белгіленген жолмен оңжаққа ... ... және т.б. ... ... жолыққанға дейін жалғаса береді. Сонан соң жоғарыда қарастырылған программаларды қолдануға болады.
Пост машинасын ЭЕМ-нің қарапайым моделі деп ... ... Шын ... ЭЕМ де, Пост ... ... ... толтырылмаған ақпараттың бөлінбейтін тұғырлары (шаршылар- биттер);
элементар әрекеттердің шектелген жиынтығы - әрқайсысы бір актыда (адымда) орындалатын командалар-бар.
Екі ... да ... ... ... ... Дегенмен Пост машинасында ақпарат сызық бойынша орналасады да, бірінен соң бірі оқыла береді, ал ЭЕМ-де ақпаратты ... ... ... ... ЭЕМ ... ... әлде- қайда кең әрі Пост машинасы командаларына қарағанда айқын, т.с.с.
Тьюринг машинасы
Пост машинасына ұқсас, бірақ сәл ... ... ... ... ... (ТМ) есепші таспадан (ұяшықтарға бөлінген және солынан шектелген, бірақ оңынан ... оқып және ... ... ... ... мен амал атқарушы құрылғыдан тұрады. Құрылғы кейбір ақырлы жиынға (ішкі күй-жай әріппесіне) жататын дискретті күйлерінің бірінде болады. ... - ... күй деп ... да, ... ... ... ... әріптерін оқи да, өшіре де, баспаға шығара да алады. ... ... ... әр ... А ... әрпімен толтырылған. -"бос орын" әрпі бәрінен жиі кездеседі. Түбіртек әр мезет таспа ұяшығының бірі-ағымдағы жұмысшы ұяшық үстінде тұрады. Таспатар ... ... ... ... ... үстінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ шетіне шығу жағдайы болуы мүмкін. Ол жағдай, тоқтау ... ... ... орындау барысындағы машиналық тоқтау немесе апатты (болмайтын)тоқтау болып табылады.
ТМ жұмыс реті ( ... ... мен ... бар). ... ... ... ... өрнектеледі. Бұл кесте төрт тікжолды және (s+1) (t+1) жолы бар ... ... ... Әр жол мына ... ... ... ... мен таспатартар механизм үшін бүйрықтар жиынын біріктіру элементі белгіленген. Бұйрықтар жиыны: l-таспаны солға орналастыру, r-таспаны оңға ... ... ... vіj - a0, a1,...., at әріппесі таңбасын таспа ұяшығына жазудан, не түбіртекті қозғаудан, не машинаны тоқтатудан тұратын ТМ ... qіj ... ... ... ... мына ... ... жұмыс істейді:
Егер ТМ qі күйінде болса, түбіртек жұмысшы ұяшығынан aj таңбасын оқиды. qі aj таңбаларынан басталатын qі aj vіj qіj жолы ... ... рет ... Егер vіj- ... ... әрпі ... онда ... жұмысшы ұяшықтағыны өшіріп, оған осы әріпті апарып жазады. Егер vіj- таспатартар механизм үшін r немесе l командасы ... онда ... оңға ... ... бір ... ... ... таспаның сол жақ шетіне шығып кетпесе).
Тюринг машинасы А әріппесінің бір таңбасы бар ... ... ... ... оқып-жазатын түбіртектің орны мен бастапқы күйден (әдетте q0) тұратын ... ... ... жұмысын бастайды.
ТМ жұмысшы әріппесінде әртүрлі таңбалардың болуы таспада кезкелген мәтіндік және сандық ... ... ... ... ал ТМ ... орталығының әртүрлі күйге ауысуы Тюринг машинасының жұмыстың аралық нәтижелерін жадында ұстауын модельдейді. ТМ жұмысы ретін анықтайтын ... тура ... ... емес ... ... кезекпен бірінен соң бірі орындалмайды, таспадағы әлдебір ... ... ... ... ТМ кестесін жиі Тюринг машинасының сүлбесі деп атайды немесе ТМ құрылысы мен ... ... ... белгілі болғандықтан Тюринг машинасының өзімен теңдестіре салады. Тюринг машинасының бірнеше сүлбесі мысалдарын ... ... ... Г.Т. ... ... ... 2003, ... О. Камардинов Алматы, 1997ж
* А.Бочкин. ... ... ... ... ... школа, 1998-430

Пән: Информатика
Жұмыс түрі: Реферат
Көлемі: 7 бет
Бұл жұмыстың бағасы: 300 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Алгоритмнің тиімділігі мен күрделілігі. Тьюринг, Пост абстрактілі машиналарымен жұмыс29 бет
Тұжырымдар алгебрасы41 бет
Компьютер ұғымы10 бет
Компьютерлік схемотехниканың арифметикалық негіздері. ЭЕМ құрудың классикалық негіздері жайлы9 бет
: автомобиль жолдарының жабындарын қалпына келтіру және жөндеу машиналары мен жабдықтары3 бет
Автомобиль жолдары мен аэро алаңдарды жазда күту машиналары5 бет
Алматы облысы М.Бейсебаев атындағы агробизнес және менеджмент колледжінде «Тұрақты ток машиналарының құрылысы және жұмыс істеу принципі» тақырыбына оқыту әдістемесін жасау57 бет
Астық өңдеу машиналары27 бет
Ауыл шаруашылық машиналары31 бет
Жылу және суытқыш машиналары, Карно циклы19 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь