тренажер для изучения универсального исполнителя

Что это такое?

Тренажёр «Машина Тьюринга» — это учебная модель универсального исполнителя (абстрактной вычислительной машины), предложенного в 1936 году А. Тьюрингом для уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста и нормальным алгорифмам Маркова .

Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a 0 ,a 1 ,…,a N } . Любой алфавит содержит символ «пробел», который обозначается как a 0 или Λ. При вводе команд пробел заменяется знаком подчеркивания « _ ».

Машина Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A , а столбцы — состояниям автомата Q={q 0 ,q 1 ,…,q M } . В начале работы машина Тьюринга находится в состоянии q 1 . Состояние q 0 — это конечное состояние: попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу a i и некоторому состоянию q j , находится команда, состоящая из трех частей:

1. символ из алфавита A ;
2. направление перемещения: > (вправо),
3. новое состояние автомата

Новости

1. Фалина И.Н. Тема «Машина Тьюринга» в школьном курсе информатики (inf.1september.ru).
2. Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru).
3. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач , М.: МГУ, 2006.
4. Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
5. Соловьев А. Дискретная математика без формул (lib.rus.ec)
6. Ершов С.С. Элементы теории алгоритмов , Челябинск, Издательский центр ЮУрГУ, 2009.
7. Варпаховский Ф.Л. Элементы теории алгоритмов , М: Просвещение, 1970.
8. Верещагин Н.К., Шень А. Вычислимые функции , М: МЦНМО, 1999.

Что с этим делать?

В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.

В таблице в нижней части окна набирается программа. В первом столбце записаны символы алфавита, он заполняется автоматически. В первой строке перечисляются все возможные состояния. Добавить и удалить столбцы таблицы (состояния) можно с помощью кнопок, расположенных над таблицей.

При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.

Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость .

Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер.

Если вы заметили ошибку или у вас есть предложения, замечания, жалобы, просьбы и заявления, пишите .

Технические требования

Программа работает под управлением операционных систем линейки Windows на любых современных компьютерах.

Лицензия

Программа является бесплатной для некоммерческого использования. Исходные тексты программы не распространяются.

Программа поставляется «as is », то есть, автор не несет никакой ответственности за всевозможные последствия ее использования, включая моральные и материальные потери, вывод оборудования из строя, физические и душевные травмы.

При размещении программы на других веб-сайтах ссылка на первоисточник обязательна.

1. 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
2. 2) распространение неполных или измененных материалов;
3. 3) включение материалов в сборники на любых носителях информации;
4. 4) получение коммерческой выгоды от продажи или другого использования материалов.

Скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.

Скачать

После распаковки архива программа находится в работоспособном состоянии и не требует никаких дополнительных установок.

В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» - абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом - учёным, которого считают одним из основоположников информатики.

Его кругозор распространялся от квантовой теории и принципа относительности до психологии и неврологии. А в качестве способа познания и передачи своих знаний Тьюринг использовал аппарат математики и логики. Он находил решения, казалось бы, нерешаемых задач, но был сильнее всего увлечен идеей «Универсальной машины», способной вычислить всё, что в принципе вычислимо.

Детство, образование, увлечения

Родители Алана жили в индийском городе Чхатрапур. Отец - Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Имперской государственной службе. Мать - Сара Этель (урожденная Стони), была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне.

Там Алан Тьюринг и родился 23 июня 1912 года. У него был старший брат Джон. Государственная служба Юлиуса Тьюринга продолжалась и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары. Признаки гениальности проявлялись у Тьюринга с раннего детства.

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

Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте 6 лет, он просил у своих воспитателей разрешения читать научно-популярные книги.

В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но её опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School).

В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 км от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.

Увлечение Тьюринга математикой не нашло особой поддержки среди учителей Шерборнской школы, где уделяли больше внимания гуманитарным наукам. Директор школы писал родителям: «Я надеюсь, что он не будет пытаться усидеть на двух стульях разом. Если он намеревается остаться в частной школе, то он должен стремиться к получению «образования». Если же он собирается быть исключительно «научным специалистом», то частная школа для него - пустая трата времени».

О школьных успехах Алана красноречиво свидетельствует классный журнал, в котором можно найти, например, следующее

Я могу смотреть сквозь пальцы на его сочинения, хотя ничего ужаснее в жизни своей не видывал, я пытаюсь терпеть его непоколебимую небрежность и непристойное прилежание; но вынести потрясающую глупость его высказываний во время вполне здравой дискуссии по Новому Завету я, все же, не могу.

Тем не менее, в областях, интересовавших его, Тьюринг проявлял незаурядные способности.

В 1928 году, в возрасте 16 лет, Тьюринг ознакомился с работой Эйнштейна, в которой ему удалось разобраться до такой степени, что он смог догадаться из текста о сомнениях Эйнштейна относительно выполнимости Законов Ньютона, которые не были высказаны в статье в явном виде.

Университет

Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.

Кембриджский университет, обладавший особыми привилегиями, дарованными английскими монархами, издавна славился либеральными традициями, и в его стенах всегда царил дух свободомыслия. Здесь Тьюринг обретает – пожалуй, впервые – свой настоящий дом, где он смог полностью отдаться науке.

Главное место в жизни заняло увлечённое изучение столь интересующих его наук – математики и квантовой физики. Те годы были периодом бурного становления квантовой физики, и Тьюринг в студенческие годы знакомится с самыми последними работами в этой области. Большое впечатление производит на него книга Джона фон Неймана «Математические основы квантовой механики», в которой он находит ответы на многие давно интересующие его вопросы.

Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне – одном из самых известных университетов США. Ещё позже фон Нейман, так же как и Тьюринг, будет назван «отцом информатики». Но тогда, в начале 30-х годов ХХ века, научные интересы обоих будущих выдающихся учёных были далеки от вычислительных машин – и Тьюринг, и фон Нейман занимаются в основном задачами «чистой» математики.

