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

Презентация қосу

Орындаған: Мавланов М
Тьюринг машинасы. Тьюринг тезисі
және оның негіздемесі. Марковтың
нормальды алгоритмы. Нормальдау
принциптері және оның негіздемесі.
Марковтың нормальды алгоритмі және
Тьюринг машинасының композициясы.
Алан Мэтисон Тьюринг
Аланның ата-анасы Чхатрапур қаласында қоныстады. Әкесі — Юлиус Мэтисон
Тьюринг , шотландық ақсүйек тегінің өкілі, Империялы қ үкіметтік қызметінде
жұмыс атқарды. Анасы — Сара Этель (қыз тегі - Стони), ирланды қ протестантты қ
ақсүйектер отбасынан шыққан. Сара бала күтіп ж үргенде, ж ұбайлар н әрестелері
Лондонда туулып тәрбиеленсін деген ниетпен Англия ға қоныс аударды. Алан
Тьюринг 1912 жылы маусымның 23-ші жұлдызында дүниеге келді. Отбасында
Аланнан басқа Джон есімді ағасы болды. Әкесінің үкіметтік қызметі жал ғаса
берді, сол себепті жұбайларға жиі Гастинг пен Индия арасында саяхаттау ға тура
келді. Ұлдары қызметтен босатылған армиялы қ ж ұпты ң т әрбиесінде қалатын.
Дарындылықтың белгілері Аланның бойынан ерте бай қала бастады.
Алты жасында Алан Тьюринг киелі Михаил атында ғы мектепті ң ал ғаш
табалдырығын аттады.
Мектеп директоры Аланның зеректілігін бірден атап өтті. 1926 жылы 13 жасар
Алан білім беруімен атақты иемденген Шерборн жеке мектебіне ауысты. Оны ң
мектептегі алғашқы күні 1926 жылғы көтеріліске сәйкес келіп қалды.
Нәтижесінде, Тьюринг Саутгемптон мен Шерборн арасында ғы 100 км-ге жуы қ
қашықтықты велосипедпен өтіп, жол-жөнекей қонақ үйде т үнеді
Тьюринг машинасы – алгоритмдік
процесті жүзеге асыратын абстрактылы
орындаушы
Бұл физикалық машина емес,
математикалық объект болып табылады

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

2) Әр түрлі Тьюринг машиналары өздерінің
бағдарламаларымен ерекшеленеді
Әрбір алгоритм үшін өзінің Тьюринг
машинасы құрылады, дәлірек айтсақ өзінің
бағдарламасы құрылады
басында ілентаға сөзі
түрінде бастапқы
берілгендер жиынтығы
берілед
Будем говорить, Бос емес сөзі А\{a0} алфавитінде
машинада стандартты күйде қабылданады деп
ұғамыз, егер:
- Ол лентаның тізбектес ұяшыұтарында берілсе;
- Қалған барлық ұяшықтар бос болса;
- Машина сөзі жазылған шеткі оң жақтағы
ұяшықтарды бейнелейді
Анықтама. Алгоритм (Тьюринг бойынша) – қойылған есепті шешуге
келтірілетін Тьюринг машинасына құрылған программа.
Тьюринг машинасы мен тезисі болашақта да қолданылады, себебі кез
келген проблема шешілмейді деп айтуға болмайды, шешілмейтін есеп
болмауы керек, оны қандай да бір шешілетін түрге келтіру керек, соған
орайластырылған алгоритм құрастыру керек.
Машинаның белгілі бір процесті орындауының өзі алгоритмдік процесс
болып табылады. Сондықтан алгоритмге қойылатын талаптар мен
қасиеттер оны орындайтын машинаға да қойылады:
1) Машинаның жұмысы дискретті, бірінен кейін бірі орындалатын жеке –
жеке командалармен орындалуы керек.
2) Әрекеттер детерминделген , яғни қадамдар қатаң реттелген , ал
олардың нәтижесі алдыңғы қадамда алынған нәтижелермен тікелей
байланысты болуы керек.
3) Жұмыс алдында алғашқы берілгендер алгоритмнің анықталу облысынан
алынуы керек.
4) Саны санаулы қадамдарды орындаудан соң нәтиже алынуы керек.
5) Машина универсалды , жан – жақты болуы керек, оның көмегімен кез –
келген алгоритмді орындайтын болуы керек.
Сипатталған машинаның құрылғылары немесе структурасы қарапайым
болса және орындалатын қадамдар элементарлы болса, алгоритмнің
орындалуы машинаның жұмыс істеуі деп есептеуге болады .
Машинаның орындайтын қадамдары элементарлы болуы үшін белгілі бір
алфавит арқылы ақпаратты алмастыру керек. Сондықтан алгоритм – кез–
келген ақырлы алфавиттен берілгендерді немесе ақпаратты алмастыру
Санақтың ондық жүйесінде п санына бірді қосу
алгоритмі.

