Тьюринг және пост машиналары

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ  ДЕНСАУЛЫҚ  САҚТАУ МЕН ӘЛЕУМЕТТІК ДАМУ МИНИСТРЛІГІ

ОҢТҮСТІК ҚАЗАҚСТАН МЕМЛЕКЕТТІК ФАРМАЦЕВТИКА АКАДЕМИЯСЫ

 

Медициналық биофизика,информатика және математика кафедрасы

 

Реферат

Тақырыбы: Тьюринг және пост машиналары

 

 

 

 

 

 

 

 

 

Орындаған: Шырынхан А

Тобы: 101 «А» ФК

Қабылдаған: Байдилдаева Акмарал

 

 

 

 

 

 

Шымкент – 2014 жыл

 

Жоспар

Кіріспе

Негізгі бөлім

1. Тьюиринг машинасы

2. Тьюиринг машинасының  жұмысының сипаттамасы

3. Пост машинасы

Қорытынды

Пайдаланылған әдебиеттер

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Кіріспе

Тьюринг машинасының кейбір күйлері терминалды деп белгіленеді, бұл күйге өту жұмыстың аяқталмағанын, яғни алгоритмнің тоқтағанын білдіреді. Бір ғана ережеден тұратын Тьюринг машинасы анықталған (детерминирленген) Тьюринг машинасы деп аталады, ал егер екі немесе одан да көп командасы болатын «лента символы — күй» жұбы бар болса, мұндай Тьюринг машинасы анықталмаған (детерминирленбеген) деп аталады. Тьюринг машинасы Пост машинасын Марковтың нормальды алгоритмдері және компьютердегі кез – келген программаны (кірістік деректерді қандай да бір алгоритм бойынша шығыстық деректерге түрлендіретін) имитация жасай алады. Өз кезегінде түрлі абстрактілі орындаушылар Тьюринг машинасын имитациялай алады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тьюринг машиналары

Чёрч- Тьюринг тезисі

Есептеулер модельдерінің үш түрі бар:

1) Тьюринг машинасы

2) Лямбда есептеу (рекурсия)

3) Комбинаторлық логика

Тьюринг машинасы– бұл абстрактты орындаушы (абстрактты есептеу машинасы), 1936 жылы алгоритм ұғымын формальдау үшін Алан Тьюринг ұсынды. абстрактты орындаушы (абстрактты есептеу машинасы). Тьюринг машинасы – ақырлы автоматтың кеңейтілген түрі, басқа орындаушыларды қадамдап есептеу процесін жүзеге асырып имитациялай алады (өту ережелерін беру арқылы қарапайым), қадамдар аса қарапайым.

Тьюринг машинасының құрамы:

1 ) екі жағы шексіз лентадан (олар ұяшыққа бөлінген)

2) басқару құралы,осы күйлердің біреуінде болады

3) күйлер жиыны. Күйлердің саны шектеулі және нақты беріледі

Басқару құралы лентада солға, оңға жылжи алады, лентаға қандай да бір ақырлы алфавиттің символдарын жазады не оқиды. Бос символ болады, ол лентаның кірістік деректер жазылмаған,қалған ұяшықтарына жазылады.

Басқару құралы өту ережесі бойынша жұмыс істейді. Өту ережесі Тьюринг машинасында жүзеге асатын алгоритм. Өтудің әрбір ережесі Тьюринг машинасына ағымдағы күймен ағымдағы ұяшықтағы символға байланысты, осы клеткаға жаңа символ жазуды, жаңа күйге өтуге немесе бір клеткаға оңға немесе солға жылжуға бұйрық береді.

Тьюринг машинасының кейбір күйлері терминалды деп белгіленеді, бұл күйге өту жұмыстың аяқталмағанын, яғни алгоритмнің тоқтағанын білдіреді. Бір ғана ережеден тұратын Тьюринг машинасы анықталған (детерминирленген) Тьюринг машинасы деп аталады, ал егер екі немесе одан да көп командасы болатын «лента символы — күй» жұбы бар болса, мұндай Тьюринг машинасы анықталмаған (детерминирленбеген) деп аталады.

Тьюринг машинасын анықтау үшін мыналар көрсетіледі:

