Который, позаимствовав идею у Эмиля Поста, придумал её, как считается, в 1936 году. Несмотря на довольно сложное формальное определение, идея в принципе проста. Чтобы понять её, давайте прогуляемся по страницам Википедии.

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

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

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

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

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

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

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

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

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

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

2. Ещё более похож на машину Тьюринга процесс исправления ошибок в ДНК - её репарация. Здесь ДНК-полимераза вместе с другими белками двигается по ленте ДНК и считывает обе её половинки (геномная ДНК, как известно, представляет собой две переплетенных нити, несущих одну и ту же информацию). Если информация в половинках не совпадает, ДНК-полимераза принимает одну из них за образец и «правит» другую.

Такая аналогия не нова, и в Википедии она тоже описана в статье «Молекулярный компьютер »:

Молекулярный компьютер

Биомолекулярные вычисления или молекулярные компьютеры или даже ДНК - или РНК -вычисления - все эти термины появились на стыке таких различных наук как молекулярная генетика и вычислительная техника.

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

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

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

Немножко фантастические перспективы только подогревают наше любопытство. Между тем, мы еще не всё выяснили относительно машины Тьюринга. Как вы помните, в статье из Википедии её назвали расширением конечного автомата. Что же это такое конечный автомат? На него, к счастью, даётся ссылка. Заходя по ней, узнаём, что:

Конечный автомат

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

С каждым определением мы всё больше вторгаемся в область чистой математики. Язык становится строже, появляются формальные определения, состоящие из математических символов. Если двигаться дальше, мы придём к теории алгоритмов и теории вычислимости. Путешествовать по страницам Википедии можно долго, но лучше запастись водой и едой, на случай забредания в пустыни аксиом и определений, или хотя бы надёжными ссылками на учебники по математике, например http://www.mccme.ru/free-books/ , или статьи журнала «Потенциал» ;)

Надеюсь, после этого объяснения вам стало немного яснее, что же такое машина Тьюринга?

Давайте вернёмся к истории этого термина.

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

Алан Тьюринг

Тьюринг, Алан Матисон (23 июня 1912 - 7 июня 1954) - английский математик, логик, криптограф, изобретатель Машины Тьюринга.

В самой статье больше про труды Тьюринга: помимо текста про машину Тьюринга, который мы еще приведем дальше, повествуется о том, что он работал над «проблемой зависания» (Забавно, не так ли? Компьютеров еще не было, и системы Windows тоже, а проблема зависания уже была.); героическая история про то, как Тьюринг взломал код «Энигмы» во время Второй Мировой Войны и тем самым спас Великобританию; факт о том, что он является основателем теории искусственного интеллекта, а также упоминание о знаменитом тесте Тьюринга. Сейчас этот тест уже не так часто используется как завязка научно-фантастического рассказа, однако проблема человеческого в машине всегда останется классикой, как и романы Айзека Азимова и Станислава Лема.

Несмотря на свою старомодность, тест Тьюринга всплыл неожиданным образом в современном мире общения по интернету. К примеру, можно встретить текст диалога двух пользователей ICQ, один из которых является «ботом», и задача - определить, какой именно. Или к Вам может постучаться незнакомый пользователь, возможно, ICQ-робот. Узнаете ли вы его? Изучая теорию, Вы, возможно, сумеете вовремя применить тест Тьюринга и не останетесь обмануты. Начать изучение можно с соответствующей статьи в Википедии, а затем пройтись по ссылкам, приводимым в конце статьи:

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

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

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

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

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

Тьюринг предложил тест, чтобы заменить бессмысленный, по его мнению, вопрос «может ли машина мыслить?» на более определённый.

Тьюринг предсказал, что компьютеры в конечном счёте пройдут его тест. Он считал, что к 2000 году, компьютер с памятью 1 миллиард бит (около 119 Мб) в ходе 5-минутного теста сможет обмануть судей в 30 % случаев. Это предсказание не сбылось. (Правда, на первом конкурсе Лебнера компьютерная программа «PC Therapist» на IBM PC 386 смогла ввести в заблуждение 5 судей из 10, но ей не засчитали результат, а в 1994 году конкурс усложнили.) Тьюринг также предсказал, что сочетание «мыслящая машина» не будет считаться оксюмороном , а обучение компьютеров будет играть важную роль в создании мощных компьютеров (с чем большинство современных исследователей согласны).

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

Ежегодно производится соревнование между разговаривающими программами, и наиболее человекоподобной, по мнению судей, присуждается приз Лебнера (Loebner). Есть дополнительный приз для программы, которая, по мнению судей, пройдёт тест Тьюринга. Этот приз ещё не присуждался.

Самый лучший результат в тесте Тьюринга показала программа A.L.I.C.E. выиграв тест 3 раза (в 2000, 2001 и 2004).

Ссылки

