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