Тьюринг происходил из аристократической семьи, но никогда не был «эстетом»: кембриджские политические и литературные кружки были чужды ему. Он предпочитал заниматься своей любимой математикой, а в свободное время ставить химические опыты, решать шахматные головоломки.

Ставя химические опыты, он играл в особую игру «Необитаемый остров», изобретенную им самим. Цель игры заключалась в том, чтобы получать различные «полезные» химические вещества из «подручных средств» – стирального порошка, средства для мытья посуды, чернил и тому подобной «домашней химии».

Он также находил отдых в интенсивных занятиях спортом – греблей и бегом. Марафонский бег останется его поистине страстным увлечением до конца жизни.

Тьюринг блестяще заканчивает четырёхлетний курс обучения. Одна из его работ, посвященная теории вероятностей, удостаивается специальной премии, его избирают в научное общество Королевского колледжа. В 1935 году Тьюринг публикует работу «Эквивалентность левой и правой почти-периодичности», в которой он упрощает одну идею фон Неймана в теории непрерывных групп – фундаментальной области современной математики. Казалось, его ждет успешная карьера слегка эксцентричного кембриджского преподавателя, работающего в области «чистой» математики.

Однако Тьюринг никогда не удерживался в каких-либо «рамках». Никто не мог предвидеть, какая экзотическая проблема неожиданно увлечет его, и какой математически неординарный способ ее решения ему удастся придумать.

Кроме того, в Кембридже Алан посещал лекции Виттенштейна Людвига. Виттенштейн утверждал теорию о несостоятельности математики. По его словам математика не ищет истину, но сама создаёт её. Алан был с этим не согласен и много спорил с Людвигом. Тьюринг выступал за «формализм» - математическое философское течение, которое не требовало точного перевода слов и ограничивалось примерным смыслом. А Людвиг искал абсолютной точности.

Во время обучения в колледже Алан Тьюринг изучал основы криптографии – то есть расшифровки данных. Это пригодилось ему во время Второй Мировой войны, когда учёный работал над расшифровкой немецких посланий.

Машина Тьюринга

В 1928 году немецкий математик Давид Гильберт привлек внимание мировой общественности к проблеме разрешения (Entscheidungsproblem). В своей работе «On Computable Numbers, with an Application to the Entscheidungsproblem», опубликованной 12 ноября 1936 года. Тьюринг переформулировал теорему Гёделя о неполноте, заменив универсальный формальный арифметический язык Гёделя на простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга.

Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сперва доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.

Хотя доказательство Тьюринга было обнародовано в скором времени после эквивалентного доказательства Алонзо Чёрча, в котором использовались Лямбда-исчисления, сам Тьюринг был с ним не знаком. Подход Алана Тьюринга принято считать более доступным и интуитивным. Идея «Универсальной Машины», способной выполнять функции любой другой машины, или другими словами, вычислить всё, что можно, в принципе, вычислить, была крайне оригинальной. Фон Нейман признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Машины Тьюринга по-прежнему являются основным объектом исследования теории алгоритмов.

На вопрос : «Что такое машина Тьюринга и какое отношение она имеет к программированию?» один из пользователей Toster ответил так:

В первую очередь - это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие «Тьюринг-полного» языка - если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (препроцессор языка С таким не является, а C# - является).

В общем, МТ - способ определить некоторый класс алгоритмов:

Некоторые задачи можно решить конечным автоматом;
- для некоторых потребуется конечный автомат со стековой памятью;
- для других достаточно машины Тьюринга;
- для остальных требуется божественное откровение или другие неалгоритмизируемые методы.

С сентября 1936 года по июль 1938 Тьюринг работал под руководством Чёрча в Принстоне. Кроме занятий математикой, учёный изучал криптографию, а также конструировал электромеханический бинарный умножитель.

В июне 1938 года Тьюринг защитил докторскую диссертацию «Логические системы, основанные на ординалах», в которой была представлена идея сведения по Тьюрингу, заключающаяся в объединении машины Тьюринга с оракулом. Это позволяет исследовать проблемы, которые невозможно решить с помощью лишь машины Тьюринга.

Криптоанализ

Во время Второй мировой войны Алан Тьюринг принимал активное участие во взломе немецких шифров в Блетчли-парке. Историк и ветеран Блетчли-парка Эйза Бригс однажды сказал:

«Блетчли-парку был нужен исключительный талант, исключительная гениальность, и гениальность Тьюринга была именно такой».

С сентября 1938 года Тьюринг работал на полставки в GCHQ - британской организации, специализировавшейся на взломе шифров. Совместно с Дилли Ноксом он занимался криптоанализом «Энигмы». Вскоре после встречи в Варшаве в июле 1939 года, на которой польское Бюро шифров предоставило Великобритании и Франции подробные сведения о соединениях в роторах «Энигмы» и методе расшифровки сообщений, Тьюринг и Нокс начали свою работу над более основательным способом решения проблемы.

Польский метод основывался на недоработках индикаторной процедуры, которые немцы исправили к маю 1940 года. Подход Тьюринга был более общим и основан на методе перебора последовательностей исходного текста, для которого он разработал начальную функциональную спецификацию Bombe.

Машина, созданная на основе этой спецификации, искала возможные настройки, использованные для шифрования сообщений (порядок роторов, положение ротора, соединения коммутационной панели), опираясь на известный открытый текст. Для каждой возможной настройки ротора (у которого было 10 ^ 19 состояний или 10 ^ 22 в модификации, использовавшейся на подводных лодках) машина производила ряд логических предположений, основываясь на открытом тексте (его содержании и структуре).

Далее машина определяла противоречие, отбрасывала набор параметров и переходила к следующему. Таким образом, бо́льшая часть возможных наборов отсеивалась и для тщательного анализа оставалось всего несколько вариантов.
Первая машина была запущена в эксплуатацию 18 марта 1940 года. Перебор ключей выполнялся за счёт вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов.

Спецификация для «Бомбы» была только первым из пяти важнейших достижений Тьюринга в области военного криптоанализа.

Учёный также определил индикаторную процедуру ВМФ Германии; разработал более эффективный способ использования Bombe, основанный на статистическом анализе и названный «Банбурисмусом»; метод определения параметров колёс машины Лоренца, названный «Тьюринжерией»; ближе к концу войны Тьюринг разработал портативный шифратор речи Delilah.

Статистический подход к оптимизации исследований различных вероятностей в процессе разгадывания шифров, который использовал Тьюринг, был новым словом в науке. Тьюринг написал две работы: «Доклад о применимости вероятностного подхода в криптоанализе» и «Документ о статистике и повторениях», которые представляли для GCCS, а позже и для GCHQ (англ. Government Communications Headquarters) такую ценность, что не были предоставлены национальному архиву вплоть до апреля 2012 года, незадолго до празднования ста лет со дня рождения учёного. Один из сотрудников GCHQ заявил, что этот факт говорит о беспрецедентной важности этих работ.

Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 года по март 1943 года в США.

В 1945 году Тьюринг был награждён орденом Британской империи королём Георгом VI за свою военную службу, но этот факт оставался в секрете многие годы.

Послевоенные годы

После того как фон Нейман в США предложил план создания компьютера EDVAC, аналогичные работы были развернуты в Великобритании в Национальной физической лаборатории, где Тьюринг проработал с 1945 года. Ученый предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), который, однако, так и не был реализован.