• Тьюринг А. М. Вычислительные машины и разум. // В сб.: Хофштадер Д., Деннет Д. Глаз разума. - Самара: Бахрах-М, 2003. - С. 47-59.
• Книга на английском: Roger Penrose «The Emperor’s New Mind».
• Статья Алана Тьюринга:
  • Alan Turing, «Computing Machinery and Intelligence», Mind, vol. LIX, no. 236, October 1950, pp. 433-460.
  • В сети:
• Статья Дж. Оппи (G. Oppy) и Д. Дави (D. Dowe) о тесте Тьюринга из Стэнфордской Философской Энциклопедии (на английском)
• «Turing Test: 50 Years Later» обзор 50-летней работы над тестом Тьюринга, с точки зрения 2000 г. (на английском).

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

Выдержка из статьи Википедии «Алан Тьюринг»

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

Алан Тьюринг высказал предположение (известное как Тезис Чёрча-Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

В статье под названием «Те́зис Чёрча-Тью́ринга» про него пишут так:

Те́зис Чёрча-Тью́ринга

Те́зис Чёрча-Тью́ринга - фундаментальное утверждение для многих областей науки, таких, как теория вычислимости , информатика , теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

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

Тезис Чёрча-Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».

Физический тезис Чёрча-Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга .

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

Универсальная машина Тьюринга

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

Формальное определение

Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т. п.; обозначим этот машинный алфавит как Σ 1 {\displaystyle \Sigma _{1}} . Тогда универсальной машиной Тьюринга U для класса машин с алфавитом Σ 2 {\displaystyle \Sigma _{2}} и k входными лентами называется машина Тьюринга с k+1 входной лентой и алфавитом Σ 1 ∪ Σ 2 {\displaystyle \Sigma _{1}\cup \Sigma _{2}} такая, что если подать на первые k лент входное значение, а на k+1 - правильно записанный код некоторой машины Тьюринга , то U выдаст тот же ответ, какой выдала бы на этих входных данных M 1 {\displaystyle M_{1}} , или будет работать бесконечно долго, если M 1 {\displaystyle M_{1}} на этих данных не остановится.

Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (то есть если исходная машина произвела t шагов, то универсальная произведёт не более ct 2 ). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана Тьюрингом в 1936-37 г.

Программная реализация на языке программирования Delphi достаточно проста. С одной из таких реализаций можно ознакомиться на сайте http://kleron.ucoz.ru/load/24-1-0-52 . Предусмотрена возможность загрузки и сохранения в файл Excel.

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

Вероятностная машина Тьюринга

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

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

Существует также альтернативное определение:

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

Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется классом BPP .

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

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

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

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

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

Скачать

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

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

• 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, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.

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

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

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

Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = {0, 1, а0}.

Непрерывную цепочку символов на ленте называют словом .

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

Внутренний алфавит . Конечное множество состояний каретки (автомата). Обозначается буквой Q={q1,q2...}. Одно из состояний - q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.

Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.

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

Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

Передвигаться на одну ячейку влево или вправо.

Менять свое внутреннее состояние.

Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра : символ ai из выбранного алфавита A, направление перемещения каретки ("←” - влево, "→” - вправо, "точка” - нет перемещения) и новое состояние автомата qk.

Например , команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.

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

Вопрос 28

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

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

	a 0	a 1	a 2
q 1	а 0 Пq 1	a 1 Пq 1	a 2 Лq 2
q 2	а 1 Пq 2	a 2 Нq 0	a 0 Нq 0

Вопрос 29

Машины Тьюринга с двумя выходами

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

Оказывается, что если заданы две машины Тьюринга T1 и Т2, которые допускают непересекающиеся множества слов Х1 и Х2 соответственно, то всегда можно построить машину Тьюринга T3 с двумя выходами, которая будет допускать Х1 и запрещать Х2. Эти машины Тьюринга будут нам полезны при рассмотрении вопроса о разрешимости.

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

Вопрос 30

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

Каждая лента бесконечна в обоих направлениях. При одном движении, зависящем от состояния конечного управления и сканируемого символа каждой из ленточных головок, машина может: 1) изменить состояние; 2) напечатать новый символ на каждой из сканируемых ячеек; 3) передвинуть каждую из ее ленточных головок независимо друг от друга на одну ячейку влево, вправо или оставить ее на том же месте.

Сначала входная цепочка имеется только на первой ленте, а все другие лен- ты пусты. Мы не будем определять это устройство более формально, предоставляя это читателю.

Теорема 6.2. Если язык L принимается многоленточной машиной Тьюринга, то он принимается одноленточной машиной Тьюринга. Доказательство. Пусть язык L принимается машиной Тьюринга T1 с k лентами. Построим одноленточную машину Тьюринга T2 с 2k дорожками, по две для каждой из лент машины T1. На одной дорожке записывается содержимое соответствующей ленты машины T1, а другая - пустая, за исключением маркера в ячейке, содержащей символ и сканируемой соответствующей головкой машины T1. Такое устройство для моделирования трех лент посредством одной иллюстрируется рис. 6.5. Конечное управление машины T2 запоминает, какие маркеры головок машины T1 находятся слева, а какие - справа от головки T2. Состояния машины T1 тоже запоминаются в конечном управлении машины T2.

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