п санының ондық жазбасы берілсін (яғни, п натурал
санының ондық санның жүйесіндегі көрінісі); п+1
санының ондық жазбасын алу қажет. ТМ сыртқы
әріппесі 0,1,2,3,4,5,6,7,8,9 он цифрдан және бос орын
таңбаларынан тұру керектігі анық. Бұл цифрлар бір
ұяшыққа жазылады (бірінен соң бірі, бос орын
қалдырмай). Машинаның және екі ішкі күйінің болуы
жеткілікті көрінеді. Бастапқы кезде түбіртек санның
бір цифрының үстінде тұрсын делік, ал машина
күйінде тұрсын. Онда есеп екі кезеңде шешілуі мүмкін:
түбіртектің сан бірліктерінің цифрына ( іш күйінде)
қарай қозғалысы және ол цифрды бірге үлкенмен
ауыстыру (1-ді келесі разрядқа көшіру есебінен, іш
күйде, егер ол 9 болса). Сәйкес ТМ сүлбесі мына түрге
ие болуы мүмкін.
Тьюринг машиналарының композициясы

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

а) әртүрлі таңбалар әртүрлі кодтық
топтармен алмастырылуы қажет, бірақ бір
таңба қай жерде кездескеніне қарамай, бір
ғана кодтық топпен жаппай ауыстырылуы
қажет;

б) кодтық жазба жолдары жеке кодтық
топтарға бірмәнді бөлшектенуге тиіс

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

Ортақ сырт әріппесі бар және сәйкес , іш күйлері бар және Т2
Тьюринг машиналары берілген болсын. Композиция немесе Т1,Т2
машиналарының көбейтіндісі деп сол сырт әріппесі, іш күйлерінің
жиынтығы және Т1,Т2 машиналары программаларының біртіндеп
орындалуына парапар программасы бар Т машинасын айтамыз: Т=
Т1* Т2.

Дәрежеге шығару амалы да осылай анықталады: Т машинасының
n - дәрежесі деп көбейткіші бар көбейтіндіні айтады.

Итерация амалы бір машинаға ғана қолданымды және былай
анықталады: T1 машинасының бірнеше қорытынды күйлері
болсын. Оның - қорытынды күйін таңдап, оны машина сүлбесінде
оның бастапқы қалпымен теңдестіреміз. Алынған Т машинасы Т1
машинасының итерация нәтижесі болып табылады: Т= T1.
Әртүрлі машиналар құрылымын
салыстыру және олардың күрделілігін
бағалау үшін сәйкес машиналар
күрделігінің өлшемін алу қажет. К.
Шеннон ондай өлшем ретінде сырт
әріппе таңбалары санының іш күйлер
санына көбейтіндісін қарастыруды
ұсынды. Күрделілігі тым аз әмбебап
Тьюринг машинасын құрастыру есебі
үлкен қызығушылық тудырып отыр.
Қолданылған ақпарат
қөздері
Джон Хопкрофт, Раджив Мотвани, Джеффри
Ульман. Глава 8. Введение в теорию машин
Тьюринга // Введение в теорию автоматов, языков
и вычислений = Introduction to Automata Theory,
Languages, and Computation. — М.: «Вильямс»,
2002. — С. 528. — ISBN 0-201-44124-1.
Карпов Ю. Г. Теория автоматов. —
ISBN 5-318-00537-3
https://kk.wikipedia.org/wiki/Алан_Тьюринг
www.pdf-spot.com/ebook/тьюр/тьюринг-машинасы-
туралы
О. Камардинов «Информатика», Алматы,2006

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

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

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

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

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

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

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

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

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

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

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

Пәндер