Несмотря на то, что постройка ACE была вполне осуществима, секретность, окружавшая Блэтчли-парк, привела к задержкам в начале работ, что разочаровало Тьюринга.

1947–1948 академический год Тьюринг провел в Кембридже. Пока Алан Тьюринг пребывал в Кембридже, Pilot ACE был построен в его отсутствие.

Franklin ACE 1200

Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру, DEUCE и Bendix G-15.

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

В 1948 году Алан совместно со своим бывшим коллегой начал писать шахматную программу для компьютера, который ещё не существовал.

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

Тест Тьюринга

В 1948 году Алан Тьюринг получил звание Reader в математическом департаменте Манчестерского университета. Там в 1949 году он стал директором компьютерной лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I.

В то же время Тьюринг продолжал работать над более абстрактными математическими задачами, а в своей работе «Computing Machinery and Intelligence» (журнал «Mind», октябрь 1950) он обратился к проблеме искусственного интеллекта и предложил эксперимент, ставший впоследствии известным как тест Тьюринга.

Его идея заключалась в том, что можно считать, что компьютер «мыслит», если человек, взаимодействующий с ним, не сможет в процессе общения отличить компьютер от другого человека. В этой работе Тьюринг предположил, что вместо того, чтобы пытаться создать программу, симулирующую разум взрослого человека, намного проще было бы начать с разума ребёнка, а затем обучать его. CAPTCHA, основанный на обратном тесте Тьюринга, широко распространён в интернете.

В 1951 году Тьюринг был избран членом Лондонского королевского общества.

В первоначальной формулировке «тест Тьюринга» предполагает ситуацию, в которой два человека, мужчина и женщина, по некоторому каналу, исключающему восприятие голоса, общаются с отделенным от них стеной третьим человеком, который пытается по косвенным вопросам определить пол каждого из своих собеседников; при этом мужчина пытается сбить с толку спрашивающего, а женщина помогает спрашивающему выяснить истину.

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

Данный мысленный эксперимент имел ряд принципиальных следствий. Во-первых, он предложил некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?».

Во-вторых, этот критерий оказался лингвистическим: указанный вопрос был явным образом заменен вопрос о том, может ли машина адекватным образом общаться с человеком на естественном языке. Тьюринг прямо писал о замене формулировки и при этом выражал уверенность в том, что «метод вопросов и ответов пригоден для того, чтобы охватить почти любую область человеческой деятельности, какую мы захотим ввести в рассмотрение».

Следствием этого стала та важнейшая роль, которую в дальнейшем развитии искусственного интеллекта, во всяком случае, до 1980-х годов играли исследования по моделированию понимания и производства естественного языка. В 1977 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.

Машина Тьюринга - это совокупность следующих объектов

• 1) внешний алфавит A={a 0 , a 1 , …, a n };
• 2) внутренний алфавит Q={q 1 , q 2 ,…, q m } - множество состояний;
• 3) множество управляющих символов {П, Л, С}
• 4) бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;
• 5) управляющее устройство, способное находиться в одном из множества состояний

Символом пустой ячейки является буква внешнего алфавита а 0 .

Среди состояний выделяются начальное q 1 , находясь в котором машина начинает работать, и заключительное (или состояние остановки) q 0 , попав в которое машина останавливается.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы алфавита A. Управляющее устройство работает согласно командам, которые имеют следующий вид

q i a j > a p X q k

Запись означает следующее: если управляющее устройство находится в состоянии q i , а в обозреваемой ячейке записана буква a j , то (1) в ячейку вместо a j записывается a p , (2) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходит в состояние q k.

Поскольку работа машины, по условию, полностью определяется ее состоянием q, в данный момент и содержимым а обозреваемой в этот момент ячейки, то для каждой возможной конфигурации q i a j имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Поэтому программа машины Тьюринга с внешним алфавитом A={a0, a1, …, an} и внутренним Q={q1, q2,…, qm} содержит не более m (n+ 1) команд.

