В чем особенность машины алана тьюринга. Машина Тьюринга. Задачи и решения. Варианты машины Тьюринга

Ребята, мы вкладываем душу в сайт. 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 даровала ему посмертное помилование.

Введение

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

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

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

Основные положения машины Тьюринга

Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. Машина Тьюринга имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку влево или вправо в соседнюю ячейку. Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. Для каждой пары (состояние, обозреваемый символ) определена тройка (записываемый символ, движение головки, новое состояние). До начала работы машина Тьюринга находится в начальном состоянии, а головка чтения-записи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, машина записывает новый символ (может быть, тот же самый), сдвигает головку влево, вправо или остается на месте и переходит в новое состояние или остается в прежнем.

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

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

Рисунок 1 - Схема машина Тьюринга

Машина Тьюринга работает в некотором произвольном конечном алфавите A = {_, a1…an} - этот алфавит называется внешним. В нем выделяется специальный символ - _, называемый пустым знаком - его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj. При этом возможны сочетания:

1) аj = аi - означает, что в обозреваемой ячейке знак не изменился;

2) аi ? _, аj = _ - хранившийся в ячейке знак заменяется пустым, т.е. стирается;

3) аi = _, аj ? _ - пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;

4) аi ? аj ? _ - соответствует замене одного знака другим.

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

Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции. По этой причине команда сдвига ленты влево обозначается R (Right), сдвига вправо - L (Left), отсутствие сдвига - S (Stop). Мы будем говорить именно о сдвиге головки и считать R, L и S командами ее движения.

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

Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q1…qm, q0} , причем состояние q0 соответствует завершению работы, а q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (ai+1, qi+1, Di+1). Схема ЛУ машины Тьюринга изображена на рисунке 2.

Рисунок 2 - Схема ЛУ машины Тьюринга

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (ai), а на другой вход - знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (ai, qi) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (ai+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на переход в следующее состояние (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рисунке 3.

Рисунок 3 - Схема функционирования машины Тьюринга

В данной схеме отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты - она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (qi+1), а в D - команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.

Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qi aj > qi" aj" Dk, т.е. после обзора символа aj головкой в состоянии qi в ячейку записывается символ aj", головка переходит в состояние qi", а лента совершает движение Dk. Для каждой комбинации qi aj имеется ровно одно правило преобразования (правил нет только для q0, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов qi aj одну и только одну тройку выходных qi"aj"Dk - она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки - знаками внешнего алфавита. Если знаков внешнего алфавита n, а число состояний ЛУ m, то, очевидно, общее число правил преобразования составит nЧm.

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

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

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

В зависимости от начальной конфигурации возможны два варианта развития событий:

1) после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;

2) остановки не происходит.

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

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

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

Что такое машина Тьюринга

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

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

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

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

Множества A = {a0, a1, ..., ai} и Q = {q0, q1, ..., qj} являются конечными, a0 – символ пустой ячейки, q1 – начальное состояние, q0 – пассивное состояния, условие выхода машины из цикла.

Создадим таблицу для реализации алгоритма Тьюринга:

Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.

Пусть наша лента выглядит так:

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

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

Зачем это программисту

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

• нормальным алгоритмом Маркова;
• лямбда-вычислениями;
• языком программирования Brainfuck.

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

Полнота по Тьюрингу

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

Тест по Тьюрингу

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

Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.

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

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

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

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

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

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

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 до конца данной последовательности и встретит пустую ячейку.

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

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

Машина Тьюринга - одно из самых интригующих и захватывающих интеллектуальных открытий 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”.