ДС17о02-машина-Тьюринга (1238898)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonМашина ТьюрингаАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция2,12сентября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771УСТРОЙСТВО МАШИНЫ ТЬЮРИНГАконечныйалфавитсимволов a ={a0,a1,…an};2. конечныйсписок Q={q0,q1,…,qm} элементарныхсостояний;3. программа,составленнаяизкоманд Tij,имеющихвид: aiqj"a’iq’jM,где M - одиниз символовдвиженияL,R илиS.NB:результатработымашинызависитотеёначальногосостояния1.… l l l l l l a* a* a* a* a* a* l l l l l l l l l …q#2НАПИСАТЬ ПРОГРАММУ ДЛЯ МАШИНЫ ТЬЮРИНГА,ЗАПОЛНЯЮЩУЮ ЯЧЕЙКУ ЛЕНТЫ,НА КОТОРУЮУКАЗЫВАЕТ ГОЛОВКА В КОНЕЧНОМ СОСТОЯНИИ,• СИМВОЛОМ 1,ЕСЛИ НА ЛЕНТЕ ЗАДАНОПРАВИЛЬНОЕ СКОБОЧНОЕ ВЫРАЖЕНИЕ И•СИМВОЛОМ 0 – В ПРОТИВНОМ СЛУЧАЕ.НАЧАЛЬНОЕ ПОЛОЖЕНИЕ ГОЛОВКИ –УСТАНОВЛЕНА НА ПЕРВЫЙ (САМЫЙ ЛЕВЫЙ)СИМВОЛ СКОБОЧНОГО ВЫРАЖЕНИЯ.3#include <iostream>#include <string>using namespace std;ВАРИАНТstring str;ПРОГРАММЫ int main() {НА С++int s=0;cin >> str;for(int i=0;i<str.length();i++)if(str[i]=='(') s++; elseif(--s<0) break;cout << (s?"No":"Yes") << endl;return 0;}4Marvin Lee Minsky ( 1927-2016 )5)(lXX(lXq0q1q0q2q0LRLR)Х0Хq1q1qoq1LRSL01Xq2q2SSL6)(lXq0Xq1 L(q0 Rl q2 LXq0 RАЛФАВИТa = {(,),0,1,X}q1) q1 LХ qo R0- SХ q1 Lq2--0- S1- SXq2 LСостоянияq0 – исходноеипоиск )q1 – влеводопарнойq2 - влеводофиниша7ПРОГРАММА ДЛЯ МТ(q0 ® (q0R(q1 ® Xq0R)q0 ® Xq1Llq1 ® 0-SXq0 ® Xq0RXq2 ® Xq2Llq0 ® lq2L(q2 ® 0-SXq1 ® Xq1Llq2 ® 1-S8Блок-схемапрограммыдляМТ(,XXLl1l(RX)XX(Ll02 – Финишный 0 – Старт и 1 – Поискпоиск вправо влевопоиск влево9КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lll((((())())()))l()()lll…¢)0->X1L(0->(0RX0->X0Rl 0->02L¢)0->X1L(0->(0RX0->X0Rl 0->02L¢(1->X0RX1->X1Ll 1->n0S¢(1->X0RX1->X1Ll 1->n0S¢(2->n0SX2->X2Ll 2->y0S¢(2->n0SX2->X2Ll 2->y0S10КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lllXXXXXXXXXXXXXXl()()lll…¢)0->X1L(0->(0RX0->X0Rl 0->02L¢(1->X0RX1->X1Ll 1->n0S¢(2->0 0SX2->X2Ll 2->1 0S11КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lllXXXXXXXXXXXXXXl()()lll…¢)0->X1L(0->(0RX0->X0Rl 0->l 2L¢)4->X5L(4->(4RX4->X4Rl 4->06LX3->l 3Rl 3->l 4R¢(1->X0RX1->X1Ll 1->00S¢(5->X4RX5->X5Ll 5->n0S¢(2->00SX2->X2Ll 2->l 3R¢(6->n0SX6->X6Ll 6->y0S12РазновидностимашинТьюрингакдоказательствусуществованияалгоритмическинеразрешимыхзадач13ДвоичнаямашинаТьюрингаПустьалфавитa машиныТсостоитизk символов,тогдадляихкодированиямашинеТ*потребуетсяn= élog2(k+1)ù двоичныхразрядов.¢ Анализкортежейизn битпридвиженииТ*вправобудетприводитьксостоянию,соответствующемусчитываниюсимволаизa машинойТ.¢ Инаоборот:скаждымизk символовбудемассоциироватьнаборизn движенийвлевоТ*сзаписью0или1,которыесоставятдвоичныйкодсимвола,которыйзаписалабымашинаТ.¢14a ={0,1} : (=10(0->(0RX0->X0R)0->X1Ll 0->02L(1->X0RX1->X1Ll 1->n0S(2->n 0SX2->X2Ll 2->y0S)=011q0 ->1q01R0q01 ->0q0R1q01 ->1q0R0q0 ->0q00R0q00 ->0q000L0q000 ->0q2L1q00 ->1q001L0q001 ->1q1L//(//X//l//)X=11l=001q1 ->1q11L1q11 ->1q1L //X0q1 ->1q10L0q10 ->n-S//l1q10 ->1q101R//(0q101 ->1q0R0q2 ->0q20L0q20 ->y-S1q20 ->n-S1q2 ->1q21L1q21 ->1q2L//l//(//X15a ={0,1} :(=10(0->(0RX0->X0R)0->X1Ll 0->02L(1->X0RX1->X1Ll 1->n0S(2->n0SX2->X2Ll 2->y0S)=011q0 ->1q3R0q3 ->0q0R//(1q3 ->1q0R//X0q0 ->0q4R0q4 ->0q5L//l0q5 ->0q2L1q4 ->1q6L//)0q6 ->1q1LQ={q0 …q11}X=11l=001q1 ->1q7L1q7 ->1q1L//X0q1 ->1q8L0q8 ->n-S//l1q8 ->1q9R//(0q9 ->1q0R0q2 ->0q10L0q10 ->y-S1q10 ->n-S1q2 ->1q11L1q11 ->1q2L//l//(//X16МАШИНА ТЬЮРИНГА С ЛЕНТОЙ,БЕСКОНЕЧНОЙ ВОДНОМ НАПРАВЛЕНИИ.………17ФУНКЦИЯ ВЫЧИСЛИМАЯ ПО ТЬЮРИНГУf – функциявычислимаяпоТьюрингу,еслиеёзначениямогутбытьвычисленынекотороймашинойТьюринга,налентекоторойпервоначальнонезаписаноничего,кромепредставленияx вдвоичномкоде,аf(x) – этото,чтоналентебудетзаписановдвоичномкоде,когдамашинаостановится.18УниверсальнаяМашинаТьюрингаЕсли машина Т: sx ® Sf(x)sx…то существует машина U: DT,sx ® Sf(x)DTstqtОписаниемашины ТСимволТСостояниеТsx…Рабочая лента19ПроблемаостановаT:10®11R00®11RDT11®10L01®00SDT1 01TA1 10TA……$ ли анализатор А: для " T и " t выдает результат1 – в случае, если останов Т на наборе t произойдет,0 – в противном случае ?20АЛГОРИТМИЧЕСКИ НЕ РАЗРЕШИМАНесуществуеталгоритма(машиныТьюринга),• позволяющегоопределить поописанию• произвольногоалгоритма• иегоисходныхданных• останавливаетсяилиработаетбесконечно• этоталгоритм• наэтихданных.21ДоказательствоПредположениеобратного– существование«анализатора»¢ Шаг1.Навходанализируемоймашине– еёописание¢ Определениесамоприменимой машины¢ Шаг2.Композиция«анализатора»и«копира»¢ Шаг3.Модернизациякомпозициициклом¢ Шаг4.Парадокссвойствмодернизированнойкомпозиции¢22¢Предположимобратное,тогда:$ А:ДЛЯ НЕКОТОРОЙ T (ПРОИЗВОЛЬНОЙ!)ПО ДАННОМУ ЕЁ ОПИСАНИЮ DTИ ОПИСАНИЮ (ЛЮБОЙ!)ЛЕНТЫ tОПРЕДЕЛЯЕТ ПРОИЗОЙДЕТ ОСТАНОВ ИЛИ НЕТ.DT«НЕТ»St…А«ДА»S23ШАГ 1DTDT…q0«НЕТ»SА«ДА»SПользуясьобщностьюнабораданныхрассмотримчастныйслучай,когдаtºDT24СамоприменимаямашинаТьюрингадостигаетрезультирующегоостанованаданныхявляющихсякодомэтоймашины10®11R 00®11R 11®10L 01®00SСамоприменимая101101¢ 001101¢ 111010¢ 010000Самонеприменимая111010¢ 010000¢ 101101¢ 001101¢¢1011010011011110100100001110111000010110100110125ШАГ 2DT…q0«НЕТ»B«ДА»SS¢ МашинаBестькомпозициядвухмашин:СоздаеткопиюDT2.

МашинаА1.26ШАГ 3DT…q0«НЕТ»SB*«ДА»xLRx¢ МодифицируемкодмашиныВдобавиввсоставеёкомандцикл(длялюбоговозможногоx)¢ НазовемтакуюмашинуВ*27СВОЙСТВА В*DT…q0«НЕТ»SB*«ДА»xRLЕслианализаторуВ*предъявленоописание• само-применимойМТ,то онзацикливается,• еслинесамоприменимой,тооностанавливается.28ШАГ 4DB*…q0«НЕТ»SB*«ДА»xRxLВ*самоприменимая машина?⦁ Еслида,топопадаемвцикл⦁ Еслинет,топопадаемнаостановПротиворечияопровергаютисходноепредположение29.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций