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

Лекция № 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]-[23]

Дата добавления: 2014-01-15