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

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

Тексерген: Рысжанова Айжан Сайлаухановна

Орындаған: Оралғазин Бекнар Болатқазыұлы

Жоспар

1. Кіріспе

2. Негізгі Бөлім

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

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

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

В) Нормальдау принциптері және оның негіздемесі.

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

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

Кіріспе

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

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

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

Негізгі бөлім Сондықтан Тьюринг машинасы - математикалық абстракция, адам ақыл-сыбыс: ол табиғатта жоқ. Немесе бар? Бірден қалай тірі жасуша, ақыл келеді. Кем дегенде екі мысал. РНК полимеразы -, ДНК ақпарат таспа машиналар Тьюринга түрін ақпаратты оқып қатты ұйымдастырды ферментінің көмегімен ұяшықта белоктар өндіру үшін 1. . Мұнда, алайда, таспа өзі жасушаларының ешқандай қайта жазу бар, бірақ басқа тәсілмен процесс өте ұқсас: ДНҚ-ның РНК-полимераза және ол РНҚ тұтамын синтездейді, ал ол, бір бағытта жылжиды сидит - ДНК ұқсас нуклеин қышқылы. Дайын РНК протеин өндіруге ұялы органеллалар ақпаратты асырады ферментінің ажыратылған. Оның жөндеу - Тіпті көп ұқсас ДНК Тьюринга машина қатесі түзету процесіне 2. . Мұнда, басқа да белоктар ДНҚ полимераза, таспа бойымен ДНҚ жылжытылады және оның екі жартыға делінген (белгілі, геномдық ДНҚ, бірдей ақпаратты асыратын, екі өзара жіп тұрады) . Таймнан ақпарат сәйкес келмесе, ДНҚ-полимераза моделіне және басқа үшін «құқығын» ретінде олардың бірін алады. Бұл ұқсастығы жаңа емес, сондай-ақ мақала «молекулалық компьютерлер» сипаттайды:

Молекулалық компьютерлік Тіпті Биомолекулярных есептеулер немесе молекулярлық компьютерлер немесе ДНҚ немесе РНҚ есептеу - бұл терминдердің барлық осындай молекулалық генетика және компьютерлік ғылым ретінде түрлі ғылымдардың тоғысында пайда. Биомолекулярных Есептеу - әр түрлі техникада, бір жолмен немесе ДНК немесе РНК байланысты басқа арналған ұжымдық атауы болып табылады. ДНК есептеу деректер бірлік және нөл түрінде емес ұсынылған, бірақ молекулалық құрылымын түрінде, ДНК спираль негізінде құрылады болса. оқу, көшіру және деректерді басқару үшін бағдарламалық қамтамасыз рөлі ерекше ферменттер орындайды.

Бүкіл биологиялық ақпаратты сақтау жүйесін, және, демек, ДНК компьютерлер негізі сутегі атомдарының қабілеті азоттық қосылыстар (аденин, тимин, цитозин және гуанин) енгізілген, белгілі бір жағдайларда, қосылған емес кеден жұбын қалыптастыру, бір-біріне тартылады. Екінші жағынан, бұл заттар ковалентті деп аталатын нуклеотидтер қалыптастыру, қант молекуласының (дезоксирибоза) тіркесімдері мен фосфаттар байланыстыруға болады. Нуклеотидтердің, өз кезегінде, оңай ондаған негіздер миллион полимерлер ұзындығы қалыптастырады. Осы supermolecule фосфаты және дезоксирибоза ақпаратты кодтау үшін құрылымдарды (олар тізбекте кезекпен), және азот қосылыстары қолдау рөл атқарады. Молекуласы бағыттарын алынған: фосфат топтары мен дезоксирибоза ұштарында басталады. ДНК жіп ұзын бұрымды қысқа деп аталады - олигонуклеотиды. Деп аталатын қосымша Уотсон - алақайлап Әрбір ДНК молекуласы басқа ДНҚ сәйкес келеді. Ол бастапқы молекуласының қарағанда қарама-қарсы бағытта бар.

Нәтижесінде, гуанин үшін тимин және цитозин тарту аденин ұялы молайту кезінде ДНК еселеу мүмкіндігін қамтамасыз ететін, белгілі қос спираль алынған. полимераздық - екі есе мақсаты арнайы ақуыз ферментінің көмегімен қол жеткізіледі. Синтез ДНҚ оның толықтырулар бөлігін қоса берілген кезде ғана басталады, Бұл сипат кеңінен молекулярлық биология және молекулалық есептеу қолданылады. Мәні полимеразы жылы - машиналар Тьюринга іске асыру екі таспалар және бағдарламаланатын қашықтан басқару тұрады. Бақылау, бір таспа деректерді оқиды белгілі бір алгоритм бойынша оларды өңдейді, және басқа таспа жазады. Полимеразды-ақ дәйекті бір таспа (ДНҚ) шикізат деректерді оқиды және олардың негізінде есептеулер (Уотсон қосу - алақайлап) нәтижелері бар таспаны жасайды. Кішкентай фантастикалық болашағы тек біздің қызығушылығымен жылытылған. Сонымен қатар, біз әлі Тьюринг машинасы қатысты бәрін түсіндік жоқ. Естеріңізде болса, Уикипедия мақала бұл мемлекеттік машинаның кеңейту деп аталды. Бұл мемлекеттік машина қандай? Ол үшін, бақытымызға, сілтемені берілген. Оған жандандыру, біз білеміз, бұл:

