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

Жоспар
І.Кіріспе
II.Негізгі бөлім
1. Тьюринг машина сыртқы және ішкі алфавиттері
2. Командалары
3. Пост машинасы
4. Графиктері
III.Пайдаланған әдебиттер
IV.Қортынды

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

Пайдаланған әдебиеттер

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

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

3. А.Бочкин. Методика преподавания информатики. Минск, Вышэйшая школа, 1998-430

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 8 бет
Таңдаулыға:

Жоспар
І.Кіріспе
II.Негізгі бөлім
1. Тьюринг машина сыртқы және ішкі алфавиттері
2. Командалары
3. Пост машинасы
4. Графиктері
III.Пайдаланған әдебиттер
IV.Қортынды

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

командадан кейін
Түбіртектің оңға қозғалуы

Түбіртектің солға қозғалуы

М енін жазу m

С енін өшіру m

Басқаруды беру

Тоқтау стоп n

Әрбір команданың өз нөмірі бар: і. Жебеше қозғалыс бағытын көрсетеді. Команданың соңында тұрған екінші j саны жөнелткіш деп аталады. Басқаруды беру командасында екі жөнелткіш болуы мүмкін. Сондықтан да абстракты автомат програмасының екі бірдей қасиеті болуға тиіс:
1) бірінші орында тізімде әрқашан 1-нөмірлі команда тұрады,
екінші орында 2-нөмірлі және т.б;
2) кез келген команданы жөнелткіш әрқашан бағдарлама командаларының тізімінде орналасқан.
Таспаны солға немесе оңға қозғағаннан кейін түбіртек секцияның (бос немесе ен жазылған) күй-жайын оқиды.
Қай секциялар бос, қайсысы белгіленгендігі туралы ақпарат таспа күйін немесе автомат күйін бейнелейді. Автомат программасы деп командалардың ақырлы бос емес тізімін айтады.
Абстракты автомат жұмысы үшін бағдарламаны және бастапқы
күй-жайды, яғни түбіртектің орнын және таспа ұяшықтарының күй-жайын беру керек.
Әрбір қадам сайын бір команда орындалады, сонан соң нөмірі жөнелткіште көрсетілген команда орындала бастайды. Егер бұл команданың екі жөнелткіші болса, және түбіртек астында бос ұяшық болса, онда жоғарғы жөнелткіш нөмірі бар команда орындалады. Егер түбіртек астында ені бар ұяшық болса, онда төменгі жөнелткіш нөмірі бар команда орындалады. Басқаруды беру командасының орындалуы автомат күйін (ендердің ешбірі жойылмайды да қойылмайды, және таспа қозғалыссыз қалады). Автоматты іске қосқанда мына жағдайдың бірі орын алуы мүмкін:
автомат орындалмайтын команданы (енді бос емес ұяшыққа жазу, бос ұяшықта енді өшіру) орындауға дейін жетті, программаның орындалуы тоқталады, автомат тоқтайды, нәтижесіз тоқтау болады;
автомат стоп командасына дейін жетті, программа орындалды деп есептелінеді, нәтижелі тоқтау болады;
автомат нәтижелі де, нәтижесіз де тоқтауға жетпейді, жұмыс толассыз жүре береді (автомат ілініп қалды).
Пост машинасының типті программаларының орындалу барысындағы автомат жұмысын қарастырып көрейік. Түбіртектің бастапқы күйі берілсін және бос таспада екі ен салу керек болсын.
Бастапқы күйі

M 2

M 4

Стоп 4

Циклдық үрдісті ұйымдастыру үшін шартты өту командасын қалай пайдалануға болатынын көрсетейік. Таспада қатарынан бірнеше еннен тұратын жазба бар және түбіртек ең шеткі оң жақ еннің үстінде тұрсын. Түбіртекті солға бірінші бос орынға дейін жылжыту қажет.
Бастапқы күйі
1
2
3

стоп 3
1-жол

п. 1

2-жол

п. 1

3-жол

п. 1

4-жол

п. 3
стоп

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

n санын таспада ұзындығы n+1 массиві арқылы беру мақұлданған. Мысалы, 6,3 және 2 сандары автоматтық бейнелері арқылы суретте былай берілген:
Пост машинасында пайдаланылатын сандарды жазу жүйесі позициялық емес екендігіне көңіл аударайық.
Кез келген санға бір қосудың программасын жасайық. Ол ұшін Пост машинасы үшін мына қасиетке ие болатын программа жазу қажет болады: таспаға жазылған кезкелген п саны үшін программа п+1 санын таспаның кез келген жеріне жазып, нәтижелі тоқтауы керек.
Таспада ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.