Словом в алфавите А или в алфавите Q, или в алфавите A Q называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-того шага (или слово в алфавите А, записанное на ленту к началу k-того шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.

Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.

Будем говорить, что непустое слово б в алфавите А {а 0 } = {a 1 , …, a n } воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справа ячейку из тех, в которых записано слово б. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (соответственно в состоянии остановки q 0).

Если обработка слова б переводит машину Тьюринга в заключительное состояние, то говорят, что она применима к б, в противном случае - не применима к б (машина работает бесконечно)

Рассмотрим пример:

Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 - символ пустой ячейки), алфавитом внутренних состояний Q = {q 0 , q 1 , q 2 } и со следующей функциональной схемой (программой):

q 1 0 > 1 Л q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 С q 1 ;

Данную программу можно записать с помощью таблицы

На первом шаге действует команда: q 1 0 > 1 Л q 2 (управляющее устройство находится в состоянии q1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q2), в результате на машине создается следующая конфигурация:

Наконец, после выполнения команды q 2 0 > 0 П q 0 создается конфигурация

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q 0 .

Таким образом, исходное слово 110 переработано машиной в слово 101.

Полученную последовательность конфигураций можно записать более коротким способом (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Машина Тьюринга - не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A Q, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.

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

Суть простыми словами

Следует сразу обозначить важный момент: машина Тьюринга - исключительно умозрительное устройство. В природе ничего подобного не существует. Компьютерные модели, правда, есть. Даже действующие. Но они - не более чем модели.

Почему так? Потому что предмет обсуждения представляет собой бесконечную ленту, полноценное физическое существование которой на данном этапе развития науки и техники возможно исключительно теоретически.

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

Как это функционирует

Движущаяся часть - устройство чтения и записи. Какая-нибудь штуковина, способная считывать содержимое ячеек, записывать в них что-нибудь своё и, главное, действовать в соответствии с получающимися результатами.

Причём, автомат может за один раз перемещаться только на одну ячейку. Вправо, влево, куда надо для выполнения вычислений. Здесь что-то приплюсовал - надо передвинуться, чтобы что-то отнять. А потом - опять сложить. И так сколь угодно долго, пока задача не будет выполнена. Лента ведь бесконечная, вариантов хватит для любых операций.

Собственно говоря, Алан Тьюринг как раз и стремился подчеркнуть, что каждое вычисление, каким бы сложными ни было, можно выполнять поэтапно, шаг за шагом, разбив задачу на элементарные составляющие. В этом и заключается суть алгоритма .

Разные варианты

Посмотрели начинающие кибернетики на машину Тьюринга и уразумели, что придраться не к чему. Действительно, компьютерные программы следует строить на основе алгоритмов - пошагового исполнения инструкций.

Вместе с тем, слава Алана Тьюринга многим не давала покоя, и последователи начали, как говорится, ловить её отблески. Начали выдумывать многомерные машины Тьюринга, с множеством лент, «полубесконечные» etc.

Мы же попытаемся внести в этот хаос хоть какую-то ясность и рассмотрим всамделишные варианты обсуждаемого устройства.

1. Недетерминированная - это такая машина Тьюринга, которая действует на вышеописанной ленте с ячейками в соответствии с ситуацией, возникающей на том или ином этапе вычислений. Куда ей надо, туда и двинется, иными словами.
2. Детерминированная - такая, в которую заложены конкретные инструкции. Например, если в ячейке, где находится исполняющий автомат, записана буква А, то надо передвинутся в соседнюю, с буквой Б, хочется того или нет.
3. Полная - способная вычислить вообще всё, что можно вычислить пошаговыми операциями. Может даже смоделировать машину в машине, эмулятор, описывающий алгоритмами работу другого аналогичного устройства.
4. Универсальная - умеющая всё, что умеют какие угодно варианты машины Тьюринга. Вообще любые, даже ещё не придуманные. Конечно, является полной.

Практическая польза

Конечно, алгоритм - понятие более сложное, нежели просто передвижение исполнения по шагам в одномерном пространстве. Ведь возможны ветвления, зацикливания, возвращения назад, задействование подпрограмм.

Кроме того, смоделировать бесконечное множество ячеек, содержащих данные, невозможно на практике хотя бы потому, что возможности компьютерного оборудования ограничены.

Тем не менее, есть программы, имитирующие машину Тьюринга, предназначенные для обучения студентов. Начинающим программистам предлагается разработать разные алгоритмы, например, ищущие, меняющие, добавляющие, переставляющие в ячейках буквы.

Следовательно, польза от машины Тьюринга именно такая, какая и была задумана её создателем, пророком компьютерной эпохи: наглядная демонстрация сути алгоритмических вычислений.

Предыдущие публикации:

Последнее редактирование: 2013-04-01 10:58:05

Метки материала: ,

В логике с помощью понятия машины Тьюринга строится теория неразрешимых проблем, однако в вычислительной практике чаще приходится иметь дело с разрешимыми, но “трудно решаемыми” проблемами. Выбирая и здесь в качестве вычислительной модели машину Тьюринга, мы руководствуемся тем, что она проста и допускает те же языки, что и компьютер, причем сложность вычислений на машине Тьюринга полиномиальна от числа шагов компьютера.

Машина Тьюринга представляет собой абстрактную вычислительную машину, состоящую из управления с конечным числом состояний и бесконечной ленты, разделенной на ячейки, в каждой из которых хранится один ленточный символ, и одна из ячеек является текущей позицией ленточной головки. Формальная запись машины Тьюринга - это упорядоченный набор M = (X, Q, q 0 , F, I), где

X – внешний алфавит символов (букв на ленте), включающий символ L;

Q – конечный алфавит внутренних состояний;

q 0 – инициальное состояние (начало работы), q 0 Î Q;

F– множество заключительных состояний, FÌ Q;

I - множество инструкций, или машинных команд, каждая из которых принадлежит множеству (Q \ F) ´ X ´ {®} ´ Q ´ X ´ {R,L,S}.

Переходы осуществляются на основе текущего состояния и обозреваемого считывающей головкой символа к следующему состоянию, переписыванию символа и сдвигу головки (вправо R, влево L, на месте S).

Можно определить функцию переходов

d: (Q \ F) ´ X* ® Q ´ X* ´ {R,L,S}, где X* -слова в алфавите X.

В случае однозначной функции d машина Тьюринга называется детерминированной машиной Тьюринга.

Текущей конфигурацией машины Тьюринга называют цепочку значащих (отличных от L) символов, записанных на ленте в данный момент времени, вместе с символом состояния, помещенным в цепочку перед обозреваемым символом.

Останов (завершение работы) происходит в заключительном состоянии или когда левая часть (до ®) ни одной из машинных команд не содержится в полученной конфигурации. Говорят, что машина допускает вход, если она останавливается на нем в заключительном состоянии.

В качестве примера рассмотрим работу детерминированной машины Тьюринга, вычисляющей функцию ïm - nï. Упорядоченную пару натуральных чисел (m,n) представляем как слово 0 m 10 n в алфавите X \ {L} = {0,1}, ячейки слева и справа от которого содержат символ L.

Q 0 0 ® LRq 1 Состояния Символ

Q 1 0 ® 0Rq 1 0 1 L

q 1 1 ® 1Rq 2 q 0 LRq 1 1Sq 5 0Sq 5

q 2 0 ® 1Lq 3 q 1 0Rq 1 1Rq 2 ¾

q 2 1 ® 1Rq 2 q 2 1Lq 3 1Rq 2 LLq 4

q 3 1 ® 1Lq 3 q 3 0Lq 3 1Lq 3 LRq 0

q 3 0 ® 0Lq 3 q 4 0Lq 4 LLq 4 0Sq 5

q 3 L ® LRq 0 q 5 ¾ LRq 5 ¾

q 2 L ® LLq 4 *

q 4 1 ® LLq 4 Таблица 1. Программа вычисления функции ôm - nô,

q 4 0 ® 0Lq 4 где функция переходов задается таблицей

q 0 1 ® 1Sq 5 *

Машина Тьюринга M допускает (отвергает) слово wÎ X * , если она останавливается на нем, придя в допускающее (заключительное) состояние. Машина допускает язык LÍ X * , если она допускает все слова языка L. Машина M распознает язык LÍ X * , если она допускает все слова из L и останавливается на словах из X * \ L, не находясь в заключитель ном состоянии. Языки, допускаемые машиной Тьюринга, назовем рекурсивно перечислимым.

Язык L допускается (распознается) за полиномиальное время , если существует машина M, которая допускает (распознает) язык L, причем всякое слово wÎ L допускается (распознается) за время O(n k), где n – длина слова w, а k – не зависящее от w число.

Теперь можно определить класс P, как множество языков LÍ {0,1} * , распознаваемых за полиномиальное время.

Теорема. Класс P есть множество языков, допускаемых за полиномиальное время.

Доказательство. В одну сторону тривиально, если машина M распознает язык L, то она и допускает язык L. Обратно, пусть язык L допускается машиной M за время O(n k), т.е. существует константа c, что любое слово из L длины n допускается не более, чем за T = c×n k шагов. С другой стороны, слова, не принадлежащие L, не допускаются ни за какое время. Построим машину M * , которая на слове w моделирует не более Т = c×n k шагов машины M и останавливается, выдавая 1, если M(w)=1, в противном случае - останавливается, сделав Т = c×n k шагов, выдавая на выход 0. Таким образом, машина M * распознает язык L и сложностной класс P можно рассматривать, как множество языков, допускаемых за полиномиальное время. “

Многоленточная машина Тьюринга.

Для имитации работы компьютера используются многоленточные машины Тьюринга. В начальной конфигурации многоленточной машины на первой ленте размещается вход (конечная последовательность символов, куда не входит L), все клетки остальных лент содержат символ L, считывающие головки всех лент находятся в начальном состоянии.

За один переход осуществляются следующие действия:

Управление переходит в новое состояние,

На каждой ленте записывается новый (или тот же) символ;

Считывающие головки каждой из лент независимо сдвигаются на одну ячейку (R,L,S).

Языки, допускаемые одноленточными машинами Тьюринга, рекурсивно перечислимы. Допустимы ли многоленточными машинами не рекурсивно перечислимые языки? Ответ в следующей теореме.

Теорема. Каждый язык L, допускаемый многоленточной машиной Тьюринга, рекурсивно перечислим.

Доказательство. Одноленточную машину Тьюринга можно представить, как многодорожечную , задавая ее аргументы в виде кортежей. При этом одна дорожка хранит данные, а другая отметку. Смоделируем k - ленточную машину M как многодорожечную машину N, содержащую 2k дорожек, где каждая вторая содержит маркер, указывающий позицию головки соответствующей ленты. Машина N должна посетить каждый из маркеров головок k лент и изменить соответствующим образом символ, представляющий соответствующую ленту, перемещая маркер в том направлении, как это происходило на соответствующей ленте. Наконец, N изменяет состояние М, записанное в конечном управлении N. В качестве допускающих состояний N выбираются все те состояния, в которых запоминалось допускающее состояние M. Таким образом, машина M и N одновременно допускают язык L. Но все языки, допускаемые одноленточной машиной N, рекурсивно перечислимы, поэтому рекурсивно перечислимы все языки, допускаемые многоленточной машиной M. “

Теорема. Время, необходимое одноленточной машине N для имитации n переходов k-ленточной машины M, есть O(n 2).

Доказательство. После n переходов машины M маркеры головок разделены не более, чем 2n клетками, так что и машине N надо сдвинуться не более, чем на 2n клеток вправо, чтобы найти все маркеры головок. Теперь ей надо совершить проход влево, изменяя содержимое M лент и сдвигая головочные маркеры, что потребует не более 2n сдвигов влево плюс не более 2k переходов для изменения направления движения и записи маркера в клетку. Таким образом, число переходов N для имитации одного из переходов машины M не более 4n+2k, т.е. O(n). Для n переходов требуется времени в n раз больше, т.е. O(n 2). “

Различие во времени вычисления на машинах с разным числом лент сохраняет полиномиальную сложность и для одноленточной машины ограничено с×T(n) 2 , а емкость - с×S(n) (для входа длины n), где T(n), S(n) – параметры k-ленточных машин. Зависимость между емкостью и временем для k-ленточных машин линейная: S £ kT; для входа w длины n

Недетерминированные машины Тьюринга.

По причинам, которые вскоре будут понятны, недетерминированные машины Тьюринга являются ключевым понятием в теории NP-полных задач. Недетерминированная машина Тьюринга отличается от обычной (детерминированной) машины Тьюринга тем, что может иметь более одного перехода от текущей конфигурации к следующей. Недетерминированная машина допускает слово w, если существует хотя бы одна цепочка конфигураций, ведущая от начальной конфигурации в заключительную. Существование других последовательностей конфигураций, не ведущих в заключительное (допускающее) состояние не имеет значение. Работу недетерминированной машины на входе w можно представить в виде дерева, где каждый путь из корня w в лист представляет некоторую последовательность возможных шагов машины. Если s w кратчайшая последовательность возможных шагов работы машины, которая оканчивается допускающей конфигурацией, то ½s w ½ есть время, затраченное машиной на обработку входа w. Если на входе w никакая последовательность не приводит к допускающей конфигурации, то время, затраченное на обработку w не определено. Считается, что недетерминированная машина Тьюринга на входе w параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего состояния или окажется, что ее программа не применима к полученной конфигурации.

Остается открытым вопрос, существуют ли языки, допускаемые недетерминированной машиной Тьюринга с данной временной и емкостной сложностью и не допускаемые никакой детерминированной машиной с той же сложностью.

Недетерминированные машины Тьюринга допускают те же языки, что и детерминированные. Однако, надо заметить, что последним приходится за это расплачиваться сильным увеличением временной сложности.

Обозначим через L(M) множество всех слов wÎX*, допускаемых машиной M, L(M) называют языком машины M.

Теорема. Если M недетерминированная машина с полиномиальной временной сложностью T(n), то существует детерминированная машина M ’ , с L(M ’ ) = L(M) и временной сложностью O(c T(n)).

Доказательство. Доказательство основывается на том, что для любой недетерминированной машины Тьюринга M строится детерминированная машина M ’ , которая исследует последовательности конфигураций (пути в дереве недетерминированной машины) и если находит хотя бы одну с допускаемым состоянием, то сама переходит в допускаемое состояние. Обследованные конфигурации помещаются в очередь, длины k (k=1,2…) Построим детерминированную многоленточную машину M ’ , моделирующую недетерминированную машину M. Первая лента машины M ’ хранит последовательность конфигураций машины M и метку на текущее состояние последней. Записи слева от метки предполагаются исследованными и их в дальнейшем игнорируют. Конфигурации справа рассматриваются в порядке очереди. Программа машины M хранится в конечном управлении M ’ . Обработка текущей конфигурации на первой ленте состоит в следующем:

Машина M ’ проверяет состояние и обозреваемый символ и, если состояние допускающее, также переходит в допускающее состояние.

Если состояние не допускающее и из данной конфигурации есть k переходов, то M ’ использует вторую ленту для создания k копий, которые записываются в конце очереди на ленте 1.

M ’ изменяет k конфигураций в соответствии с программой машины M.

M ’ перемещает отметку текущей конфигурации на следующую справа и цикл повторяется с шага 1.

Допустим, что m есть максимальное число выборов машины M в любой конфигурации. Тогда существует одно начальное состояние M, не более m конфигураций, достижимых за 1 шаг, не более m 2 конфигураций, достижимых за 2 шага и т.д. Таким образом, после n переходов машина M может достичь не более 1+ m +m 2 +…+m n £ n×m n конфигураций. Порядок, в котором машина M ’ исследует конфигурации, называется “поиском в ширину”, т.е. M ’ исследует все достижимые конфигурации машины M за 0 шагов, достижимые за 1 шаг и т.д.

Допускающая конфигурация машины M будет рассмотрена машиной M ’ в числе первых n×m n конфигураций. Таким образом, если машина M допускает, то машина M ’ также допускает, т.е. L(M) = L(M ’ ). “

Отметим, что работа построенной детерминированной машины M ’ может потребовать экспоненциально большего времени, чем время работы недетерминированной машины M, которую она моделирует. Разница между полиномиальным и экспоненциальным временем - это граница того, что можно решить с помощью компьютера, а что практически нерешаемо.

Теорема. Если M недетерминированная машина Тьюринга с емкостной сложностью S(n), то найдется детерминированная машина Тьюринга M ’ с емкостной сложностью O(S 2 (n)) и L(M ’ ) = L(M).

Доказательство. Пусть M недетерминированная машина Тьюринга (возможно k-ленточная) с емкостной сложностью S(n). Тогда число различных конфигураций, в которые машина M может попасть из начальной с входом длины n, не превосходит некоторого числа c S (n) , точнее ½Q½(½X½+1) k S(n) (S(n)) k , где k – число лент. Тогда число переходов от конфигурации C 1 к конфигурации C 2 (С 1 ├ С 2) на любой из лент не превосходит c S (n) . Можно выяснить, существует ли переход С 1 ├ С 2 за 2i шагов, проверив для всех C 3 существует ли переход С 1 ├ С 3 и С 3 ├ С 2 за i шагов. После каждого обращения к процедуре число i уменьшается вдвое.

Идея моделирования машиной M ’ работы машины M приведена в доказательстве предыдущей теоремы. Стратегия работы машины M ’ -

установить приведет ли начальная конфигурация C 0 к какой-нибудь допускающей конфигурации C f . Чтобы найти верхнюю емкостную границу для машины M ’ , расположим конфигурации (длины O(S(n))) на стеках того же размера. В каждый момент времени число фрагментов стека не превосходит 1+ log éc S (n) ù , т.е. O(S(n)). Для всего стека машины M потребуется O(S 2 (n)) ячеек. “

Теорема. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга M = (X, Q, q 0 , F, I) с временной сложностью T(n), то он допускается одноленточной недетерминированной машиной с временной сложностью O(T 2 (n)).

Доказательство. Пусть M 1 одноленточная недетерминированная машина Тьюринга, имеющая на ленте 2k дорожек, т.е. ленточные символы машины M 1 представляются 2k-членными кортежами, в которых на нечетных местах стоят символы алфавита X, а на четных – либо символ L, либо маркер #. Дорожки с нечетными номерами соответствуют k лентам машины M, а каждая дорожка с четным номером 2j содержит символ L во всех ячейках, кроме одной, где стоит маркер #, отмечающий положение головки машины M на ленте j, которой соответствует дорожка 2j-1. Машина M 1 моделирует один шаг работы машины M следующим образом. Допустим, что вначале головка машины M 1 обозревает клетку, содержащую самую левую головку машины M.

Головка машины M 1 движется вправо, пока не минует все k маркеров положений головок на дорожках с четными номерами. При этом M 1 запоминает в своем состоянии символы, обозреваемые каждой из головок машины M. Теперь M 1 делает недетерминированное развлетвление, исходя из состояния машины M, которое машина M 1 запомнила в своем состоянии, и обозреваемых машиной M на лентах символов, которые машина M 1 также нашла.

Выбрав для моделирования шаг машины M, машина M 1 изменяет в соответствии с ним состояние машины M, которое она помнит в своем состоянии. Затем M 1 сдвигает свою головку влево и проходит все маркеры, изменяя ленточный символ на дорожке над маркером и сдвигая маркер не более чем на одну клетку (L,R,S).

Машина M 1 промоделировала один шаг работы машмны M. Действия машины M 1 на этом шаге детерминированы. Ее головка находится правее левого маркера не более чем на две ячейки. Начиная с этого маркера цикл можно повторить.

Если машина M допускает цепочку w длины n, то совершает при этом не более T(n) переходов. Очевидно, что в последовательности из T(n) шагов головки мащины M могут разойтись не более чем на T(n) клеток, и, значит, M 1 может смоделировать один шаг этой последовательности не более чем за O(T(n)) своих шагов. Таким образом, M 1 допускает цепочку w, выполняя не более чем O(T 2 (n)) переходов. Отсюда следует, что M 1 допускает язык L и имеет временную сложность O(T 2 (n)). “

Следствие 1. Если язык допускается k-ленточной детерминированной машиной Тьюринга с временной сложностью T(n), то он допускается одноленточной детерминированной машиной Тьюринга с временной сложностью O(T 2 (n)). “

Следствие 2 . Если язык L допускается k-ленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n). “