Мемлекеттік аппарат Мемлекеттік (алгоритмдер теориясы) машина - объектінің мәртебесі өзгерту жолдарын сипаттауға мүмкіндік береді математикалық қоймаларынан, оның ағымдағы жағдайына байланысты және кіріс деректер, мүмкін мемлекеттердің жалпы саны ақырлы екенін көрсетті. Мемлекеттік аппарат дерексіз машиналары арнайы жағдай. Мемлекеттік аппарат, оның мінез-бір немесе бірнеше нұсқалары кейбір сатысында бар ма байланысты, белгілі немесе анықталмаған болуы мүмкін. Ресми, мемлекеттік машина бестігі ретінде анықталады М = (K, \ Sigma, \ пи, с, F) K қайда - тек рұқсат етілген бастапқы қалпы, F \ подмножество K - рұқсат етілген F = Ø, және F = K, Σ бар соңғы мемлекеттердің жиынтығы, - сызықты қалыптасқан оның жарамды енгізу әліпбиі, ақырлы автоматтың мемлекеттердің орнату, К \ с машина оқитын, \ Pi: К \ есе \ Sigma \ rightarrow К - өтпелі функция. автоматты машина енгізу жолдың бір таңбаны оқып, мемлекеттік с басталады. Машинаның символы болып саналады өтпелі функциясы сәйкес, К жаңа мемлекет аударылады. ол мемлекет Ф бірін толғанға дейін процесі жалғасуда

Ақырлы мемлекеттік машиналар кеңінен осындай парсерін және олардың арасындағы нысан мемлекеттер мен Шарлау саны салыстырмалы түрде аз болып табылады, басқа жағдайларда, өйткені іс жүзінде қолданылады.

Дерексіз машина Дерексіз машина (алгоритмдер теориясы) - математикалық абстракция бір кіріс ұясы бар дискретті құрылғының моделі, бір шығыс және бірнеше ықтимал бірдей күйіне әр уақытта. осы құрылғыға кіріс ол (жалпы алғанда) шығыс рәміздер түрлі тілдік өндіреді, тіл кодын алады. Ресми, дерексіз машина бестігі ретінде анықталады ~ A = (S, X, Y, \ Delta, \ Lambda) Қайда S - автоматтың мемлекеттердің ақырғы жиынтығы, X, Y - соңғы кіріс және шығыс алфавиттер, тиісінше, сызықты қалыптасқан, оның оқу және тапанша, \ Delta берілген: S \ есе X \ rightarrow S - өтпелі функциясын, \ лямбда: S \ есе X \ rightarrow Y - шығу функциясы. Құрметті бастапқы мемлекетпен Abstract Machine бастапқы автоматқа деп аталады. Осылайша бағзы машина бастапқы автоматтары отбасын анықтайды S жылы ~ (s_i, A), s_i \ Дерексіз машиналар енгізілді жіктеу сипаттарын анықтау үшін. Аннотация машиналар жеке үлгісі ретінде, және ірі Тьюринг машиналары компоненті, өңдеу беру автоматтары, ақырғы автомат және басқа да деректер түрлендіргіштер ретінде дискретті модельдер іргелі класс құрайды. Дерексіз машиналары моделі кеңінен, тану дискретті модельдерін құру генерациялау және таңбалардың ретін айырбастау үшін негіз ретінде пайдаланылады.

Алан Тьюринг Тьюринг, Алан Mathison (23 маусым 1912 - 7 маусым, 1954) - ағылшын математигі, Логиком, шифрлаушы, Тьюринг машиналары өнертапқыш. Тым Funny, бұл дұрыс емес Компьютерлер болған жоқ, және Windows жылы (біз әрі қарай ол: «Ажырату мәселесіне» бойынша жұмыс деп айтып беретін, Тьюринг машинасы туралы мәтіннен бөлек, мен:? Сол мақалада Тьюринге жұмыстарының туралы көбірек мәселе қазірдің өзінде өзіңіз туралы мәлімдеді. ) ; Тьюринг Екінші дүниежүзілік соғыс кезінде коды «Enigma» Жарылған және осылайша Ұлыбритания сақталған қалай ерлік әңгіме; ол жасанды интеллект теориясы негізін қалаушы, сондай-ақ атақты Тьюринг тест ескертпені фактісі. Енді сынақ жиі тең фантастикалық әңгіме ретінде пайдаланылмайды, бірақ автомобильде адам проблемасы әрқашан классикалық, сондай-ақ Айзек Азимов және Станислав дықтарды романдары болады. Оның ескірген қарамастан, Тьюринг сынақ Интернетте байланыс қазіргі әлемде күтпеген беті. Ол қандай болды анықтау үшін - мысалы, сіз «бот» және міндеті болып табылады біреуі екі пайдаланушылар ICQ, арасындағы үнқатысуды мәтінін таба аласыз. Немесе сіз бейтаныс пайдаланушыға мүмкін, ICQ-робот қағып алады. Сіз оны мойындайды ма? Теориясын зерттеу, сіз жай ғана Тьюринг тест пайдалана алуыңыз мүмкін және ұтылған қалдыруға болмайды. Сіз тиісті Уикипедия мақаланы оқыту басталады, содан кейін мақала соңында келтірді әдебиеттер арқылы баруға болады: