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

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

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

Тексерген: Рысжанова Айжан Сайлаухановна
Орындаған: Оралғазин Бекнар Болатқазыұлы
Жоспар
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-робот қағып алады. Сіз оны мойындайды ма?
Теориясын зерттеу, сіз жай ғана Тьюринг тест пайдалана алуыңыз мүмкін және ұтылған
қалдыруға болмайды. Сіз тиісті Уикипедия мақаланы оқыту басталады, содан кейін
мақала соңында келтірді әдебиеттер арқылы баруға болады:
Тьюринг Test

Тьюринг тест - компьютерлік сөздің адам мағынасында негізділігін тексеру
үшін бапта «Есептеу техникасы және барлау» (Есептеу техникасы мен
барлау) 1950 жылы Алан Тюринг ұсынған сынақ.

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

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

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

Тьюринг мағынасыз орнына тест ұсынды, оның пікірінше, мәселе
«машиналар ойлауға болады?» Толығырақ белгілі.
• Тьюринг компьютерлер, сайып келгенде, оның тест тапсырады
деп болжануда. Ол 2000 жылы 5-минуттық тест кезінде 1 млрд
бит (шамамен 119 МБ) жады бар компьютерлік жағдайларды
30% судьяларын алдауға қабілетті болады деп сенген. Бұл
болжау шындыққа жоқ. (Алайда, IBM PC 386 бірінші байқауы
Lebnera компьютерлік бағдарламалық қамтамасыз ету «PC
терапевт» 10 5 судьяларын адастыруы мүмкін, бірақ ол нәтиже
есептеуге болады, ал 1994 жылы бәсекелестік күрделі.)
Тьюринг, сондай-ақ, «ойлау машина» комбинациясы деп
болжаған Бұл оксюморон, қарастырылмайды, және
компьютерлік оқыту (ең заманауи ғалымдар келісесіз
қарағанда) қуатты құру маңызды рөл атқаратын болады.

Әзірге, бағдарламалардың бірде-бір дерлік тест тапсыру келді
емес. Мұндай Elisa (ELIZA) сияқты бағдарламалар, кейде
адамдар осындай AOLiza деп аталатын бейресми эксперимент
ретінде, адамның сөйлесіп деп санайды құрайды. Бірақ мұндай
«табыстары» Туринг тест тапсыру жоқ. Осы жылы Тьюринг
сынақ адам белсенді ол сөйлесіп кім анықтау тырысады, ал
бірінші, осы әңгімелер адамдар, ол бағдарламасымен дейді деп
ұйғаруға негіз жоқ еді.
Екіншіден, істерді құжаттандыру әдетте көптеген
әңгімелер және толымсыз мағынасыз АРО, сондай-ақ осы
чаттарға қараңыз. Үшіншіден, көптеген IRC
пайдаланушылар екінші немесе үшінші тілі ретінде
ағылшын пайдаланыңыз, мағынасыз жауап бағдарлама
бәлкім тілдік тосқауыл есептен болады. Төртіншіден,
көптеген пайдаланушылар Элиза туралы ештеңе және
ұқсас бағдарламаларды білмейді және бұл
бағдарламалар мүмкіндік беретін толық адамгершілікке
жатпайтын қателіктерін анықтай алмайды.

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

Тьюринг сынақ бағдарламасы үздік нәтиже Алиса
көрсетті (2000, 2001 және 2004 жылы) тест 3 есе жеңіп
алды.
Пайдаланған әдебиеттер

Жақыпбекова Г.Т Информатика оқыту
әдістемесі.-Шымкент, 2011,646
О. Камардинова «Есептеуіштер техника және
программалау» Алматы, 2010ж
А.Бочкин. Методика преподавания
информатики. Минск, Вышэйшая школа,
2011-430

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

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

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

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

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

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

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

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

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

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

Программалау тілдері туралы ақпарат

Пәндер