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



ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ физика-математика факультеті
Тақырыбы: Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі. Марковтың нормальды алгоритмы. Нормальдау принциптері және оның негіздемесі. Марковтың нормальды алгоритмі және Тьюринг машинасының композициясы.
Орындаған: Бабаева Ш. Қ
Тексерген: Рысжанова А. С.
Тобы: Т-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-жылдардың соңында енгізген. Марков алгоритмдері туралы сөз болғанда, "алгорифм" деп атау қабылданған. Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты мынада: әртүрлі математикалық есептердің алгоритмдік шешімділігі мәселесін шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма?- деген сұраққа жауап беру.
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.

Ақпарат
Қосымша
Email: info@stud.kz