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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тренажёр «Машина Тьюринга» — это учебная модель универсального исполнителя (абстрактной вычислительной машины), предложенного в 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 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.

Тема “Машина Тьюринга” в школьном курсе информатики

И.Н. Фалина,
Москва

Во многих учебниках по информатике при изучении понятия и свойств алгоритма присутствуют фразы такого содержания: “…существует много разных способов для записи одного и того же алгоритма, например, запись в виде текста, запись в виде блок-схемы, запись на каком-либо алгоритмическом языке, представление алгоритма в виде машины Тьюринга или машины Поста…”. К сожалению, такого типа фразы являются единственными, где упоминается машина Тьюринга. Без сомнения, объем часов, отводимых на изучение алгоритмов, не позволяет включать в эту тему еще и изучение способов записи алгоритма в виде машины Тьюринга. Но эта тема крайне интересна, важна и полезна для школьников, особенно увлекающихся информатикой.

Тема “Машина Тьюринга” может изучаться в 8–11-х классах в рамках темы “Информационные процессы. Обработка информации”, на факультативных занятиях, в системе дополнительного образования, например, в школах юных программистов. Изучение этой темы может сопровождаться компьютерной поддержкой, если у учителя есть программный тренажер-имитатор “Машина Тьюринга”. В классах с углубленным изучением программирования школьники могут самостоятельно написать программу “Машина Тьюринга”. В рамках этой статьи вашему вниманию предлагается практикум по решению задач на тему “Машина Тьюринга”. Теоретический материал по данной теме не раз печатался на страницах газеты “Информатика”, например, в № 3/2004 статья И.Н. Фалиной “Элементы теории алгоритмов”.

Краткий теоретический материал

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

В каждой машине Тьюринга есть две части:

1) неограниченная в обе стороны лента , разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита : алфавит входных символов A = {a 0 , a 1 , ..., a m }и алфавит состояний Q = {q 0 , q 1 , ..., q p }. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q .) Состояние q 0 называется пассивным . Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q 1 называется начальным . Находясь в этом состоянии, машина начинает свою работу.

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

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

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

• · записать новую букву в обозреваемую ячейку;
• · выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
• · перейти в новое состояние.

То есть у машины Тьюринга есть три вида операций. Каждый раз для очередной пары (q j , a i ) машина Тьюринга выполняет команду, состоящую из трех операций с определенными параметрами.

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

Клетка (q j , a i ) определяется двумя параметрами - символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).

После выполнения автоматом очередной команды он переходит в состояние q m (которое может в частном случае совпадать с прежним состоянием q j ). Следующую команду нужно искать в m -й строке таблицы на пересечении со столбцом a l (букву a l автомат видит после сдвига).

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

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

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

Решение. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так:

В этой машине Тьюринга q 1 - состояние изменения цифры, q 0 - состояние останова. Если в состоянии q l автомат видит цифру 0..8, то он заменяет ее на 1..9 соответственно и переходит в состояние q 0 , т.е. машина останавливается. Если же он видит цифру 9, то заменяет ее на 0, сдвигается влево, оставаясь в состоянии q l . Так продолжается до тех пор, пока автомат не встретит цифру меньше 9. Если же все цифры были равны 9, то он заменит их нулями, запишет 0 на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем перейдет в состояние q 0 , т.е. остановится.

Практические задания

1. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q 1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q 1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q 1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q 1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “()”.

