Когда была изобретена машина тьюринга. Машины тьюринга. Что это и кто создал
До сих пор нам было удобно ссылаться на программистский опыт , говоря об алгоритмах, программах, интерпретаторах, пошаговом выполнении и т.д. Это позволяло нам игнорировать детали построения тех или иных алгоритмов под тем предлогом, что читатель их легко восстановит (или хотя бы поверит все-таки не каждый читатель в своей жизни писал интерпретатор паскаля на паскале).
Но в некоторых случаях этого недостаточно. Пусть, например, мы хотим доказать алгоритмическую неразрешимость какой-то задачи, в определении которой ничего не говорится о программах (в этом разделе, например, мы докажем неразрешимость проблемы равенства слов в полугруппах , заданных образующими и соотношениями). Это обычно делается так. Мы показываем, что проблема остановки сводится к этой задаче. Для этого мы моделируем работу произвольного алгоритма в терминах рассматриваемой задачи (что это значит, будет видно из приводимого ниже примера). При этом нам важно, чтобы определение алгоритма было как можно проще.
Таким образом, наш план таков. Мы опишем довольно просто определяемый класс машин (его можно выбирать по-разному, мы будем использовать так называемые машины Тьюринга), затем объявим, что всякая вычислимая функция может быть вычислена на такой машине, а затем покажем, что вопрос об остановке машины Тьюринга можно свести к вопросу о равенстве слов в полугруппе.
Другая причина, по которой важны простые вычислительные модели (таких моделей много разные виды машин Тьюринга, адресные машины и т.п.), связана с теорией сложности вычислений, когда нас начинает интересовать время выполнения программ. Но этот вопрос выходит за рамки классической теории алгоритмов.
Машины Тьюринга: определение
Машина Тьюринга имеет бесконечную в обе стороны ленту , разделенную на квадратики (ячейки ). В каждой ячейке может быть записан некоторый символ из фиксированного (для данной машины) конечного множества , называемого алфавитом данной машины. Один из символов алфавита выделен и называется " пробелом" предполагается, что изначально вся лента пуста, то есть заполнена пробелами.
Машина Тьюринга может менять содержимое ленты с помощью специальной читающей и пишущей головки , которая движется вдоль ленты. В каждый момент головка находится в одной из ячеек. Машина Тьюринга получает от головки информацию о том, какой символ та видит, и в зависимости от этого (и от своего внутреннего состояния) решает, что делать, то есть какой символ записать в текущей ячейке и куда сдвинуться после этого (налево, направо или остаться на месте). При этом также меняется внутреннее состояние машины (мы предполагаем, что машина не считая ленты имеет конечную память , то есть конечное число внутренних состояний). Еще надо договориться, с чего мы начинаем и когда кончаем работу.
Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:
Таблица переходов устроена следующим образом: для каждой пары указана тройка . Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x {-1,0,1} , определенная на тех парах, в которых состояние не является заключительным.
Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация , складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z -> A ), текущей позиции головки (некоторое целое число ) и текущего состояния машины (элемент S ). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом, если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово , которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1 ).
Таким образом, любая машина Тьюринга задает некоторую частичную функцию на двоичных словах. Все такие функции естественно назвать вычислимыми на машинах Тьюринга .
Машины Тьюринга: обсуждение
Разумеется, наше определение содержит много конкретных деталей, которые можно было бы изменить. Например, лента может быть бесконечной только в одну сторону. Можно придать машине две ленты. Можно считать, что машина может либо написать новый символ, либо сдвинуться, но не то и другое вместе. Можно ограничить алфавит , считая, скажем, что в нем должно быть ровно 10 символов. Можно потребовать, чтобы в конце на ленте ничего не было, кроме результата работы (остальные клетки должны быть пусты). Все перечисленные и многие другие изменения не меняют класса вычислимых на машинах Тьюринга функций. Конечно, есть и небезобидные изменения. Например, если запретить машине двигаться налево, то это радикально поменяет дело по существу лента станет бесполезной, так как к старым записям уже нельзя будет вернуться.
Как понять, какие изменения безобидны, а какие нет? Видимо, тут необходим некоторый опыт практического программирования на машинах Тьюринга, хотя бы небольшой. После этого уже можно представлять себе возможности машины, не выписывая программы полностью, а руководствуясь лишь приблизительным описанием. В качестве примера опишем машину, которая удваивает входное слово (изготавливает слово XX , если на входе было слово X ).
Если машина видит пробел ( входное слово пусто), она кончает работу. Если нет, она запоминает текущий символ и ставит пометку (в алфавите помимо символов 0 и 1 будут еще их " помеченные варианты" и ). Затем она движется направо до пустой клетки, после чего пишет там копию запомненного символа. Затем она движется налево до пометки; уткнувшись в пометку, отходит назад и запоминает следующий символ и так далее, пока не скопирует все слово .
Имея некоторый опыт , можно за всеми этими фразами видеть конкретные куски программы для машины Тьюринга. Например, слова " запоминает символ и движется направо" означают, что есть две группы состояний, одна для ситуации, когда запомнен нуль, другая когда запомнена единица , и внутри каждой группы запрограммировано движение направо до первой пустой клетки.
Имея еще чуть больше опыта, можно понять, что в этом описании есть ошибка не предусмотрен механизм остановки, когда все слово будет скопировано, поскольку копии символов ничем не отличаются от символов исходного слова. Ясно и то, как ошибку исправить надо в качестве копий писать специальные символы и , а на последнем этапе все пометки удалить.
77 . Покажите, что функция " обращение", переворачивающая слово задом наперед, вычислима на машине Тьюринга.
Другой пример неформального рассуждения: объясним, почему можно не использовать дополнительных символов, кроме 0 , 1 и пустого символа. Пусть есть машина с большим алфавитом из N символов. Построим новую машину, которая будет моделировать работу старой, но каждой клетке старой будет соответствовать блок из k клеток новой. Размер блока (число k ) будет фиксирован так, чтобы внутри блока можно было бы закодировать нулями и единицами все символы большого алфавита. Исходные символы 0 , 1 и пустой будем кодировать как 0 , за которым идут (k-1) пустых символов, 1 , за которым идут (k-1) пустых символов, и группу из k пустых символов. Для начала надо раздвинуть буквы входного слова на расстояние k , что можно сделать без дополнительных символов (дойдя до крайней буквы, отодвигаем ее, затем дойдя до следующей, отодвигаем ее и крайнюю и так далее); надо только понимать, что можно идентифицировать конец слова как позицию, за которой следует более k пустых символов. Ясно, что в этом процессе мы должны хранить в памяти некоторый конечный объем информации, так что это возможно. После этого уже можно моделировать работу исходной машины по шагам, и для этого тоже достаточно конечной памяти (е конечного числа состояний), так как нам важна только небольшая окрестность головки моделируемой машины. Наконец, надо сжать результат обратно.
В заключение обсуждения приведем обещанный выше аргумент в пользу того, что любая вычислимая функция вычислима на машине Тьюринга. Пусть есть функция , которую человек умеет вычислять. При этом, он, естественно, должен использовать карандаш и бумагу, так как количество информации , которое он может хранить " в уме", ограничено. Будем считать, что он пишет на отдельных листах бумаги. Помимо текущего листа, есть стопка бумаг справа и стопка слева; в любую из них можно положить текущий лист , завершив с ним работу, а из другой стопки взять следующий. У человека есть карандаш и ластик. Поскольку очень мелкие буквы не видны, число отчетливо различимых состояний листа конечно, и можно считать, что в каждый момент на листе записана одна буква из некоторого конечного (хотя и весьма большого) алфавита. Человек тоже имеет конечную память , так что его состояние есть элемент некоторого конечного множества . При этом можно составить некоторую таблицу, в которой записано, чем кончится его работа над листом с данным содержимым, начатая в данном состоянии (что будет на листе, в каком состоянии будет человек и из какой пачки будет взят следующий лист ). Теперь уже видно, что действия человека как раз соответствуют работе машины Тьюринга с большим (но конечным) алфавитом и большим (но конечным) числом внутренних состояний.
Ребята, мы вкладываем душу в сайт. 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 году А. Тьюрингом для уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста и нормальным алгорифмам Маркова .
Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита 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 , находится команда, состоящая из трех частей:
- символ из алфавита A ;
- направление перемещения: > (вправо),
- новое состояние автомата
Новости
- Фалина И.Н. Тема «Машина Тьюринга» в школьном курсе информатики (inf.1september.ru).
- Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru).
- Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач , М.: МГУ, 2006.
- Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
- Соловьев А. Дискретная математика без формул (lib.rus.ec)
- Ершов С.С. Элементы теории алгоритмов , Челябинск, Издательский центр ЮУрГУ, 2009.
- Варпаховский Ф.Л. Элементы теории алгоритмов , М: Просвещение, 1970.
- Верещагин Н.К., Шень А. Вычислимые функции , М: МЦНМО, 1999.
Что с этим делать?
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.
С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.
В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.
В таблице в нижней части окна набирается программа. В первом столбце записаны символы алфавита, он заполняется автоматически. В первой строке перечисляются все возможные состояния. Добавить и удалить столбцы таблицы (состояния) можно с помощью кнопок, расположенных над таблицей.
При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.
Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость .
Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер.
Если вы заметили ошибку или у вас есть предложения, замечания, жалобы, просьбы и заявления, пишите .
Технические требования
Программа работает под управлением операционных систем линейки Windows на любых современных компьютерах.
Лицензия
Программа является бесплатной для некоммерческого использования. Исходные тексты программы не распространяются.
Программа поставляется «as is », то есть, автор не несет никакой ответственности за всевозможные последствия ее использования, включая моральные и материальные потери, вывод оборудования из строя, физические и душевные травмы.
При размещении программы на других веб-сайтах ссылка на первоисточник обязательна.
- 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
- 2) распространение неполных или измененных материалов;
- 3) включение материалов в сборники на любых носителях информации;
- 4) получение коммерческой выгоды от продажи или другого использования материалов.
Скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.
Скачать
После распаковки архива программа находится в работоспособном состоянии и не требует никаких дополнительных установок.
Маши́на Тью́ринга (МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма .
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча - Тьюринга , способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга .
Энциклопедичный YouTube
1 / 5
✪ 09 - Введение в алгоритмы. Машина Тьюринга
✪ Машина Тьюринга - Александр Шень
✪ Лекция 20: Машина Тьюринга
✪ Машина Тьюринга. Пример работы
✪ 16 - Вычислимость. Машины Тьюринга. Мотивировка и примеры
Субтитры
Устройство машины Тьюринга
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки , и управляющее устройство (также называется головкой записи-чтения (ГЗЧ )), способное находиться в одном из множества состояний . Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода , которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные , и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной , если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ - состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной .
Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q i a j →q i1 a j1 d k (если головка находится в состоянии q i , а в обозреваемой ячейке записана буква a j , то головка переходит в состояние q i1 , в ячейку вместо a j записывается a j1 , головка делает движение d k , которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Пример машины Тьюринга
Приведём пример МТ для умножения чисел в унарной системе счисления . Запись правила «q i a j →q i1 a j1 R/L/N» следует понимать так: q i - состояние при котором выполняется это правило, a j - данные в ячейке, в которой находится головка, q i1 - состояние в которое нужно перейти, a j1 - что нужно записать в ячейку, R/L/N - команда на перемещение.
Машина работает по следующему набору правил:
q 0 | q 1 | q 2 | q 3 | q 4 | q 5 | q 6 | q 7 | q 8 | |
---|---|---|---|---|---|---|---|---|---|
1 | q 0 1→q 0 1R | q 1 1→q 2 aR | q 2 1→q 2 1L | q 3 1 → q 4 aR | q 4 1→q 4 1R | q 7 1→q 2 aR | |||
× | q 0 ×→q 1 ×R | q 2 ×→q 3 ×L | q 4 ×→q 4 ×R | q 6 ×→q 7 ×R | q 8 ×→q 9 ×N | ||||
= | q 2 =→q 2 =L | q 4 =→q 4 =R | q 7 =→q 8 =L | ||||||
a | q 2 a→q 2 aL | q 3 a→q 3 aL | q 4 a→q 4 aR | q 6 a→q 6 1R | q 7 a→q 7 aR | q 8 a→q 8 1L | |||
* | q 0 *→q 0 *R | q 3 *→q 6 *R | q 4 *→q 5 1R | ||||||
q 5 →q 2 *L |
Описание состояний:
Начало | |
q 0 | начальное состояние. Ищем «x» справа. При нахождении переходим в состояние q1 |
---|---|
q 1 | заменяем «1» на «а» и переходим в состояние q2 |
Переносим все «1» из первого числа в результат | |
q 2 | ищем «х» слева. При нахождении переходим в состояние q3 |
q 3 | ищем «1» слева, заменяем её на «а» и переходим в состояние q4.
В случае если «1» закончились, находим «*» и переходим в состояние q6 |
q 4 | переходим в конец (ищем «*» справа), заменяем «*» на «1» и переходим в состояние q5 |
q 5 | добавляем «*» в конец и переходим в состояние q2 |
Обрабатываем каждый разряд второго числа | |
q 6 | ищем «х» справа и переходим в состояние q7. Пока ищем заменяем «а» на «1» |
q 7 | ищем «1» или «=» справа
при нахождении «1» заменяем его на «а» и переходим в состояние q2 при нахождении «=» переходим в состояние q8 |
Конец | |
q 8 | ищем «х» слева. При нахождении переходим в состояние q9. Пока ищем заменяем «а» на «1» |
q 9 | терминальное состояние (остановка алгоритма) |
Умножим с помощью МТ 3 на 2 в единичной системе. В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Начало. Находимся в состоянии q 0 , ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.
1-й шаг. Смотрим по таблице правил что будет делать машина, находясь в состоянии q 0 и над символом «*». Это правило из 1-го столбца 5-й строки - q 0 *→q 0 *R. Это значит, что мы переходим в состояние q 0 (то есть не меняем его), символ станет «*» (то есть не изменится) и смещаемся по введённому нами тексту «*111x11=*» вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q 0 1 (1-й столбец 1-я строка) обрабатывается правилом q 0 1→q 0 1R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ «х». И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.
Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву «а», и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на «а» и дописывания такого же количества единиц в конце строки (слева от крайнего правого «*»). Затем меняем все «а» до знака умножения «х» обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой «а» и снова переносим единицы. Когда до знака «=» не окажется единиц - значит умножение завершено.
Полнота по Тьюрингу
Можно сказать, что машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам преобразует входные данные с помощью последовательности элементарных действий .
Элементарность действий заключается в том, что действие меняет лишь небольшой кусочек данных в памяти (в случае машины Тьюринга - лишь одну ячейку), и число возможных действий конечно. Несмотря на простоту машины Тьюринга, на ней можно вычислить всё, что можно вычислить на любой другой машине, осуществляющей вычисления с помощью последовательности элементарных действий. Это свойство называется полнотой .
Один из естественных способов доказательства того, что алгоритмы вычисления, которые можно реализовать на одной машине, можно реализовать и на другой, - это имитация первой машины на второй.
Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины D {\displaystyle D} и входные данные X {\displaystyle X} , которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные X {\displaystyle X} .
Как было сказано, на машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
На машине Тьюринга можно имитировать машину Поста , нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью (суммарная память компьютера - оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. - может быть очень большой, но, тем не менее, всегда конечна).
Варианты машины Тьюринга
Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.
Машина Тьюринга, работающая на полубесконечной ленте
В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте (то есть на ленте, бесконечной в одну сторону).
Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых, произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:
Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.
Двумерные машины Тьюринга
- Муравей Лэнгтона
См. также
- JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата
Если вы не учились профессии программиста в вузе или не ходили в специальную школу, то, возможно «Машина Тьюринга» для вас просто дешифратор из курса истории или фильма «Игра в имитацию». В действительности всё немного сложнее, любому уважающему себя программисту необходимо знать и понимать, что это такое.
Что такое машина Тьюринга
Для того, чтобы представить простейшую машину Тьюринга, взглянем на её художественную реализацию:
Это бесконечная лента, не имеющая ни начала, ни конца, поделённая на ячейки. Для работы с ней мы используем некое управляющее устройство (автомат), для визуализации выбрана каретка. В каждый момент времени она имеет состояние qj и считывает содержимое ячейки ai. О том, что происходит в остальной части ленты, каретка не знает, соответственно оперировать она может только текущими данными. Всего возможно три типа действий, зависящий от этой композиции:
- выполнить сдвиг на соседнюю ячейку;
- записать в текущую новое содержимое;
- изменить состояния.
Что-то похожее реализовано в электронных таблицах: там тоже условно неограниченное поле, вы можете изменить значение ячейки, изменить действие или перейти на другую ячейку.
Множества A = {a0, a1, ..., ai} и Q = {q0, q1, ..., qj} являются конечными, a0 – символ пустой ячейки, q1 – начальное состояние, q0 – пассивное состояния, условие выхода машины из цикла.
Создадим таблицу для реализации алгоритма Тьюринга:
Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.
Пусть наша лента выглядит так:
Начальное положение – крайняя правая ячейка, остановка – в пустой клетке. Догадались как она будет выглядеть после завершения алгоритма?
На указанном примере всё выглядит довольно просто. Можете поиграть с увеличением алфавита, преобразованием состояний, помещением начальной позиции не в крайнюю позиции, условиями выхода из цикла и т.д. Фактически, практически любую задачу преобразования можно решить с помощью машины Тьюринга.
Зачем это программисту
Машина Тьюринга позволяет размять мозги и взглянуть на решение задачи иначе. В конечном счёте, с той же целью следует познакомиться с:
- нормальным алгоритмом Маркова;
- лямбда-вычислениями;
- языком программирования Brainfuck.
Но машина Тьюринга – базовая теория алгоритмов, которая помогает думать не столько о средствах языка, сколько о различных путях решения задачи. Для профессионального роста – это необходимый навык.
Полнота по Тьюрингу
Ещё один важный вопрос, связанный с именем известного математика. На форумах и в статьях вы неоднократно могли видеть выражение «полный\не полный язык программирования по Тьюрингу». Ответ на вопрос «что это означает?» возвращает нас к описанной выше теории. Как уже было сказано, машина Тьюринга позволяет выполнить любое преобразование, соответственно, вы можете реализовать на ней абсолютно любой алгоритм или функцию. То же самое относится и к языкам. Если с его помощью вы можете реализовать любой заданный алгоритм – он тьюринг-полный. Если в дело вступают ограничения синтаксиса или любые физические – не полный.
Тест по Тьюрингу
Последний раздел никак не связан с машиной. Тест Тьюринга – игра, в ходе которой человек с помощью текстовых сообщений взаимодействует одновременно с машиной и другим человеком, не видя их. Задача машины – ввести участника в заблуждение.
Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.
Алан Тьюринг остался в истории не только человеком, совершившим важное открытие во время Второй мировой войны, но и подаривший миру несколько фундаментальных теорий, которыми пользуется человечество до сих пор.