Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ физика-математика факультеті

Тақырыбы: Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері және оның негіздемесі. Марковтың нормальды алгоритмі және Тьюринг машинасының композициясы.

Орындаған: Бабаева Ш. Қ

Тексерген: Рысжанова А. С.

Тобы: Т-313

Жоспар:

I. Кіріспе

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

1. Тьюринг машинасының сыртқы және ішкі алфавиттері

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

3. Командалары

4. Графиктері

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

IV. Қорытынды

Алан Мэтисон Тьюринг

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

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

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

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

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

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

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

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

Жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы.

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

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

Машина штрихталмаған зонада жұмыс істейді. Еер жұмыс кезінде ‘*’ символы кезіксе, оқу-жазу бастиегі зона шекарасына жеткені. Лентаның «*» сол жағындағылар бұл машинада қарастырылмайды. Жаңа Тьюринг машинасының бастапқы күйі бастапқы машинадағыдай жақта орналасады.

Төменде жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы жұмысының схемасы берілген:

Тьюринг машинасы келесі ережелер бойынша жұмыс істейді:

Ережелер

q0*→q0R

q01→q0R

q0×→q1×R

q11→q2aR

q21→q21L

q2a→q2aL

q2=→q2=L

q2×→q3×L

q31 → q4aR

q3a→q3aL

q3*→q6*R

q4×→q4×R

Ережелер

q4a→q4aR

q4=→q4=R

q41→q41R

q4*→q51R

q5*→q2*L

q6a→q61R

q6×→q7×R

q7a→q7aR

q71→q2aR

q7=→q8=L

q8a→q81L

q8×→q9H

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

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

A= {a˳, a₁, . . a᷿}

a˳ - ұяшықтың бос символы

Ішкі алфавит:

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

Пост машинасы: i-2, i-1, i, i+1, i+2

Пост абстракты машинасы жазатын немесе оқитын түбіртек арқылы не ен жазылып, не ен оқылатын жеке секцияларға (ұяшықтарға) бөлінген ақырсыз таспа болып табылады.

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

Абстракты автомат командалары әдетте келесі әрекеттердің бірінен тұрады:

Команда

Түбіртектің оңға қозғалуы →m

Түбіртектің солға қозғалуы ←m

М енін жазу m

С енін өшіру m

Басқаруды беру m1; m2

Тоқтау стоп n

Таспаның күйі

Командадан кейін

Марковтың нормальды алгоритмдері.

Марковтың нормаль алгоритмі (МНА) - алгоритм ұғымының формалді анықтамасын берудің стандарты тəсілдерінің бірі (Тьюринг машинасы сияқты) . Бұл ұғымды көрнекті кеңес математигі А. А. Марков(1903-1979жж. ) 1940-жылдардың соңында енгізген. Марков алгоритмдері туралы сөз болғанда, "алгорифм" деп атау қабылданған. Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты мынада: әртүрлі математикалық есептердің алгоритмдік шешімділігі мәселесін шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма?- деген сұраққа жауап беру.

Ұқсас жұмыстар

Тьюринг машинасы. Тьюринг тезисі жә не оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері жә не оның негіздемесі. Марковтың нормальды алгоритмі жә не Тьюринг машинасының композициясы

Тьюринг тезисі және оның негіздемесі

Тьюринг машинасы. Алан Мэтисон Тьюринг

Тьюринг тезисі және оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері және оның негіздемесі. Марковтың нормальды алгоритмі және Тьюринг машинасының композициясы

Марковтың нормальды алгоритмі

Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері және оның негіздемесі. Марковтың нормальды алгоритмі және Тьюринг машинасының композициясы

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

ТЬЮРИНГ МАШИНАСЫ жә не Марковтың нормальді алгоритмы

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

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

Пәндер