Следствие 3. Если язык допускается k-ленточной детерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной детерминированной машиной Тьюринга с емкостной сложностью S(n). “

Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.

К основным компонентам вычислительной машины относятся оперативная память и процессор. Программы и данные, представленные в двоичном алфавите, помещаются в память. При выполнении программы отдельные ее команды и нужные данные извлекаются из памяти в процессор и наоборот – значения, получаемые при выполнении команд, записываются в ячейки памяти.

Память состоит из некоторого числа запоминающих ячеек (регистров), предназначенных для промежуточного хранения значений операндов и для хранения другой информации, необходимой для выполнения команд, регистров для управления запоминающими ячейками, адресов ячеек и полей самих ячеек.

Процессор состоит из устройства управления (УУ) и арифметического устройство (АУ). Устройство управления содержит счетчик тактов, команд и т.д., вырабатывает управляющие сигналы для выполнения команд, передачи данных и т.д. Процессор содержит регистры операндов, линии связи и линии задержки для непосредственной реализации процессов вычислений.

Наряду с процессором и памятью компьютеру необходимы еще устройства ввода/вывода.

Имитация машины Тьюринга на компьютере. Пусть M - машина Тьюринга, одним из составляющих которой является ее конечное управление. Поскольку M имеет конечное число состояний и конечное число правил перехода, программа компьютера может закодировать состояния в виде цепочек символов, как и символы ее внешнего алфавита, и использовать таблицу переходов машины M для преобразования цепочек. Бесконечную ленту машины Тьюринга можно имитировать сменными дисками, размещаемыми в двух магазинах, соответственно для данных, расположенных слева и справа от считывающей головки на ленте. Чем дальше в магазине расположены данные, тем дальше они от головки на ленте.

