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

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

Ребята, мы вкладываем душу в сайт. Cпасибо за то,
что открываете эту красоту. Спасибо за вдохновение и мурашки.
Присоединяйтесь к нам в Facebook и ВКонтакте

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

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

Ранние годы

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

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

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

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

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

Кристофер Морком.

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

Но планам не суждено было сбыться: Кристофер Морком внезапно умер от туберкулеза. Для Алана это стало сильным ударом, он погрузился в длительную депрессию, однако нашел в себе силы поступить в Кембридж. Алан был убежден, что обязан был поступить, чтобы непременно совершить все те открытия, которые, по его словам, должен был сделать Кристофер. Уже учась в колледже, он попросил у миссис Морком фотографию сына, которую затем поставил на свой рабочий стол. «Теперь она стоит на моем столе, побуждая меня усиленно трудиться», - написал Алан матери своего умершего друга.

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

Научная карьера и Вторая мировая война

Реконструированная «Бомба».

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

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

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

В Принстоне Тьюринг проработал 2 года и получил степень доктора философии, однако, когда ему предложили самостоятельную должность, отказался и вернулся в Англию, в свою альма-матер. Шел 1938 год. Через год, 1 сентября 1939-го, началась Вторая мировая война.

Памятник Алану Тьюрингу в Блетчли-парке.

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

И. Гуд, коллега Алана Тьюринга

Через 3 дня после начала войны Алан Тьюринг пришел на работу в Блетчли-парк - секретное подразделение английской разведки. Стараниями группы ученых, которыми руководил Тьюринг, через полгода был взломан код «Энигмы» - шифровальной машины, которую немецкое командование использовало для передачи секретных сообщений.

В 1941 году Алан сделал предложение коллеге по Блетчли-парку Джоан Кларк, но спустя короткое время признался ей в своей гомосексуальности, и молодые люди отменили свадьбу.

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

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

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

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

Дом, где прошли последние годы Алана Тьюринга.

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

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

Более того, именно Тьюринга можно считать и создателем компьютерной музыки. В 1951 году созданная им машина была способна генерировать 3 мелодии, в числе которых и знаменитая «В настроении» Гленна Миллера. Однако об этом было напрочь забыто вплоть до 2016 года, когда была воссоздана запись 65-летней давности.Алану был предоставлен выбор между тюремным заключением и гормональной терапией - по сути, химической кастрацией. Он выбрал второе.

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

Памятник Алану Тьюрингу в Манчестере.

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

Эндрю Ходжес, автор биографической книги о Тьюринге, по которой был снят фильм Игра в имитацию» с Бенедиктом Камбербэтчем, пришел к выводу, что Алан разыграл сцену из диснеевской «Белоснежки» - своего любимого мультфильма. Кстати, есть теория, что логотип Apple появился именно благодаря яблоку, ставшему причиной смерти Тьюринга.

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

Так или иначе, жизнь одного из величайших ученых XX века оборвалась, когда ему не было и 42 лет. В 2009 году премьер-министр Великобритании принес публичные извинения за преследования Алана Тьюринга, а в 2013 году королева Елизавета II даровала ему посмертное помилование.

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

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

Машина Тьюринга является вычислительным устройством, состоящим из головки чтения/записи (или «сканера») с бумажной лентой, проходящей через него. Лента разделена на квадраты, каждый из которых несет одиночный символ - "0" или "1". Назначение механизма состоит в том, что он выступает и как средство для входа и выхода, и как рабочая память для хранения результатов промежуточных этапов вычислений. Из чего состоит устройство Каждая такая машина состоит из двух составляющих: Неограниченная лента. Она является бесконечной в обе стороны и разделена на ячейки. Автомат – управляемая программа, головка-сканер для считывания и записи данных. Она может находиться в каждый момент в одном из множества состояний.

Каждая машина связывает два конечных ряда данных: алфавит входящих символов A = {a0, a1, ..., am} и алфавит состояний Q = {q0, q1, ..., qp}. Состояние q0 называют пассивным. Считается, что устройство заканчивает свою работу, когда попадает именно на него. Состояние q1 называют начальным - машина начинает свои вычисления, находясь на старте в нем. Входное слово располагается на ленте по одной букве подряд в каждой позиции. С обеих сторон от него располагаются только пустые ячейки.