Сыртқы алфавит

A= { }    - ұяшықтың бос символы

Ішкі күйлердің алфавитінемесе оны ішкі алфавит деп атаймыз.

 

Q = {  } , мұндағы  - тоқтаудың күйі. Осыған келгенде машина жұмысын тоқтатады.  - бастапқы күй, машина жұмысын бастайды.

Программа(функционалды схема), ол – команда деп аталатын өрнектердің жиынтығы. Мынандай әрбір жұп үшін ( )  тек бір ғана команда болады.

Ереженің жалпы түрі: 

 

- жаңакүй, олкейде  қалуымүмкін.

-  -ныңорнынажазылатынжаңасимвол

Тьюрингмашинасынсипаттауүшінбастапқыжәнесоңғыкүйді( ), лентадағыбастапқыорналасудыжәнебасқаруқұрылғысыныңбастиегініңорнынкөрсетукерек.

Тьюринг бойыншатолықтық. Тьюрингмашинасында басқамашиналарды (Постмашинасын, Марковтың нормальды алгоритмдерін) және кірістікдеректерді қандайда біралгоритм арқылышығыстық деректерге түрлендіретін компьютердіңпрограммаларын имитациялауғаболады. Олсызықты жадыбар қарапайымесептеу машинасы,формальды ережелербойынша кірістікдеректерді элементар(яғни әрәрекет тек жадтың бірұяшығын ғанаөзгертеді және әрекеттер саны ақырлы) әрекеттертізбегі арқылы түрлендіреді.

Тьюринг машинасы бір ұяшықтан тұратын жадысы бар машина болғандықтан, оның әрекеттері қарапайым және мүмкін әрекеттердің саны шектеулі. Тьюринг машинасы қарапайым болса да, онда басқа машинада есептелінетіндердің барлығын есептеуге болады. Бірақ ол есептеулер қарапайым әрекеттердің тізбегі болу керек. Осы қасиетті толықтықдеп аталады.

Тьюринг машинасын имитациялай алатын абстрактты орындаушыларды Тьюринг бойынша толық деп атайды.

Унарлық санау жүйесінде сандарды көбейтуге арналған Тьюринг машинасының мысалы. Машина келесі ережелер бойынша жұмыс істейді:

 

Ережелер Ережелер

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 логикалық тілі) және грамматиканың жалпы түрі де тьюринг-толық. Ал ақырлы автоматтар, жай рекурсивті функциялар, контксті-бос грамматика, регулырлы грамматика тьюринг толық емес.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Қорытынды

Тьюринг машинасы бір ұяшықтан тұратын жадысы бар машина болғандықтан, оның әрекеттері қарапайым және мүмкін әрекеттердің саны шектеулі. Тьюринг машинасы қарапайым болса да, онда басқа машинада есептелінетіндердің барлығын есептеуге болады. Бірақ ол есептеулер қарапайым әрекеттердің тізбегі болу керек. Осы қасиетті толықтықдеп аталады. Тьюринг машинасының моделі өзін кеңейтуге мүмкіндік береді. Ленталардың кез – келген саны бар және көпөлшемді ленталардан тұратын Тьюринг машиналарын қарастыруға болады. Олардың барлығы Тьюринг машинасы бойынша толық болады және кәдімгі Тьюринг машинасымен модельденеді.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пайдаланылған әдебиеттер тізімі

        1. Лихтарников Л.М., Сукачева Т. Г. Математическая логика. - Санкт – Петербург, 1998 г.

2. Дискретная математика. Юнаты 1, 2 Дистанционное образование, Москва, 2001 г.

3. Фор Р., Кофман А., Дени – Папен М. Современная математика. М.: Издательство «Мир», 1996 г.

4. Столяр А. А., Лельчук М. П. Математика. Минск: Педвуздың бастауыш класс мұғалімдерін дайындау факультеттеріне арналған «Жоғарғы мектеп», 1975 ж.

5. Емеличев В. А., Мельников О. И., Сарванов В. И., Тыжкеевич Ф. И. Лекции по теории графов. М.: «Наука» главная редакция физико – математической литературы, 1990 г.