Для имитации компьютера на машине Тьюринга существенны две вещи:

Существуют ли инструкции, выполняемые компьютером, и недоступные для машины Тьюринга;

Работает ли компьютер быстрее машины Тьюринга, т.е. более, чем полиномиальная зависимость разделяет время работы компьютера и машины Тьюринга при решении какой-то проблемы.

Неформальная модель реального компьютера :

Память, состоящая из последовательности слов и их адресов. В качестве адресов будут использоваться натуральные числа 0,1, …;

Программа компьютера, записанная в слова памяти, каждое из которых представляет простую инструкцию. Допускается “непрямая адресация” по указателям;

Каждая инструкция использует конечное число слов и изменяет значение не более одного слова;

Имеются слова памяти с быстрым доступом (регистры), но скорость доступа к различным словам влияет лишь на константный сомножитель, что не искажает полиномиальную зависимость.

Возможная конструкция машины Тьюринга для имитации компьютера

представлена на рис.

Рис стр 369

Машина имеет несколько лент. Первая лента представляет всю память компьютера – адреса и значения (в двоичной системе). Адреса заканчиваются маркером *, значения – маркером #. Начало и конец записей 1-й ленты обозначаются маркером $. Вторая лента – “счетчик инструкций”, содержит одно двоичное целое, представляющее одну из позиций считываюшей головки на первой ленте, адрес инструкции, которая должна быть выполнена следующей. Третья лента содержит адрес и значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции машина Тьюринга должна найти значение по одному или нескольким адресам памяти, где хранятся данные, участвующие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения. Значение по этому адресу копируется на третью ленту и перемещается на нужное место, как правило, по одному из начальных адресов, представляющих регистры компьютера. Четвертая лента имитирует входной файл. Пятая лента - рабочая память, служит для выполнения вычислений. Допускающая инструкция машины Тьюринга соответствует выводу на печать в выходном файле.

