Техникалық факультет
жүктеу/скачать 25,15 Kb.
|
|
Ақтөбе өңірлік Құдайберген Жұбанов атындағы университет Техникалық факультет Мәнжазба Тьюрнинг машинсы Орындаған:Маратов Асылжан Тобы :Кико-101 Тексерген:Байбақтина Ақсәуле Жоспар Кіріспе Негізгі бөлім 1. Тьюиринг машинасы 2. Тьюиринг машинасының жұмысының сипаттамасы 3. Пост машинасы Қорытынды Кіріспе
Тьюринг машинасының кейбір күйлері терминалды деп белгіленеді, бұл күйге өту жұмыстың аяқталмағанын, яғни алгоритмнің тоқтағанын білдіреді. Бір ғана ережеден тұратын Тьюринг машинасы анықталған (детерминирленген) Тьюринг машинасы деп аталады, ал егер екі немесе одан да көп командасы болатын «лента символы — күй» жұбы бар болса, мұндай Тьюринг машинасы анықталмаған (детерминирленбеген) деп аталады. Тьюринг машинасы Пост машинасын Марковтың нормальды алгоритмдері және компьютердегі кез – келген программаны (кірістік деректерді қандай да бір алгоритм бойынша шығыстық деректерге түрлендіретін) имитация жасай алады. Өз кезегінде түрлі абстрактілі орындаушылар Тьюринг машинасын имитациялай алатын абстрактты орындаушыларды Тьюринг бойынша толық деп атайды.Унарлық санау жүйесінде сандарды көбейтуге арналған Тьюринг машинасының мысалы. Машина келесі ережелер бойынша жұмыс істейді: Ережелер Ережелер q0*→q0R q4a→q4aR q01→q0R q4=→q4=R q0×→q1×R q41→q41R q11→q2aR q4*→q51R q21→q21L q5*→q2*L q2a→q2aL q6a→q61R q2=→q2=L q6×→q7×R q2×→q3×L q7a→q7aR q31 → q4aR q71→q2aR q3a→q3aL q7=→q8=L q3*→q6*R q8a→q81L q4×→q4×R q8×→q9H 1930-жылдардың ортасында Алонзо Чёрч пен Алан Тьюринг айтқан бұл тұжырым —есептелу теориясы, информатика, теориялық кибернетика және т.б. ғылым салалары үшін іргелі тұжырым. Алан Тьюринг мынандай жорамал айтты (оны Чёрч — Тьюринг тезисі дейді): «Кез келген алгоритм осы сөздің интуициялық мағынасында эквивалентті Тьюринг машинасымен көрсетіле алады». Жалпы түрде бұл Чёрч-Тьюрингтің тезисі былай дейді: «Кез келген интуициялық есептелетін функция жартылай есептелетін функция, яғни қандай да бір Тьюринг машинасымен есептеліне алады». Чёрч-Тьюрингтің физикалық тезисі: «Физикалық құрылғымен есептеліне алатын кез келген функция Тьюринг машинасымен де есептеліне алады». Тьюринг машинасы Пост машинасын Марковтың нормальды алгоритмдері және компьютердегі кез – келген программаны (кірістік деректерді қандай да бір алгоритм бойынша шығыстық деректерге түрлендіретін) имитаци жасай алады. Өз кезегінде түрлі абстрактілі орындаушылар Тьюринг машинасын имитациялай алады. Мұндай орындаушыларды Тьюринг бойынша толық деп атайды. Тьюринг машинасын имитациялайтын программалар бар (компьютерлерге арналған), бірақ оның имитациясы толық емес, өйткені Тьюринг машинасының лентасы екі жағынан да шексіз, ал компьютер жады шектеулі. Тьюринг машинасының моделі өзін кеңейтуге мүмкіндік береді. Ленталардың кез – келген саны бар және көпөлшемді ленталардан тұратын Тьюринг машиналарын қарастыруға болады. Олардың барлығы Тьюринг машинасы бойынша толық болады және кәдімгі Тьюринг машинасымен модельденеді. Тьюринг машинасының түрлері:Жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы 2 өлшемді тьюрниг машинсы( Муравей Ленгтона); Әмбебап Тьюринг машинасы; Тьюрингтің анықталмаған (детерминирленбеген) машинасы; Тьюрингтің ықтималдық машинасы; Тьюрингтің селкілдегі (Тьюринговская трясина). Жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы.Мұндай машинаны Тьюринг машинасына өзгерту оңай, ол үшін ұяшықтарды қайта нөмірлейді, күйлердің санын 2 еселейді, басқару құрылғысының қозғалысын реттейді. * белгісі Тьюринг машинасының сөздігінде сақталмайды, штрихталған зонада шекараға жеткендігін білдіреді, ал бастапқы күй жартылай шексіз лентада қай жерде тұрса, мұнда да сол жерде тұрады. Машина штрихталмаған зонада жұмыс істейді. Еер жұмыс кезінде ‘’ символы кезіксе, оқу-жазу бастиегі зона шекарасына жеткені. Лентаның «» сол жағындағылар бұл машинада қарастырылмайды. Жаңа Тьюринг машинасының бастапқы күйі бастапқы машинадағыдай жақта орналасады. Төменде жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы жұмысының схемасы берілген. Тьюрингтің ықтималдық машинасында лентадағы күйден және лентаның мәндерінен бірнеше күйге өтудің мүмкіндігі болады. Бұл машина өтудің нұсқасын қандай да бір ықтималдықпен таңдайды (монета лақтыру) және анықталмаған (недетерминированная) Тьюринг машинасына ұқсас. Тьюрингтің ықтималдық машинасында полиномды уақыт ішінде жұмысын аяқтап 1/3 аз қатемен жауап қайтаратын алгоритмдер класын BPP класы деп атайды. Есептелу теориясында орындаушы тьюринг-толық деп аталады, егер онда кез келген есептелетін функцияны жүзеге асыруға келсе. Мысалы программалау тілдерінің көпшілігі (Паскаль императивті тілі, , Haskell функциональды тілі, Prolog логикалық тілі) және грамматиканың жалпы түрі де тьюринг-толық. Ал ақырлы автоматтар, жай рекурсивті функциялар, контксті-бос грамматика, регулырлы грамматика тьюринг толық емес. Қорытынды Тьюринг машинасы бір ұяшықтан тұратын жадысы бар машина болғандықтан, оның әрекеттері қарапайым және мүмкін әрекеттердің саны шектеулі. Тьюринг машинасы қарапайым болса да, онда басқа машинада есептелінетіндердің барлығын есептеуге болады. Бірақ ол есептеулер қарапайым әрекеттердің тізбегі болу керек. Осы қасиетті толықтықдеп аталады. Тьюринг машинасының моделі өзін кеңейтуге мүмкіндік береді. Ленталардың кез – келген саны бар және көпөлшемді ленталардан тұратын Тьюринг машиналарын қарастыруға болады. Олардың барлығы Тьюринг машинасы бойынша толық болады және кәдімгі Тьюринг машинасымен модельденеді. жүктеу/скачать 25,15 Kb. Достарыңызбен бөлісу:
|