ДС18о02-машина-Тьюринга (1238917)
Текст из файла
Carnegie MellonМашина ТьюрингаАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 2, 14 сентября, 2018Лектор:Дмитрий Северов, кафедра информатики 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++;else if(--s<0) break;cout << (s?"No":"Yes") << endl;return 0;}НА С++4Marvin Lee Minsky ( 1927-2016 )5)(lXX(lXq0q1q0q2q0LRLR)X0Xq1q1qoq1LRSLq2--0 - S1 - SX q2 L6)(lXX(lXq0q1q0q2q0LRLRАЛФАВИТa = {(,),0,1,X})X0Xq1q1qoq1LRSLq2--0 - S1 - SX q2 LСостоянияq0 – от начала вправо до )q1 – влево до парной (q2 - влево до конца7ПРОГРАММА ДЛЯ МТ(q0 ® (q0R(q1 ® Xq0R)q0 ® Xq1Llq1 ® 0-SXq0 ® Xq0RXq2 ® Xq2Ll q 0 ® l q 2L(q2 ® 0-SXq1 ® Xq1Llq2 ® 1-S8Блок-схема программы для МТXXl q0R )q2Ll(,X(X1от концавлеводо началаот начала и (вправодо )X(q1Ll0от (влево допарной (9КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lll((((())())()))l()()lll…¢) 0 -> X 1 L( 0 -> ( 0 RX 0 -> X 0 Rl 0 -> 0 2 L¢) 0 -> X 1 L( 0 -> ( 0 RX 0 -> X 0 Rl 0 -> 0 2 L¢( 1 -> X 0 RX 1 -> X 1 Ll 1 -> n 0 S¢( 1 -> X 0 RX 1 -> X 1 Ll 1 -> n 0 S¢( 2 -> n 0 SX 2 -> X 2 Ll 2 -> y 0 S¢( 2 -> n 0 SX 2 -> X 2 Ll 2 -> y 0 S10КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lllXXXXXXXXXXXXXXl()()lll…¢) 0 -> X 1 L( 0 -> ( 0 RX 0 -> X 0 Rl 0 -> 0 2 L¢( 1 -> X 0 RX 1 -> X 1 Ll 1 -> n 0 S¢( 2 -> 0 0 SX 2 -> X 2 Ll 2 -> 1 0 S11Разновидности машинТьюрингак доказательству существованияалгоритмически неразрешимых задач12КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lllXXXXXXXXXXXXXXl()()lll…¢) 0 -> X 1 L( 0 -> ( 0 RX 0 -> X 0 Rl 0 -> l 2 L¢) 4 -> X 5 L( 4 -> ( 4 RX 4 -> X 4 Rl 4 -> 0 6 LX 3 -> l 3 Rl 3 -> l 4 R¢( 1 -> X 0 RX 1 -> X 1 Ll 1 -> 0 0 S¢( 5 -> X 4 RX 5 -> X 5 Ll 5 -> n 0 S¢( 2 -> 0 0 SX 2 -> X 2 Ll 2 -> l 3 R¢( 6 -> n 0 SX 6 -> X 6 Ll 6 -> y 0 S13Двоичная машина Тьюринга¢¢¢Пусть алфавит a машины Т состоит из k символов,тогда для их кодирования машине Т* потребуется n =élog2(k+1)ù двоичных разрядов.Анализ кортежей из n бит при движении Т* вправобудет приводить к состоянию, соответствующемусчитыванию символа из a машиной Т.И наоборот: с каждым из k символов будемассоциировать набор из n движений влево Т* сзаписью 0 или 1, которые составят двоичный кодсимвола, который записала бы машина Т.14a = {0,1} : ( =10( 0 -> ( 0 RX 0 -> X 0 R) 0 -> X 1 Ll 0 -> 0 2 L( 1 -> X 0 RX 1 -> X 1 Ll 1 -> n 0 S( 2 -> n 0 SX 2 -> X 2 Ll 2 -> y 0 S)=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 -> ( 0 RX 0 -> X 0 R) 0 -> X 1 Ll 0 -> 0 2 L( 1 -> X 0 RX 1 -> X 1 Ll 1 -> n 0 S( 2 -> n 0 SX 2 -> X 2 Ll 2 -> y 0 S1q0 -> 1q3R0q3 -> 0q0R1q3 -> 1q0R0q0 -> 0q4R0q4 -> 0q5L0q5 -> 0q2L1q4 -> 1q6L0q6 -> 1q1L)=01//(//X//l//)Q = {q0 … q11}X=111q1 -> 1q7L1q7 -> 1q1L0q1 -> 1q8L0q8 -> n-S1q8 -> 1q9R0q9 -> 1q0R0q2 -> 0q10L0q10 -> y-S1q10 -> n-S1q2 -> 1q11L1q11 -> 1q2Ll=00//X//l//(//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 ®00SDT101TA1 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 есть композиция двух машин:1. Создает копию DT2.
Машина А26ШАГ 3DT…q0«НЕТ»SB*«ДА»xRLx¢ Модифицируемкод машины В добавив в состав еёкоманд цикл (для любого возможного x)¢ Назовем такую машину В*27СВОЙСТВА В*DT…q0«НЕТ»SB*«ДА»xRLЕсли анализатору В* предъявлено описание• самоприменимой МТ, то он зацикливается,• если не самоприменимой, то он останавливается.28ШАГ 4DB*…q0«НЕТ»SB*«ДА»xRxLВ* самоприменимая машина?Если да, то попадаем в циклЕсли нет, то попадаем на остановПротиворечия опровергают исходное предположение29.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