Функционирование такой имитирующей машины:

1.Найдя на 1-й ленте адрес, совпадающий с номером инструкции на 2-й ленте, исследуем значение по нему и копируем на 3-ю ленту. Первые биты инструкции задают действие (копировать, вставить, ветвиться и т.д.), оставщиеся биты – адрес или адреса, используемые в этом действии.

2. Если в инструкции содержится значение по некоторому адресу, то этот адрес копируется на 3-ю ленту, а позиция инструкции на 2-ю дорожку 1-й ленты.

a) скопировать по другому адресу;

Второй адрес извлекается из инструкции, помещается на 3-ю ленту, находится на 1-й ленте и значение по нему копируется в зарезервированное для него пространство. Если для нового значения надо больше (меньше) памяти, чем для старого, пространство изменяется путем сдвига, а именно,

(1) на рабочую ленту копируется часть ленты справа от того места, куда надо поместить новое значение;

(2) новое значение записывается на 1-ю ленту;

(3) рабочая часть копируется обратно на 1-ю ленту справа от нового значения.

b) прибавить найденное значение по другому адресу;

Ищем второй адрес на первой ленте, выполняем сложение значения по этому адресу и записанному на 3-й ленте.

c) перейти к выполнению инструкции по адресу, записанному на 3-й ленте, для чего лента 3 копируется на ленту 2, и цикл инструкций начинается снова.

