Информатиканың іргелі негіздері
Тьюринг және Пост машиналарының көмегімен «алгоритм» ұғымын нақтылау
жүктеу/скачать 1,13 Mb.
|
лекция ИТН
| Тьюринг және Пост машиналарының көмегімен «алгоритм» ұғымын нақтылау.
Пост машинасы Шындығында, Тьюрингтен айырмашылығы Пост «машина» терминін қолданбаған, өзінің моделін алгоритмдік жүйе деп атаған. Біз екі автордың да ойларының бір екенін айта отырып, әдебиеттерде көрсетілгендей Пост машинасы туралы айтамыз. Посттың абстрактілі машинасы бірдей секцияларға бөлінген шексіз лентадан, және оқитын-жазатын головкадан тұрады. Әр секция немесе бос (яғни оған ештеңе жазылмаған), немесе толтырылған (белгіленген – яғни, оған белгі жазылған) болады. Лентаның қалпы деген ұғым енгізіледі, бұл ұғым қай секциялардың бос, қай секциялардың белгіленгендігі туралы ақпарат береді (басқаша айтқанда: лентаның қалпы – бұл белгілердің секциялар бойынша таралуы, яғни бұл секцияның әрбір сандық нөміріне не белгі, не «бос» белгісін сәйкес қоятын функция). Әрине, машина жұмысы процесінде лента қалпы өзгереді. Лентаның қалпын және головканың орналасуын Пост машинасының қалпы сипаттайды. Шолынулы секцияның үстіндегі головканы « » таңбасымен, ал белгіні секцияның ішіндегі «М» таңбасымен белгілеуге шарттасайық. Бос секцияда ешқандай белгі болмайды. Бір тактіде (оны қадам деп те болады) головка бір секцияға оңға немесе солға жылжып, белгіні қоя немесе өшіре алады. Пост машинасының жұмысы берілген жеке командалардан құрылған программа бойынша машинаның бір қалпынан екіншісіне өтуінен тұрады. Әрбір команда келесі құрылымға ие: xKy, мұндағы х – орындалатын команданың нөмірі; K – орындалатын әрекет туралы нұсқау; у – келесі команданың (ізбасардың) нөмірі. Келесі кестеде 6 әрекеттен тұратын машинаның командалар жүйесі берліген: Таблица 7.1.
Осы тізім келесі шарттармен толықтырылуы керек: Кез-келген (y) командасының ізбасарының номері міндетті түрде осы программада бар команданың номеріне сәйкес келуі керек. Егер осы шарттар орындалмаса, машинаның нәтижесіз тоқтатылуы болады, яғни, жоспарланған нәтижеге алынудан бұрын тоқтатылу орындалады. Осы жағдан қарағанда Тағы бір негізгі түсінік келесі болады: кез-келген шекті алфавит таңбалары цифрлармен кодталған болуы мүмкін болғандықтан, осылардан алынған сөзді түрлендіру кейбір сандарды өңдеу ережелері түрінде көрсетілуі мүмкін. Осы себептен Пост машинасында тек бүтін оң таңбалы сандарды ғана жазу (көрсету) қарастырылады. k бүтін саны Пост машинасының лентасында келесі қатар белгіленген k+1 секциялар арқылы жазылады, яғни бірлік санау жүйесі қолданылады. Лентада көршілес сандарды жазғанда бір немесе бірнеше бос секциялар арқылы бөледі. Төменде 0,2,3 сандарын жазу келтірілген:
Пост машинасының көмегімен шешілетін есептеу есептерінің шеңбері кең. Бірақ, жоғарыда айтылғандай барлығы элементар қадамдар деңгейінде белгіні қою немесе өшіру және головканы қозғалтуға келтіріледі. Мысал ретінде Пост машинасын меңгеруде талқыланатын бірнеше есептерді қарастырамыз. Программаның түрі машинаның бастапқы қалпына байланысты болғандықтан, ол есептің қойылымында анық көрсетілуі керек. Мысал 7.6 Лентада қандай-да бір сан жазылған және головка белгіленген секциялардың біреуін (кез-келгенін) шолуда. Осы санған бірлікті қосу программасын құр. Жағдай келесі суретте көрсетілген:
Есепті шешуді қамтамасыз ететін программа 4 командадан тұрады: 1 және 2 командаларды тәзбектей орындау машинаның екі такті жасау барысында головканың оңға жылжуына әкеледі. Бұл орынауыстыру головканың кезекті жылжуынан кейін оның астында бос ұяшық қалғанша орындалады – сонда 3 команда бойынша оған белгі қойылады және 4 команда бойынша машина тоқтатылады. Мысал 7.7 Лентада қандай-да бір сан жазылған, және головка жазбаның сол жағында орналасқан бос секциялардың бірін (кез-келгенін) шолуда. Осы санға бірлік қосу программасын құру керек. Программасы:
Программа жұмысына түсіндірме алдыңғы мысалдағыдай, тек айырмашылығы белгі бастапқы санның алдына қойылады. Комментарий к работе программы подобен приведенному выше с той лишь разницей, что метка ставится перед исходным числом. Пост машинасының көмегімен бірлік санау жүйесінде барлық арифметикалық әрекеттерді орындауға болатынын көрсетуге болады. Алдында көрсетілгендей сандар кез-келген дискретті ақпаратты көрсетуге қолданылады. Жекелей алғанда, лентаның қалпын екілік алфавиттегі сөз ретінде кқрсетуге болады, мұнда 0 бос секцияға сәйкес келеді, ал 1 белгіленген секцияға сәйкес келеді. Жұмыс процесі кезінде лента қалпы өзгереді, бастапқы сөзден шығатын екілік алфавитте көрсетілген сөзге ауысу орындалады.
жүктеу/скачать 1,13 Mb. Достарыңызбен бөлісу:
|