Например, дано “) (() (()”, надо получить “) . . . ((”.

Автомат в состоянии q

6. Дана строка из букв “a ” и “b ”. Разработать машину Тьюринга, которая переместит все буквы “a ” в левую, а буквы “b ” - в правую части строки. Автомат в состоянии q 1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

7. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q 1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

8. Даны два натуральных числа m и n , представленные в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q 1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n . Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

9. Даны два натуральных числа m и n , представленных в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q 1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n . Известно, что m > n . Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

10. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе - “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Решения заданий

В состоянии q 1 машина ищет правый конец числа, в состоянии q 2 - пропускает знак “+”, при достижении конца последовательности - останавливается. В состоянии q 3 машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается.

Решение этой задачи аналогично рассмотренному выше примеру.

Состояние q 1 - уменьшаем младшую (очередную) цифру на 1. Если она не равна нулю, то после уменьшения сразу - останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. В клетку [a 0 , q 1 ] машина Тьюринга никогда не попадет, поэтому ее можно не заполнять.

Задача 4 (усложнение задачи 3)

Состояние q 1 - уменьшаем младшую (очередную) цифру на 1. Если она больше 1, то после уменьшения - сразу останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. Если уменьшаемая цифра равна 1, то вместо нее пишем 0 и переходим в состояние q 2 .

Состояние q 2 - после записи “0” в каком-либо разряде надо проанализировать, не является ли этот ноль старшей незначащей цифрой (т.е. не стоит ли слева от него в записи выходного слова a 0).

Состояние q 3 - если записанный “0” является старшей незначащей цифрой, то его надо удалить из записи выходного слова.

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

Состояние q 1: если встретили “(”, то сдвиг вправо и переход в состояние q 2 ; если встретили “a 0 ”, то останов.

Состояние q 2: анализ символа “(” на парность, в случае парности должны увидеть “)”. Если парная, то возврат влево и переход в состояние q 3 .

Состояние q 3: стираем сначала “(”, затем “)” и переходим в q 1 .

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

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

aaa ->

a -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

bbb -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

b -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

ab -> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

Результат обсуждения. Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q 1 - движение по цепочке из букв “a ”, а q 2 - состояние движения по цепочке из букв “b ”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q 1 или q 2 , т.е. встретили a 0 , машина должна остановиться, мы обработали всю строку.

Рассмотрим следующие варианты входных слов:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: bba -> bbb -> вернуться к левому концу цепочки из букв “b ” -> abb (заменить первую букву в этой цепочке на “a ”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q 2 . Таким образом, для решения этой задачи нам нужно построить машину Тьюринга со следующими состояниями:

q 1 - идем вправо по цепочке букв “a ”. Если цепочка заканчивается a 0 , то переходим в q 0 ; если заканчивается буквой “b ”, то переходим в q 2 ;

q 2 - идем вправо по цепочке букв “b ”, если цепочка заканчивается a 0 , то переходим в q 0 ; если заканчивается “a ”, то заменяем букву “a ” на “b ”, переходим в состояние q 3 (цепочку вида заменили на цепочку вида );

q 3 - идем влево по цепочке букв “b ” до ее левого конца. Если встретили a 0 или “a ”, то переходим в q 4 ;

q 4 - заменяем “b ” на “a ” и переходим в q 1 (цепочку вида заменяем на цепочку вида .

Задача 7

состояние q 1 - поиск правой (младшей) цифры числа;

состояние q 2 -умножение очередной цифры числа на 2 без прибавления 1 переноса;

состояние q 3 - умножение очередной цифры числа на 2 с прибавлением 1 переноса.

Машина Тьюринга для этой программы выглядит тривиально просто - в ней всего одно состояние. Такая машина Тьюринга выполняет следующие действия: стирает самый правый штрих, ищет разделитель (пустую ячейку) и в эту пустую ячейку помещает штрих, тем самым сформирована непрерывная последовательность штрихов длины n + m .

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

В этом случае их программа выглядит следующим образом:

состояние q 1 -поиск разделителя;

состояние q 2 -передвинули штрих;

состояние q 3 -проверка на конец (все ли штрихи передвинули).

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

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

Идея решения (условие останова). На ленте есть два исходных массива штрихов.

Штрихи начинаем стирать с левого конца массива m . И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n . Но прежде чем стереть правый штрих в массиве n , проверяем, единственный он (т.е. последний, который надо стереть) или нет.

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

Состояние q 1 - поиск разделителя между массивами штрихов при движении справа налево;

состояние q 2 - поиск левого штриха в массиве m ;

состояние q 3 - удаление левого штриха в массиве m ;

состояние q 4 - поиск разделителя при движении слева направо;

состояние q 5 - поиск правого штриха в массиве n ;

состояние q 6 - проверка единственности этого штриха в массиве n , т.е. определяем, был ли он последним;

состояние q 7 - если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.

При решении этой задачи следует обратить внимание на правильное выписывание алфавита:

A = {a 0 , 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А, Н, Е, Т}.

Состояние q 1 -поиск правого конца числа;

состояние q 2 -анализ младшей цифры числа; если она равна “0” или “5”, т.е. число делится на 5, то переход в состояние q 3 , иначе переход в состояние q 5 ;

состояние q 3 -запись буквы “Д” справа от слова на ленте;

состояние q 4 -запись буквы “А” справа от слова и останов машины;

состояние q 5 -запись буквы “Н” справа от слова;

состояние q 6 -запись буквы “Е” справа от слова;

состояние q 7 -запись буквы “Т” справа от слова и останов машины.

Свойства машины Тьюринга как алгоритма

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

Дискретность. Машина Тьюринга может перейти к (к + 1)-му шагу только после выполнения к- го шага, т.к. именно к- й шаг определяет, каким будет (к + 1)-й шаг.

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

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

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

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

ОТ РЕДАКЦИИ

Все приведенные в статье задачи можно решить просто в тетради, начертив информационную ленту и программу-таблицу. Но можно сделать этот процесс более увлекательным и наглядным: воспользоваться машинной реализацией - интерпретатором машины Поста и машины Тьюринга “Algo2000”, созданным Радиком Зартдиновым. Программа обладает интуитивно понятным интерфейсом, и требования у нее самые умеренные: компьютер IBM PC AT 486 и выше, наличие операционной системы Windows"95/98/NT.

Посмотрим в общих чертах, как работает “Algo2000”.

В меню программы выберем пункт Интерпретатор и укажем, с какой машиной мы хотим работать (в нашем случае это “машина Тьюринга”).

Перед нами появится поле машины Тьюринга.

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

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

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

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

Поле программы будет выглядеть так:

Формат команды в каждой ячейке - aKq. Здесь:
a - новое содержание текущей ячейки (новый символ внешнего алфавита, который заносится в текущую ячейку), K - команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп), q - новое внутреннее состояние машины Тьюринга.

Кнопка запустит программу. Если выполнение не было приостановлено, то оно всегда начинается с нулевого внутреннего состояния Q0.

Программу можно выполнить по шагам. Для этого нажмите на кнопку на панели инструментов (если кнопки не видны, нужно выбрать пункт меню Вид | Панель инструментов ) или выберите в главном меню Пуск | Пошагово . Если необходимо полностью прервать выполнение программы, то это можно сделать с помощью кнопки на панели инструментов или с помощью главного меню (Пуск | Прервать ). Пункт меню Скорость позволяет регулировать скорость выполнения программы.

Выполнение программы будет идти до тех пор, пока не встретится команда “Стоп” или не возникнет какая-нибудь ошибка.

При возникновении вопросов в ходе работы с программой-интерпретатором обращайтесь к справочному файлу Algo2000.hlp . Его, так же, как и саму программу “Algo2000”, можно найти на сайте газеты “Информатика” http://inf.1september.ru в разделе “Download”.

В гл. XII были разъяснены основные интуитивно очевидные требования, которые предъявляются к алгоритмам. Это требования детерминированности, массовости и применимости («целенаправленности») алгоритмов. Важно, что результат применения алгоритма совершенно не зависит от того, кто его использует. Человек, выполняющий алгоритм, должен действовать, «как машина», заботясь лишь о том, чтобы правильно выполнить предписания. Поэтому, естественно, возникает мысль: нельзя ли действительно поручить выполнение алгоритма машине?

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

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

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

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

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

Управляющее устройство имеет конечное число внутренних состояний и работает в дискретном времени . Входом управляющего устройства являются символы , выдаваемые считывающей и записывающей головкой, выходом - команды на действия головки: какой символ головка должна записать в соответствующей ячейке и куда передвинуться. Пусть в момент времени t считывающая и записывающая головка находилась напротив (считая слева) ячейки, в которой был записан символ , а управляющее устройство находилось в состоянии . Управляющее устройство в зависимости от состояния и входа выдает символ (в соответствии с которым головка стирает старый символ и печатает новый ), а затем один из символов П, Л или С («право»? «лево», "стоп"), в соответствии с которым головка передвигается на одну клетку вправо или влево, или остается на месте. После этого управляющее устройство переходит в новое состояние (также определяемое однозначно символами ).

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

Таблица 13.1

Таблица 13.2

Таблица 13.3

Таблица 13.3

Например, если таблица автомата есть табл. 13.1, таблица первого преобразователя - табл. 13.2, второго - табл. 13.3, то совмещенная таблица, целиком описывающая работу машины Тьюринга, имеет вид табл. 13.4.

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

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

2) вторым символом в клетке столбца этой строки является тот же символ (и никогда при );

3) третьим символом в каждой клетке этой строки является символ С (и никогда П или Л) (см. пример табл. 13.5).

Таблица 13.5

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

Таблица 13.6

Таблица 13.7

В дальнейшем для простоты будем предполагать, что алфавит символов состоит всего лишь из двух символов: «пустого» 0 и «непустого» 1.

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

1) Машина А (табл. 13.7). Если в начальный момент машина А находится в состоянии и воспринимает заполненную клетку, то она «отыскивает» на ленте первую пустую (т. е. заполненную символом 0) клетку справа от той, на которой находится головка, «печатает» там символ 1 и останавливается. Если же вначале головка находилась напротив пустой клетки, то машина ее «заполняет» и останавливается, не передвигая головку.

В табл. 13.8 и 13.9 приведены два варианта работы машины.

Таблица 13.8

Черта над соответствующей ячейкой ленты означает, что считывающая и записывающая головка находится в данный момент как раз напротив этой ячейки. Символ над чертой - состояние управляющего устройства в этот момент.

Таблица 13.9

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

2) Машина В (табл. 13.10). Эта машина имеет также лишь одно состояние (не считая состояния покоя). Она «стирает» единицу в той ячейке, где находится головка (если эта ячейка непуста), или в первой слева непустой ячейке, передвигает головку еще левее на ячейку и останавливается. Один вариант работы машины В приведен в табл. 13.11.

Таблица 13.10

Таблица 13.11

3) Машина С (табл. 13.12). Эта машина отыскивает первую после группы нулей группу единиц справа от начальной ячейки и останавливается около последней из этих единиц. Вариант работы машины С приведен в табл. 13.13.

Таблица 13.12,

Таблица 13.13

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

Таблица 13.14

4) Машина D (табл. 13.14). Эта машина заполняет первый промежуток справа между двумя группами единиц, оставляя всего одну незаполненную ячейку. Если головку машины в нулевой такт не помещать напротив пустой ячейки в состоянии , то сочетания и никогда не встретятся и в дальнейшем: состояние вообще никогда не повторится, а в машина может прийти лишь тогда, когда единица уже напечатана. Вариант работы машины приведен в табл. 13.15.