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

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

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

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

==Устройство машины Тьюринга==

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

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

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

Содержание

Описание машины Тьюринга

Конкретная машина Тьюринга задается перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (H)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

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

Приведем пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Умножим с помощью МТ 3 на 2 в единичной системе:

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

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

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

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

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

На Машине Тьюринга можно имитировать машину Поста, нормальные алгорифмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

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

Варианты машины Тьюринга

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

Машина Тьюринга, работающая на полубесконечной ленте

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

Рассмотрим доказательство, приведенное Ю.Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, т.е. мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, т.е. определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причем будем считать, что символ “*” не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число ее состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна ее работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

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

Источник

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

Содержание

Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

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

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

Определение [ править ]

Определение машины [ править ]

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

Определение процесса работы [ править ]

Особо следует рассмотреть случай переходов по пробельному символу:

Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

Результат работы [ править ]

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

Примеры машин Тьюринга [ править ]

Прибавление единицы [ править ]

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

Проверка того, является ли слово палиндромом [ править ]

Варианты машины Тьюринга [ править ]

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

Многодорожечная машина Тьюринга [ править ]

Машина Тьюринга с полубесконечной лентой [ править ]

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

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

Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.[math]\triangleleft[/math]

Многоленточная машина Тьюринга [ править ]

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

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

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

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

Источник

Машина Тьюринга — одно из самых важных открытий XX века

Тема: Наука

В 30-е годы XX века английский математик Алан Тьюринг придумал такое странное устройство, которое теперь называют машиной Тьюринга.

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

Факт №1

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

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

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

Факт №2

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

Он с коллегами расшифровал коды немецкой армии — это известная история. Там использовались шифровальные машины «Энигма», которые пытались расшифровать сначала польские криптографы, а потом английские — при активном участии Тьюринга, и им это удалось.

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

Факт №3

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

Ее можно объяснить на таком примере: выпускалась игрушка Eternity — это такая коробочка, в которую уложены плитки, раскрашенные в разные цвета, но они раскрашены так, что видно, какие плитки можно прикладывать друг к другу (там рисунок на краях). Продаются они рассыпанными, и фирма, которая их изготовила, утверждает, что все это можно собрать в одну картинку внутри этой квадратной коробки (там 256 плиток) — то есть что изначально это была одна картинка, разрезанная на плитки.

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

Факт №4

В 2000-м году был публично объявлен «список проблем следующего тысячелетия», за которые Институт Клея обещает миллион долларов.

Так вот, первая проблема в этом списке — это проблема перебора, и она там заслуженно. Интересно в теории сложности вычислений то, что не только наличие какого-то алгоритма полезно практически, но, как ни странно, часто бывает полезно отсутствие алгоритма.

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

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

Когда кто-нибудь снимает деньги в банке, или в Интернете заходит на сайт с помощью SSL — используются системы криптографии, основанные на том, что быстро разлагать на множители числа нельзя. Если кто-нибудь в какой-то момент обнаружит, что разлагать можно, то, думаю, после этого будет экономический кризис, потому что вся банковская система рухнет, пока люди не заменят это чем-то другим (вообще без использования компьютеров или с какими-то новыми алгоритмами).

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

Факт №5

Что такое случайность? Это дело тонкое, вообще, существует ли случайность? Когда в каком-нибудь казино играют в рулетку — может ли наука предсказать, что там выпадет, и как нужно играть, чтобы выиграть, или это в принципе невозможно?

Федор Михайлович Достоевский твердо верил, что если быть хладнокровным и не волноваться во время игры, то можно выиграть, — он говорил, что, к сожалению, ему не удаётся быть хладнокровным, и поэтому он всё время проигрывал.

С другой стороны, теория вероятностей основана на том, что такой системы не существует, что последовательность бросания монеты в какой-нибудь игре, или последовательность выпадения красного и черного в рулетке, случайны и непредсказуемы. Но возникает вопрос, что такое случайность? Как определить, что это значит? Можем ли мы отделить случайное от неслучайного?

Сейчас вы видите две последовательности:

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

Я думаю, что сможете, и что более-менее всякий человек, который посмотрит на эту картинку, скажет, что первая последовательность получена не бросанием монеты, а просто чередованием 0 и 1, а вторая вполне может быть получена бросанием монеты.

Но спрашивается, в чём разница? Почему вы смотрите на эту картинку и уверены, что первая последовательность не может быть получена бросанием монеты? Почему монета не может выпасть сначала орлом, потом решкой, потом снова орлом… как это объяснить? Можно сказать так: вероятность того, что это случайно произойдет, очень мала, потому что такая последовательность всего одна, а всего последовательностей очень много. Но ведь то же самое можно сказать и про вторую последовательность, появление конкретно этой последовательности имеет ту же самую малую вероятность, что и для первой. Поэтому вопрос — в чём тут разница, чем первая последовательность «лучше» второй (менее случайна, чем вторая)?

Факт №6

Или другой парадоксальный пример. Представьте себе, как в XIX веке (это написано у Лотмана в его «Беседах о русской культуре») играли в карты. В отличие от нынешней ситуации, когда карты тасуют, тогда карты продавались уже перетасованными заранее.

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

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

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

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

Если, скажем, все карты идут в порядке возрастания их значения, или сначала идут все красные карты, а потом черные — такие комбинации, вроде бы, надо браковать. Но, с другой стороны, непонятно, чем они хуже других. Одной из попыток ответить на этот вопрос (60-е годы XX века) было понятие сложности, то, что сейчас называется колмогоровская сложность или алгоритмическая сложность.

Факт №7

Идея эта совсем простая — что первая из последовательностей

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

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

Можно сказать, что, если мы начнем «сжимать» последовательности каким-то архиватором, то вторая последовательность не сожмётся, а первая сожмется.

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

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

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

Вот это такая активно развивающаяся и, к сожалению, ещё не очень развитая область, и там, может быть, что-нибудь интересное в ближайшее время (или не в ближайшее время) откроют.

Если вы хотите получать больше статей, подобно этой, то кликните Recommend ниже.

Источник

• ← Что такое машина темперирующая машина
• Что такое машина феррари →