Как работает механизм

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

Свойства механизма

Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов: Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1. Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо. Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны. Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0. Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит. Функции машины Тьюринга В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В – слова в рамках двоичного кодового алфавита В={0.1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.-

Программа для устройства

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

Составляющие для вычислений

Чтобы построить машину Тьюринга для решения одной определенной задачи, необходимо определить для нее следующие параметры. Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них - а0 - должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = {0, 1, а0}. Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом. Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q={q1, q2...}. Одно из таких положений - q1 - должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.

Таблица переходов.

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

Алгоритм для автомата

Кареткой устройства Тьюринга во время работы управляет программа, которая во время каждого шага выполняет последовательность следующих действий: Запись символа внешнего алфавита в позицию, в том числе и пустого, осуществляя замену находившегося в ней, в том числе и пустого, элемента. Перемещение на один шаг-ячейку влево или же вправо. Изменение своего внутреннего состояния. Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: ai – элемент из выбранного алфавита A, направление сдвига каретки ("←” влево, "→” вправо, "точка” - отсутствие перемещения) и qk - новое состояние устройства. К примеру, команда 1 "←” q2 имеет значение "заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q2”.

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

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

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

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

A={a1, a2, a3, …, an} — внешний алфавит, служит для записи исходных данных

Q={q1, q2, q3,…, qm} — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = {a0,a1,…,an} (В нашем случае A={0, 1})

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

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

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

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

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

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «<» (влево) или «.» (на месте)
· новое состояние автомата

В приведенной выше таблице алфавит A ={0, 1, _} (содержит 3 символа), а внутренний алфавит Q={q1, q2, q3, q4, q0}, q0 — состояние, заставляющее каретку остановиться.

Рассмотрим несколько задач решением. Скачать машину Тьюринга Вы можете на сайте в разделе .

Задача 1. Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Теперь определимся с состояниями каретки. Я называю их — «желания каретки что-то сделать».

q1) Каретка должна пойти вправо: если видит 0 меняет его на 1 и остается в состоянии q1, если видит 1 — меняет его на 0 и остается в состоянии q1, если видит _ — ворачивается назад на 1 ячейку «желает что-то другое», т.е переходит в состояние q2. Запишем наши рассуждения в таблицу исполнителя. Синтаксис смотрите в справке к программе)

q2) Теперь опишем «желание каретки» q2. Мы должны вернуться в первоначальное положение. Для этого: если видим 1 оставляем ее и остаемся в состоянии q2 (с тем же желанием дойти до конца ряда символов); если видим 0 — оставляем его и продолжаем двигаться влево в состоянии q2; видим _ — сдвигается вправо на 1 ячейку. Вот вы оказались там, где требуется в условии задачи. переходим в состояние q0.

Посмотреть работу программы можно на видео:

Задача 2. Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0. Например:

Из 001101011101 получим 000000000000 1111111.

Как видите, семь единиц записались после данной последовательности, а на их местах стоят нолики.

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

q1) увидел 1 — исправь на нолик и перейди в другое состояние q2 (новое состояние вводится, чтобы каретка не поменяла на нули все единицы за один проход)

q2) ничего не менять, двигаться к концу последовательности

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

q4) проходим по написанным единицам, ничего не меняя. Как только доходим до пустой ячейки, разделяющей последовательность от единиц, переходим с новое состояние q5

q5) в этом состоянии идем начало последовательности, ничего не меняя. Доходим до пустой ячейки, разворачиваемся и переходим в состояние q1

Состояние q0 каретка примет в том случае, когда она пройдет в состоянии q1 до конца данной последовательности и встретит пустую ячейку.

Получим такую программу:

Работу Машины Тьюринга можете посмотреть на видео ниже.

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

Что собой представляет машина Тьюринга?

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

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

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

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

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

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

Пример работы машины Тьюринга

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

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

Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q 2 (команды которого совпадают с командами q 1 предыдущей программы).