«Информатиканың теориялық негіздері»
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- ЕМЕС, ЖӘНЕ, НЕМЕСЕ ункцияларының ақиқаттық кестесі
- 9-ДӘРІС. Алгоритм ұғымы. Алгоритмдер теориясынын негізгі ұғымдары. Қарастырылатын сұрақтар
| НЕМЕСЕ функциясы - бұл функция екі немесе одан да көп аргумент функциясы. НЕМЕСЕ функциясы 1-ге тең, егер оның ең болмағанда бір аргументі 1-ге тең болса (басқа атаулары: дизъюнкция). Белгіленуі: Ү=аЬ. Табиғи тілдерде дизъюнкция функциясы «немесе» шылауымен айтылып, мына түрдегі сөйлемдерде қолданылады: Біз келесі жағалауға өте аламыз, егер өзен таяз НЕМЕСЕ көпір бүтін болса.
Логикалық формула (логикалық өрнек) – логикалық шамалар мен логикалық амалдар таңбасынан тұратын формула. Логикалық формуланың есептелуінің нәтижесі тек қана АҚИҚАТ немесе ЖАЛҒАН болады. НЕМЕСЕ элементін жүзеге асыратын элемент – дизъюнктордың шартты белгісі төмендегідей. ЕМЕС, ЖӘНЕ, НЕМЕСЕ ункцияларының ақиқаттық кестесі:
9-ДӘРІС. Алгоритм ұғымы. Алгоритмдер теориясынын негізгі ұғымдары. Қарастырылатын сұрақтар: Тьюринг машинасы және Пост машинасы көмегімен алгоритм ұғымын айқындау. Марковтың нормальды алгоритмдері. Маккарти бойынша рекурсивті алгоримдер. Алгоримдер арқылы шешілмейтін есептер. Тарихи жағынан «алгоритм» термині ІХ ғасырда өмір сүрген шығыс математигі Мухаммед ибн Муса әл-Хорезми тегінен шыққан. Ол алғаш негізгі төрт арифметикалық амалдың ережесін құрастырған. Алдымен осы ережелер алгоритмдер деп аталып, кейіннен термин ары қарай дамуын ең алдымен математикада жалғастырды – алгоритм деп қандай-да бір бастапқы мәліметтер класына бірдей орындалатын есептеулер тәсілі атала бастады, мысалы, функцияның туындысын табу. Математикаға оқытудың маңызды міндеттерінің бірі жалпы есептеу алгоритмдерін меңгерту болып табылады. Басқаша айтқанда, егер мектеп оқушысын екі санды бағанмен көбейтуге үйретсе, бұл жерде оған тек сол екі санды көбейтуді ғана емес, жалпы кез-келген екі санды көбейтуге қолданылатын әмбебап тәсілді (алгоритмді) үйретуде дегенді білдіреді. Мұндай мысалдарды көптеп келтіруге болады. Тек математикада ғана емес – «алгоритм» термині жалпы қоданысқа ие болды. Осыған байланысты сұрақ туындайды: алгритмнің жалпы және нақты анықтамасын құруға болды ма («кез-келген алгоритм» ұғымы )? Мысалы осы анықтаманы пайдаланып, қандай-да бір нұсқаулар жиынтығы алгоритм бола алатындығын немесе бола алмайтындығын анықтауға бола ма? Егер дұрыс мағынада айтсақ, алгоритм дегеніміз – қандай-да бір класстың кез-келген есебін шешуді қамтамасыз ететін, нақты анықталған (бірмәнді), қарапайым (элементар) әрекеттер тізбегі. Бірақ бұл анықтаманы алгоритмнің қатаң анықтамасы ретінде қабылдауға болмайды. Себебі оның ішінде басқа анықталмаған ұғымдар қолданылған – бірмәнділік, қарапайымдылық және т.б. Бұл ұғымдарды алгоритмге тән жалпы қасиеттерді көрстеу арқылы жетілдіруге болады. Оларға төмендегі қасиеттер жатады: 1. Алгоритмнің дискреттілігі - алгоритмнің жеке қадамдарға бөлінетінін білдіреді, сол сияқты келесі қадамның орындалуы тек қана алдыңғы қадамдағы барлық амалдар орындалып болғаннан кейін ғана мүмкін болады. Мұнда аралық мәліметтер жиынтығы аяқталған және олар алдыңғы қадамдағы мәліметтерге қандай-да бір ережені қолдану арқылы алынады. 2. Алгоритмнің детерминирленгендігі - кез-келген қадамдағы аралық шамалардың жиынтығы алдыңғы қадамда болған шамалар жүйесімен бірмәнді анықталатынын білдіреді. Бұл қасиет алгоритмнің нәтижесі оның орындаушысына байланысты емес, тек енгізілген мәліметтер мен алгоритмнің өзінің қадамдарына (әрекеттер тізбегіне) байланысты екенін білдіреді. 3. Қадамдардың элементарлығы – келесі шамалар жиынтығын алдыңғыдан алу заңдылығы қарапайым әрі жергілікті болу керек. Қандай қадамды (әрекетті) элементарлы деп есептеуге болатыны алгоритм орындаушысының ерекшеліктеріне байланысты анықталады. 4. Алгоритмнің бағыттылығы - егер қандай-да бір бастапқы мәліметтерден келесі шамаларды алу тәсілі нәтижеге әкелмесе, онда алгоритм нәтижесі ретінде нені есептеу керектігі көрсетілуі керек. 5. Алгоритмнің көпшілдігі – бастапқы шамалар жүйесі қандай-да бір жиыннан таңдалынады. Бұл қасиет бір алгоритм, яғни бір әрекеттер жиынтығы, жалпы жағдайда, кандай-да бір есептер класын (яғни, көп есептерді) шешуге қолданылатынын білдіреді. Практика үшін, жекелеме алғанда компьютерде есепті шешу үшін бұл қасиет маңызды (существенно), себебі, неғұрлым біртипті есептердің үлкен шеңберін шешуге мүмкіндік берсе, бағдарламаның пайдаланушылық құндылығы соғұрлым жоғары болады. Бірақ алгоритмдік теория құру үшін бұл қасиет қолнысқа ие емес (не существенно) және міндетті болып табылмайды. 1-5 қасиеттерді көрсету арқылы анықталған алгоритм түсінігін қатаң деп есептеуге болмайды, себебі қасиеттерді айтқанда «шама», «тәсіл», «қарапайым», «жергілікті» және басқа да нақты мағынасы орнатылмаған терминдер пайдаланылды. Ары қарай бұл анықтаманы алгоритмнің қатаң емес түсінігі деп атаймыз. Сұрақ туындайды: алгоритмнің нақты анықтамасын алу осыншама маңызды ма, егер онсыз да алгоритмдерді құрып, қолдануға болса (тіпті, терминнің өзін қолданбай-ақ)? Және де алгоритмнің интуитивті ұғымы қатаң болмаса да анық болды, тіпті ХХ ғасырға дейін қандай-да бір процесстің алгоритм болатындығы немесе болмайтындығы туралы математиктер арасында дау туындаған жағдайы болған емес. ХХ ғасырдың басында алгоритмдік шешілуі көрінбейтін мәселелер туындаған кезде жағдай бірқатар өзгерді. Шыныда да, алгоритмнің бар болуын дәлелдеу үшін белгілі тәсілдерді пайдаланып осы есепті шешу керек, немесе ол болмаса жаңа тәсілдерді ұсыну керек – мұндай жағдайда сипатталған процестің алгоритм екеніне көз жеткізу үшін алгоритмнің интуитивті ұғымы да жеткілікті. Қандай-да бір есептің (немесе есептер класының) шешілу алгоритмін құрудың мүмкін еместігі фактісін дәлелдеу әлдеқайда күрделірек – алгоримнің нақты анықтамасынсыз бұл мәселе өзінің мағынасын жоғалтады. Алгоритмнің нақты анықтамасын құруды қажет ететін басқа негіз – алгоритмдік әрекеттерді орындау кезінде «қадамның қарапайымдылығы» түсінігінің анықталмағандығы болып табылады. Математика сандық объектілерді қарастырғанда олармен орындалатын әрекеттер есептеу амалдарының қандай-да бір тізбегіне келтірілетін де, және де арифметикалық амалдар, сол сияқты шамалар арасындағы қатынасты тексеруге байланысты бірнеше логикалық амалдар (теңдік, теңсіздік, кіші, үлкен және т.б.) элементар қадамдар деп есептелінетін. Бірақ, математика кешірек күрделі объектілердің (векторлар, матрицалар, жиындар, функциялар) қасиеттері мен оларға қолданылатын амалдарды зерттеуге көшті де, «қадамның қарапайымдылығы» түсінігі оңай көрінбейтін болды. Мысалы, интеграл алу немесе матрицаны транспондауды қарапайым қадам деп қарастыруға бола ма? Ақырында, есеп бірнеше алгоритм құруға мүмкіндік берген жағдайда теориялық және практикалық тұрғыдан алғанда оларды салыстыру және ең тиімдісін таңдау туралы сұрақ туындайды, бұл сұрақты да шешу мәселесі алгоритмнің қатаң анықтамасынсыз мүмкін емес. «Кез-келген алгоритм» ұғымының нақты анықтамасын, яғни, алгоритмнің барлық ойға келетін түрлері жатқызылатын максималды жалпы анықтамасын құру қажеттілігі осылайша туындады. ХХ ғасырдың 20-шы жылдарында алгоритмнің нақты анықтамасын құру мәселесі маңызды математикалық мәселелердің біріне айналды. Бұл анықтама бір жағынан алгоритмнің интуитивті түсінігінің маңызына сәйкес келуі қажет болса, екінші жағынан формальды түрде қатаң болуы қажет болды. Осындай түсінікті құрастыру әрекеттері ХХ ғасырдың 30-шы жылдарында алгоритмдер теориясының өз алдына жеке ғылым болып қалыптасуына әкелді. Бұл ғылым математикалық логикамен бірге математиканың негізгі құралдарын – дәледеу тәсілдерін, аксиоматикалық теорияны құру тәсілдерін, математикалық процедуралардың қасиеттерін және т.б. қарастырады. 40-шы – 50-ші жылдарда есептеу техникасы мен оның функционалдануы мен қолданылуына байланысты ғылымдардың қарқынды дамуы кезінде осы ғылымдардың негізінде алгоритмдер теориясы жататыны анықталды, себебі компьютер алгоритмдер түрінде көрсетілетін процедураларды ғана жүзеге асыра алады. Кез-келген программа алгоритмнің орындаушы – компьютер «түсінетін» тілде жазылуы. Осылайша практикалық тұрғыдан алғанда да алгоритм ұғымын жетілдіру маңызды болып табылады. Алгоритм түсінігін жетілдіру алгоритмдік модельдер аясында жүргізіледі. Модель есепті шешу кезінде қолдануға болатын құралдар жиынтығын көрсетеді, яғни, элементар қадамдар тізімін, келесі қадамды анықтау тәсілін, т.б. Алгоритмдік модельдер теориялық және практикалық болуы мүмкін. Теориялық тұрғыдан алғанда модельдердің бір жағынан әмбебап болғаны, яғни, кез-келген алгоритмді сипаттауға мүмкіндік бергені, екінші жағынан неғұрлым қарапайым болғаны, яғни, есепті шешудің неғұрлым аз құралын пайдаланғаны ерекше қызығушылық тудырады. Қарапайымдылық талабы алгоритмнің нақты қажет элементтері мен қасиеттерін ерекшелеп, осы қасиеттер туралы жалпы тұжырымдарды дәлелдеуді қамтамасыз ету үшін маңызды. Практикалық және қолданбалы модельдерде программалаудың қолайлылығы мен есептеу тиімділігі маңыздырақ, сондықтан олардың құралдары – қарапайым қадамдар жиынтығы, т.б. - әлдеқайда көп және күрделірек, бұл теориялық анализді қиындатады. Алгоритмнің қатаң анықтамасын құрудың теориялық қырларында тарихи жағынан негізгі үш бағыт бөлініп шықты. Бірінші бағыт аргументтердің бүтінсанды мәндеріне тәуелді сандық функциялардың мәндерін есептеуге мүмкіндік беретін алгоритмдерді қарастырумен байланысты – мұндай функциялар есептелінетін функциялар атауына ие болды. Есептелінетін функциялар ұғымы алгоритмдер ұғымы сияқты қатаң ұғым емес. Бірақ А.Черчтің, К.Гедельдің, С.Клинидің еңбектерінің арқасында барлық жерде анықталған есептелінетін функциялар класының қатаң анықталатын бөлікті рекурсиялы функциялар класымен ұқсастығы негізделді. Бұл алгоритмдік шешілу мәселесін есепті шешешін рекурсиялы функцияны құру мүмкіндігін (немесе мүмкін еместігін) дәлелдеуге келтіруге мүмкіндік берді. Дәл осы жолмен А.Черчке математикалық логиканың мәселелерінің бірі – предикаттардың ақиқаттығын есептеу мәселесінің шешілмейтіндігін дәлелдеудің сәті түсті. Екінші бағыт машиналық математикамен бай»ланысты. Алгоритм орындаушысы – алгоритмде көрсетілген әрекеттер тізімін орындауға қабілетті субъект немесе құрылғы. Әрбір орындаушыға әрекеттерді орындауға нұсқау – арнайы тілдер арқылы беріледі. Мұнда әрекеттерді көрсететін қызметші сөздер, сол сияқты оларды біріктіретін синтаксикалық ережелер, командалар жиынтығы орындаушының командалар жиынтығын (СКИ) құрайды. Дискретті информацияны өңдеудегі қарапайым бір белгіні екіншісімен ауыстыру болып табылады. Бірақ қарапайым әрекеттер тізімін орындайтын абстрактілі және шынайы құрылғы жасауға болады. Орындаушыға арналған мұндай алгоритм құру барысында интегралданған командалар тізбегін көрсету жеткілікті, ал оларды шын қарапайым командалар тізбегіне түрлендіруді орындаушы өзі атқарады. Мұндай алгоритмдеудің «көпсатылылығы» компьютерді басқару барысында көп қолданылады. Шын қарапайым әрекет деп процессордың әрекеттерін айтуға болады қазіргі процессорларда олар бірнеше жүз немесе мыңға барады) – оларды машиналық команда, ал белгіленуін машиналық кодтар деп атайды. Машиналық кодтардан бөлінген бірінші (төменгі) деңгейдегі ассемблер коды есептелінеді, яғни ішкі (аппараттық –тәуелді) тіл. Қарапайым әрекеттерді күрделі командаларға біріктіру бұл деңгейде әлі жүргізілмейді және ассемблердің жалпы командалар саны процессордың командалар санымен бірдей болады. Бірақ машиналық пен процессор регистрлерін-мнемоникаларды символдық бейнелеу формалары қолданылады. Бұл пайдаланушыға екілік машиналық кодтан қарағанда қолайлы. Мнемониктерді машиналық командаларға аударуды – ассемблер программасы жүзеге асырады. Программист орындаушы ретінде осы тілмен жұмыс істейді. Қарапайым әрекеттерді біріктіретін командалар жоғары деңгейдегі программалау тілдерінде көрінеді. Мысалы, «Write» сөзін программа текстінде жазу жеткілікті. Ал транслятор оларды қарапайым қадамдарға айналдырады. Программистке қарағанда бұл жағдайда орындаушы программалау тілінің трансляторы есептеледі. Бұдан жоғары қарапайым интеграциялау деңгейлерін қолданбалы программалардан көреміз. Бұл жерде ақырғы пайдаланушыға қарағанда қолданбалы программа орындаушы болып тұр. Мұндау орындаушының командалар жүйесіне барлық басқару командалары кіреді, яғни меню, экрандық батырмалар және т.б. интерфейс элементтері. Бір команданы орындау күрделі әрекеттердің тізімін орындауға әкеледі, мысалы текстің көп жолдарын туралау. Осылайша алгоритмді жазу барысында алгоритмді көрсету тілі формальды болуы мүмкін, ал онда орындаушының өзімен шынайы қарапайым әрекеттерге аударылатын күрделі командалар қолданылады. 7.3 Алгоритм абстрактілі машина ретінде 7.3.1 Жалпы қырлары Бөлікті рекурсиялы функциялар класының нақты сипаттамасы Черч тезисімен бірге алгоритм үғымын жетілдіру туралы есептің мүмкін шешімдерінің бірін береді. Бірақ, бұл шешім толықтай тура емес, себебі есептелінетін функция ұғымы алгоритм ұғымына қатысты екінші болып тұр. Алгоритм ұғымы анықтамасының өзін тікелей жетілдіріп алып, содан кейін оның көмегімен есептелінетін функциялар класын нақты анықтауға болмай ма деген сұрақ туындайды. Іздеудің мұндай бағыты басқа алгоритм модельдерінің класын құруға әкелді. Оның негізгі идеясы келесіден тұрады: алгоритмдік процесстер – бұл белгілі бір үлгі бойынша құрылған, осылайша жеке амалдарды адамның орындауын модельдейтін машиналар орындайтын процесстер. Мұндай машинаның қызмет етуі (функционирование) қандай-да бір алгоритмнің орындалуы болып табылады. Алгоритмнің қасиеттерінен мұндай машиналарға жалпы талаптарды құруға болады: олардың функционалдану сипаты дискретті болуы тиіс, яғни әрбіреуі алдыңғысы аяқталған соң ғана орындалатын жеке қадамдардан тұруы керек; әрекеттері детерминирленген болуы керек, яғни, қадамдар қатаң тәртіппен орындалады, ал олардың нәтижесі қадамның өзінде және алдыңғы қадамдардың нәтижесімен анықталады; жұмыс басталмас бұрын машинаға алгоритмнің анықталу облысынан бастапқы мәліметтер беріледі; машинаның шекті қадамдар санынан кейін нәтиже алынуы тиіс (немесе нәтиже ретінде нені есептеу керектігі жөнінде ақпарат); машина әмбебап болу керек, яғни оның көмегімен кез-келген алгоритмді орындауға болатындай болуы керек; Неғұрлым сипатталған машинаның құрылымы қарапайым болса және оның қадамдары неғұрлым элементар болса, соғұрлым оның жұмысын алгоритм деп есептеуге негіз көбірек болады. Қандай қадамдарды элементар қадамдар қатарына жатқызуға болады деген сұраққа жауап беру үшін қандай-да бір шекті алфавит көмегімен көрсетілген ақпаратты түрлендіру мәселесіне оралайық. Алфавиттің шектілігі талабы шешімнің шекті қадамдар санынан кейін алынуы керектігі туралы жағдайдың салдары болап табылады. Егер ақпарат дискретті формада көрсетілмесе, мысалы нақты сандар, онда оны оңдеу жалпы жағдайда шексіз қадамдар санынан тұруы мүмкін (мысалы, р санының цифрларын табу немесе 2 санынан квадрат түбір табу). Осылайша, алгоритм дегеніміз шекті алфавит көмегімен көрсетілген берілгендерге орындалатын әрекеттердің шекті тізбегі. Осы айтылғандарды есептке алсақ, В.М.Глушков берген алгоритм анықтамасы түсінікті болады: Алгоритм – бұл кез-келген шекті алфавит үстінен ақпаратты түрлендіру ережелерінің шекті жүйесі. Айталық, алгоритмнің анықталу жүйесінен алынған берілгендер А алфавитінің көмегімен көрсетілсін және {a1…a n} белгілерінің шекті тізбегін құрсын – мұндай тізбек сөз деп аталады. Алгоритмді орындау нәтижесінде басқа В алфавитінде көрсетілген жаңа {b1…bm} сөзі құрылсын. Бір қарағанда мұндай түрлендіру кезінде элементар болып келесі амалдар (қадамдар) ерекшеленеді: ai бастапқы сөзінің бір белгісін В алфавитінен алынған bj белгісімен ауыстыру; бастапқы сөздің белгісін өшіру; бастапқы сөзге В алфавитінің белгісін қосу; Бірақ егер алфавиттерге бос белгі мағынасы бар белгілер қосылған болса, және де оларды сөзге оң жағынан немесе сол жағынан қосу бұл сөзді өзгертпесе, онда (2) амалдың ai –ді бос белгімен ауыстыру екенін және (3) амалдың бос белгіні bj белгісімен ауыстыру екенін оңай көруге болады. Осылайша, барлық мүмкін алфпавитті түрлендірулер (1) амалға – бір белгіні екіншімен ауыстыруға келтіріледі. Дәл осы себептен абстрактілі машиналардың функционалдануы оның жадыда жазылған (бұл ретте шексіз лента алынады) символдарды шолуына (яғни, оларды оқып, тануына) келтіріледі, және де өзінің қалпына және шолынған символдың қандай екеніне байланысты оны басқа символмен ауыстырады; осыдан кейін ол жаңа қалыпқа өтеді, келесі символды оқиды, және т.с.с. жұмысты тоқтату командасына дейін. Мұндай машиналар таза модельді, теориялық құрылым болғандықтан, олар абстрактілі машиналар деген атауға ие болған және мүмкін әмебеп алгоритмдік жүйе ретінде қарастырылады. Абстрактілі машина ретіндегі алгоритм концепциясын (1936-1937 жылдары) ағылшын математигі Алан Тьюринг және оның американдық әріптесі Эмиль Пост бір уақытта дерлік ұсынды. Олардың маңыздылығының тағы бір себебі – олар тек 8-9 жылдан кейін пайда болған мәліметтерді өңдеуге арналған шынайы құрылғылардың (есептеуіш машиналардың) негізгі принциптік сипатын болжап білді. Посттың алгоритмдік машинасы Шындығында, Тьюрингтен айырмашылығы Пост «машина» терминін қолданбаған, өзінің моделін алгоритмдік жүйе деп атаған. Біз екі автордың да ойларының бір екенін айта отырып, әдебиеттерде көрсетілгендей Пост машинасы туралы айтамыз. Посттың абстрактілі машинасы бірдей секцияларға бөлінген шексіз лентадан, және оқитын-жазатын головкадан тұрады. Әр секция немесе бос (яғни оған ештеңе жазылмаған), немесе толтырылған (белгіленген – яғни, оған белгі жазылған) болады. Лентаның қалпы деген ұғым енгізіледі, бұл ұғым қай секциялардың бос, қай секциялардың белгіленгендігі туралы ақпарат береді (басқаша айтқанда: лентаның қалпы – бұл белгілердің секциялар бойынша таралуы, яғни бұл секцияның әрбір сандық нөміріне не белгі, не «бос» белгісін сәйкес қоятын функция). Әрине, машина жұмысы процесінде лента қалпы өзгереді. Лентаның қалпын және головканың орналасуын Пост машинасының қалпы сипаттайды. Шолынулы секцияның үстіндегі головканы « » таңбасымен, ал белгіні секцияның ішіндегі «М» таңбасымен белгілеуге шарттасайық. Бос секцияда ешқандай белгі болмайды. Бір тактіде (оны қадам деп те болады) головка бір секцияға оңға немесе солға жылжып, белгіні қоя немесе өшіре алады. Пост машинасының жұмысы берілген жеке командалардан құрылған программа бойынша машинаның бір қалпынан екіншісіне өтуінен тұрады. Әрбір команда келесі құрылымға ие: xKy, мұндағы х – орындалатын команданың нөмірі; K – орындалатын әрекет туралы нұсқау; у – келесі команданың (ізбасардың) нөмірі. Келесі кестеде 6 әрекеттен тұратын машинаның командалар жүйесі берліген: Таблица 7.1.
Осы тізім келесі шарттармен толықтырылуы керек: Кез-келген (y) командасының ізбасарының номері міндетті түрде осы программада бар команданың номеріне сәйкес келуі керек. Егер осы шарттар орындалмаса, машинаның нәтижесіз тоқтатылуы болады, яғни, жоспарланған нәтижеге алынудан бұрын тоқтатылу орындалады. Осы жағдан қарағанда Тағы бір негізгі түсінік келесі болады: кез-келген шекті алфавит таңбалары цифрлармен кодталған болуы мүмкін болғандықтан, осылардан алынған сөзді түрлендіру кейбір сандарды өңдеу ережелері түрінде көрсетілуі мүмкін. Осы себептен Пост машинасында тек бүтін оң таңбалы сандарды ғана жазу (көрсету) қарастырылады. k бүтін саны Пост машинасының лентасында келесі қатар белгіленген k+1 секциялар арқылы жазылады, яғни бірлік санау жүйесі қолданылады. Лентада көршілес сандарды жазғанда бір немесе бірнеше бос секциялар арқылы бөледі. Төменде 0,2,3 сандарын жазу келтірілген:
Пост машинасының көмегімен шешілетін есептеу есептерінің шеңбері кең. Бірақ, жоғарыда айтылғандай барлығы элементар қадамдар деңгейінде белгіні қою немесе өшіру және головканы қозғалтуға келтіріледі. Мысал ретінде Пост машинасын меңгеруде талқыланатын бірнеше есептерді қарастырамыз. Программаның түрі машинаның бастапқы қалпына байланысты болғандықтан, ол есептің қойылымында анық көрсетілуі керек. Мысал 7.6 Лентада қандай-да бір сан жазылған және головка белгіленген секциялардың біреуін (кез-келгенін) шолуда. Осы санған бірлікті қосу программасын құр. Жағдай келесі суретте көрсетілген: Есепті шешуді қамтамасыз ететін программа 4 командадан тұрады: 1 және 2 командаларды тәзбектей орындау машинаның екі такті жасау барысында головканың оңға жылжуына әкеледі. Бұл орынауыстыру головканың кезекті жылжуынан кейін оның астында бос ұяшық қалғанша орындалады – сонда 3 команда бойынша оған белгі қойылады және 4 команда бойынша машина тоқтатылады. Мысал 7.7 Лентада қандай-да бір сан жазылған, және головка жазбаның сол жағында орналасқан бос секциялардың бірін (кез-келгенін) шолуда. Осы санға бірлік қосу программасын құру керек. Программасы: Программа жұмысына түсіндірме алдыңғы мысалдағыдай, тек айырмашылығы белгі бастапқы санның алдына қойылады. Комментарий к работе программы подобен приведенному выше с той лишь разницей, что метка ставится перед исходным числом. Пост машинасының көмегімен бірлік санау жүйесінде барлық арифметикалық әрекеттерді орындауға болатынын көрсетуге болады. Алдында көрсетілгендей сандар кез-келген дискретті ақпаратты көрсетуге қолданылады. Жекелей алғанда, лентаның қалпын екілік алфавиттегі сөз ретінде кқрсетуге болады, мұнда 0 бос секцияға сәйкес келеді, ал 1 белгіленген секцияға сәйкес келеді. Жұмыс процесі кезінде лента қалпы өзгереді, бастапқы сөзден шығатын екілік алфавитте көрсетілген сөзге ауысу орындалады. Тьюрингтің алгоритмдік машинасы Тьюринг машинасы үш бөліктен тұрады: лентадан, оқитын-жазатын головкадан және логикалық құрылғыдан ( 7.1 суретті қара). Лента сырқы жады ретінде болады; ол шектелмеген (шексіз) болып есептелінеді – бұл Тьюринг машинасының моледьді құрылғы екенін көрсетеді, себебі ешқандай шынайы құрылғының шексіз көлемді жадысы болмайды. 7.1. сурет. Тьюринг машинасының схемасы. Пост машинасындағыдай, лента жеке бөліктерге бөлінген, бірақ, Тьюринг машинасында головка қозғалмайды, ал лента оған қатысты оңға және солға қозғалады. Басқа айырмашылығы ол екілік алфавитте емес, кандай-да бір кез-келген A = { , a1…a n} шекті алфавитте жұмыс істейді – бұл алфавит сыртқы алфавит деп аталады. Онда бос белгі деп аталатын арнайы символы ерекшеленіп тұр, оны қандай-да бір ұяшыққа жіберу ондағы белгіні өшіріп, ұяшықты бос қалдырады. Лентаның әр ұяшығына бір ғана символ жазылады. Лентада сақталған ақпарат сыртқы алфавиттің бос белгісінен басқа белгілерінің шектелген тізбегімен бейнеленеді. Головка әрқашан лента ұяшықтарының бірінің үстінде орналасады. Жұмыс тактілермен (қадамдармен) жүреді. Головкаларымен орындалатын командалар жүйесі қарапайым: әр такті сайын ол шолынулы ұяшықтағы ai белгісін aj белгісіне ауыстырады. Мұнда келесі сәйкестіктер болуы мүмкін: жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|