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

Орындаған: Мавланов М

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

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

Аланның ата-анасы Чхатрапур қаласында қоныстады. Әкесі - Юлиус Мэтисон Тьюринг, шотландық ақсүйек тегінің өкілі, Империялық үкіметтік қызметінде жұмыс атқарды. Анасы - Сара Этель (қыз тегі - Стони), ирландық протестанттық ақсүйектер отбасынан шыққан. Сара бала күтіп жүргенде, жұбайлар нәрестелері Лондонда туулып тәрбиеленсін деген ниетпен Англияға қоныс аударды. Алан Тьюринг 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.

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

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

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

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

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

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

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

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

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

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

Пәндер