Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 0,9 Mb.
|
Алгоритм 001
| Тьюринг машиналары (ТМ) тіршілік өмірде тұтынылатын нақтылы машина емес. Ол қиялдан туған – елестік машина. Айқынырақ айтқанда, «Тьюрингмашинасы» дегеніміз алгоритмдер туралы ұғымды дәлді анықтау үшін және оның ерекшеліктері мен қызметін көрнекілеп талдау жәнетүсіндіру мақсатымен алынған дерексіз үлгілеме жүйенің шартты атауы болып табылады.
Алан Матисон Тьюринг (1954-1954) ағылшын инженері әрі математигі. Оның ғылыми еңбектері, көбінесе, математикалық логика мен есептегіш машина жұмысының негіздемелік мәселелерін зерттеуге және уағыздауға арналған. Кибернетика ғылымы мен электронды есептегіш машиналар теориясының негізін алғаш қалаушы Норберт Виннер (1894- 1964) : «Тьюринг расында, ғалымдардың ішіндегі ойша тәжірибе жүргізу арқылы машиналардың логикалық мүмкіндігін тұңғыш зерттнген адам болды. Тьюринг машинасы дәлді математикалық ұғым болып табылады. Оны ешұқашан кездеспейтін және ұшы қиыақырсыз жады бар механикалық құрылым деп қарастырады. Анықтама: Тьюринг машинасы (ТМ) деп ұзындықтары бірдей шаршы ұяларға бөлінген ақырсыз таспамен және уақыттың әрбір моментінде таспаның мазмұнын есепке алатын жаңа белгілеменіжазатын және таспаны жылжытатын Д тетіктен жабдықталған А ақырсыз автоматты айтады. Тьюринг машинасы соңғы автоматтандырудың жай моделі болып табылады. Қарастырайық, Тьюринг машинасы мен жай модельдік автоматтың айырмашылығын. Жай автомат ішкі құрлысына қарай күрделі емес және ол екі лента арқылы жұмыс атқарады: енгізу және шығару. Жай автомат такт бойынша жұмыс істейді. Әрбір такт енгізу символдар көмегімен лентаға енгізілген ұяшықтарды санайды, және кейбір символдарды алфавит бойынша тереді. Функционалдық автоматты бейнелеуді оның программасы ретінде санауға блады: онда 4 – тік санау жүйесі қолданылады < s, a, p, y> - бұл өткен қалып, а – келесі енгізілген сигнал, р – келесі қалып және у – кезекті шығару сигналы. Соңғы автомат программасы аргуметерді санайды, және функцияның нәтижесін шығарады: S*X – S*Y Тьюринг машинасының түсінігі туралы айтыңыз. Тьюринг машинасы үш бөліктен тұрады: лентадан, оқитын-жазатын головкадан және логикалық құрылғыдан. Лента сырқы жады ретінде болады; ол шектелмеген (шексіз) болып есептелінеді – бұл Тьюринг машинасының моледьді құрылғы екенін көрсетеді, себебі ешқандай шынайы құрылғының шексіз көлемді жадысы болмайды. Пост машинасындағыдай, лента жеке бөліктерге бөлінген, бірақ, Тьюринг машинасында головка қозғалмайды, ал лента оған қатысты оңға және солға қозғалады. Басқа айырмашылығы ол екілік алфавитте емес, кандай-да бір кез-келген A = {, a1…a n} шекті алфавитте жұмыс істейді – бұл алфавит сыртқы алфавит деп аталады. Онда бос белгі деп аталатын арнайы символы ерекшеленіп тұр, оны қандай-да бір ұяшыққа жіберу ондағы белгіні өшіріп, ұяшықты бос қалдырады. Лентаның әр ұяшығына бір ғана символ жазылады. Лентада сақталған ақпарат сыртқы алфавиттің бос белгісінен басқа белгілерінің шектелген тізбегімен бейнеленеді. Нақты Тьюринг машинасы A и Q жиындарының элементтерін көрсетумен, және сол сияқты ЛҚ-ны жүзеге асыратын логикалық функциялармен , яғни түрлендіру ережелерінің жиынтығымен беріледі. Әртүрлі A, Q жиындары мен логикалық функциялар шексіз көп болатыны түсінікті, яғни Тьюринг машинасы да сол сияқты шексіз көп. Тьюринг машинасының командаларын атаңыз. Головка әрқашан лента ұяшықтарының бірінің үстінде орналасады. Жұмыс тактілермен (қадамдармен) жүреді. Головкаларымен орындалатын командалар жүйесі қарапайым: әр такті сайын ол шолынулы ұяшықтағы ai белгісін aj белгісіне ауыстырады. Мұнда келесі сәйкестіктер болуы мүмкін: j = i – бұл шолынулы ұяшықта ештеңе өзгермегенін білдіреді; i, j = 0 – ұяшықта сақтаулы белгі бос белгіге ауыстырылғанын, яғни өшірілгенін білдіреді; жүктеу/скачать 0,9 Mb. Достарыңызбен бөлісу:
|