4. Выполнив инструкцию (не являющуюся переходом), прибавляем 1 к счетчику на ленте 2 и вновь начинаем цикл инструкции.

Теперь надо убедиться, что если проблему можно решить за полиномиальное время на компьютере, то ее можно решить за полиномиальное время на машине Тьюринга и наоборот. Как следует из доказанных выше теорем, достаточно использовать многоленточную машину Тьюринга, так как различие во времени работы одноленточной и многоленточной машин Тьюринга полиномиально.

Время работы машины Тьюринга, имитирующей компьютер

Введем следующие ограничения на модель компьютера:

Ни одна компьютерная инструкция не должна порождать слово, длиннее, чем на 1 бит, своих операндов.

Инструкция, применяемая к словам длины m должна выполняться не более, чем за 0(m 2) шагов на многоленточной машине Тьюринга.

Назовем такие операции допустимыми.

Этим условиям удовлетворяют сложение, сдвиг на 1 бит, сравнение значений, которые выполняются на многоленточной машине Тьюринга за 0(m) шагов. А также умножение m-битовых целых, если его имитировать с помощью m последовательных сложений со сдвигами на 1 бит влево. Время выполнения операции умножения будет пропорционально квадрату длины сомножителей. .

Теорема. Для компьютера, обладающего указанными свойствами, описанная выше модель машины Тьюринга может имитировать m шагов компьютера не более, чем за 0(m 3)шагов.

Доказательство. Вначале первая лента содержит только программу компьютера, длина которой не зависит от n (числа шагов выполнения инструкций). Наибольшее из компьютерных слов или адресов, встречающихся в программе, обозначим через c, а через d - число слов программы.

После выполнения n шагов компьютер не может породить слово, длиннее c+n, и не может создать или использовать адрес, занимающий больше c+n битов. Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому после выполнения n инструкций имеем d+n адресов. Каждый адрес-значение занимает не более 2(c+n) +2 разрядов, а после выполнения n инструкций не больше 2(d+n)(c+n+1), или 0(n 2)

Для просмотра адресов одной инструкции компьютера требуется времени 0(n 2), слова имеют длину 0(n), а инструкции выполняются машиной Тьюринга за время 0(n 2), сдвиг для создания пространства для нового слова включает копирование данных объемом 0(n 2) с ленты 1 на рабочую ленту и обратно. Таким образом, машина Тьюринга имитирует один шаг компьютера за 0(n 2) своих шагов, а n шагов можно проимитировать за 0(n 3) шагов машины Тьюринга. “

Теорема. Выполнение n шагов работы компьютера можно проимитировать на одноленточной машине Тьюринга не более чем за 0(n 6) шагов.

Таким образом, машина Тьюринга может имитировать память и управление реального компьютера, используя только одну ленту для записи всех элементов памяти и их содержимого – регистров, основной памяти, дисков и других запомиинающих устройств. Отсюда можно быть уверенным, что все, не выполнимое машиной Тьюринга, не может быть вычислено и компьютером. “