Информатиканың іргелі негіздері
жүктеу/скачать 1,13 Mb.
|
лекция ИТН
A={0,1,…,9, }сыртқы алфавитін қолданамыз, мұнда символы бос белгіге сәйкес келеді. Ішкі алфавит алдыңғы есептегідей екі қалыптан тұрады – жұмыс қалпы (q) және тоқтау (z) (Q={q, z}). Бастапқы сөз n, сол сияқты нәтиже – n+1 – ондық санау жүйесінде жазылады, және де цифрлар көрші ұяшықтарда бір-бірден, бос орынсыз жазылады. Функционалдық схема кесте түрінде көрсетіледі (қолайлылық үшін жол q қалпына, ал бағандар – сыртқы алфавит таңбаларына сәйкес келеді):
Айталық, бастапқы конфигурациясы 21q9болсын. Такт 1q9 q0L, яғни9таңбасы 0-ге ауысады да, головка ондықтар бірлігіне жылжиды – аралық конфигурация 2q10. Такт 2q1 z2S, яғни1таңбасы2-геауысады да соңғы конфигурациямен 2z20 тоқтау болады, яғни, 219+1қосынды нәтижесі алынды. Аталық, бастапқы конфигурация 99q9болсын. Такт 1q9 q0L, яғни, 9q90аралық конфигурациясы құрылады. Такт 2q9 q0L – q900 аралық конфигурациясы құрылады. Такт 3q9 q0L –q 000құрылады. Такт 4q z1S – z1000туындайды және жұмыс тоқтатылады. Осылайша, сипатталған алгоритм кез-келген бүтін сан мен бірлікті қосуды қамтамасыз етеді. Осылайша бірлікті емес, қандай-да бір бүтін m санын қосу үшін осы алгоритмді m рет қайталау кажеттігі түсінікті. Бүтін сандарды көбейту де санды өзіне-өзін қосуға келтіруге болады. Осыдан, Тьюринг машинасы маңызды қасиетке ие – қолда бар машиналарды біріктіру арқылы жаңа машина құру мүмкіндігі – мұндай амал композиция деп аталады. Өзінің құрылғылары бойынша Тьюринг машинасы тым примитивті. Ол алғашқы компьютерлерден әлдеқайда қарапрайым. Примитивтілігі – оның головкамен орындалатын – оқу және жазу элементар амалдар жиынтығы тым қарапайымдығында, және де сол сияқты жады ұяшықтарына қол жеткізу компьютерлердегідей адрес бойынша емес, лента бойымен тізбектей жылжу арқылы орындалатындығында. Осы себеппен, екі символды қосу немесе салыстыру сияқты қарапайым амалдарды Тьюринг машинасы бірнеше қадаммен жүргізеді, ал кәдімгі қосу және көбейту амалдары әлдеқайда көп қарапайым әрекеттер санын қажет етеді. Бірақ Тьюринг машинасы шынайы есептеуіш машиналардың моделі ретінде емес, тым қарапайым амалдармен қандай болсын күрделі алгоритмдерді құрудың принцитік (теориялық) мүмкіндігін көрсету үшін ойлап табылған, және де амалдардың өздерін де, және бірінен келесісіне өтуді де машина автоматты түрде орындайды. Тьюринг машинасы алгоритм ұғымын жетілдірудің жолдарының бірін береді. Осыған байланысты сұрақ туындайды: Тьюринг машинасы ұғымы қаншалықты жалпы болып табылады? Тьюринг машинасы көмегімен алгоритмдерді беру тәсілін әмбебап деп есептеуге бола ма? Кез-келген алгоритм осылайша беріле ала ма? Қазіргі алгоритмдер теориясы осы сұрақтарға жауапты келесі гипотеза түрінде береді: Кез-келген алгоритм тьюрингтік функционалдық схема арқылы беріліп, сәйкес Тьюринг машинасында жүзеге асырыла алады. Бұл гипотеза Тьюринг тезисі деген атауға ие болды. Черч тезисі сияқты оны дәлелдеуге болмайды, себебі ол қатаң емес алгоритм ұғымын Тьюринг машинасының қатаң анықтамасымен байланыстырып тұр. Негізінде егер тьюрингтік функционалдық схема арқылы жүзеге аспайтын алгоритмге мысал келтіру мүмкін болса бұл гипотезаны жоққа шығаруға боолады. Бірақ барлық осы кезге дейін белгілі алгоритмдер тьюрингтік функционалдық схема арқылы беріле алады. жүктеу/скачать 1,13 Mb. Достарыңызбен бөлісу:
|