Машина тьюринга это компьютер или нет
23 июня 1912 года родился Алан Тьюринг – английский математик, логик, криптограф. Он внес большой вклад в развитие информатики , в его честь названа самая престижная в мире награда в области информатики – Премия Тьюринга . Во время Второй мировой Тьюринг активно занимался криптоанализом , в том числе криптоанализом немецкого шифратора Enigma (на портале Эрудит.Онлайн есть конкурс по криптографии «Энигма» ).
В этой статье остановимся подробнее на машине Тьюринга и попытаемся объяснить ее работу максимально простым языком.
Машина Тьюринга
Машина Тьюринга – это абстрактная вычислительная машина . Если совсем просто, то машина Тьюринга – это воображаемый компьютер с бесконечной памятью.
Формально машина состоит из бесконечной ленты и управляющего устройства , которое может считывать и записывать символы в ячейки ленты. Управляющее устройство может двигаться влево и вправо по ленте.
Машина Тьюринга
Так как же нам распознавать нерегулярные шаблоны? Существует теоретическое устройство, подобное конечному автомату и называемое машиной Тьюринга (Turing Machine). Как и у машины с конечным числом состояний, у него имеется бумажная лента, с которой оно считывает информацию. Однако, машина Тьюринга также способна записывать и стирать данные на ленте. Полное объяснение принципов этого устройства займёт больше места, чем у нас здесь имеется, поэтому я обозначу лишь несколько важных моментов, относящихся к нашей дискуссии о машинах с конечным числом состояний и регулярных выражениях.
Машина Тьюринга вычислительно полна, и всё, что в принципе может быть вычислено, может быть вычислено с помощью машины Тьюринга. А благодаря способности записывать данные на ленту с такой же лёгкостью, как и считывать их с ленты, она не ограничена конечным числом состояний. Бумажную ленту можно представить, как имеющую бесконечную длину. Очевидно, что современные компьютеры не обладают бесконечным количеством памяти, однако, они имеют её достаточно, чтобы вы не вышли за предел для тех типов задач, которые они способны обработать.
Машина Тьюринга предоставляет нам воображаемое механическое устройство, позволяющее визуализировать и понять, как работает вычислительный процесс. Это особенно полезно для понимания пределов вычислений. Если это интересно, то в будущем я могу написать отдельную статью о машине Тьюринга.
Как работает машина Тьюринга?
Шаг машины можно представить так:
- Управляющее устройство , указывающее на конкретную ячейку на ленте, считывает значение в этой ячейке.
- По правилам, которые заданы заранее для решения задачи, управляющее устройство может изменить символ в ячейке (а может и не менять), а затем остаться на месте или сдвинуться на соседнюю ячейку вправо или влево. Также может измениться состояние управляющего устройства (а может и остаться прежним).
У управляющего устройства есть отдельный параметр, который называется состоянием . Набор таких состояний задается для каждой конкретной программы свой, но обязательно в этом наборе есть начальное состояние (в котором машина начинает работать) и конечные состояния (когда мы считаем, что программа завершилась, и машина останавливается). Эти состояния меняются в соответствии с правилами , которые заранее заданы.
Недетерминированная машина с конечным числом состояний (Nondeterministic Finite State Machine)
Недетерминированные машины с конечным числом состояний, или недетерминированные конечные автоматы (nondeterministic finite automaton, NFA) - это конечные автоматы, у которых входной сигнал для данного состояния может вести более чем в одно последующее состояние. Допустим, например, что мы хотим построить FSM, которая способна распознавать строки букв, начинающиеся с буквы a, за которой следует нуль или более букв b или нуль или более букв c. Условие останова - следующая буква алфавита на входе. Допустимыми строками будут:
Итак, надо распознать букву a с последующим нулём или более одинаковых букв b или c и с замыкающей следующей буквой алфавита. Самый простой способ отобразить этот алгоритм с помощью машины с конечным числом состояний представлен ниже. Финальное состояние t означает, что строка была принята целиком и соответствует шаблону.
Видите проблему? Находясь в начальной точке s мы понятия не имеем, какой из путей выбрать. Если мы прочли только букву a, то мы ещё не знаем, идти нам в q или в r. Существует несколько способов решить эту задачу. Первый из них - откат. Вы просто перебираете все возможные пути и игнорируете или возвращаетесь назад по тем из них, где решение заходит в тупик.
На этом принципе основан алгоритм большинства шахматных программ. Они просматривают все возможности всех возможных ходов на данном этапе и выбирают ту стратегию, которая в данный момент даёт максимальное преимущество над противником.
Другой путь - это преобразовать недетерминированную машину с конечным числом состояний в детерминированную. Существование алгоритма преобразования любой недетерминированного автомата в детерминированный является одним из интереснейших атрибутов NFA. Однако, часто это весьма сложный процесс. К счастью для нас, пример выше достаточно прост. Фактически, всё преобразование можно провести в уме, не прибегая к помощи формального алгоритма.
Машина ниже - детерминированная версия недетерминированной машины на предыдущем рисунке. Здесь конечные состояния t или v достижимы для любой принятой машиной строки.
Недетерминированная модель имеет четыре состояния и шесть переходов. Детерминированная модель - шесть состояний, десять переходов и два возможных завершения. Разница невелика, однако мы знаем, что сложность имеет свойство расти по экспоненте. И адекватных размеров недетерминированная машина способна вырасти в просто огромную детерминированную.
Регулярные выражения
Если вы когда-нибудь занимались любым видом программирования, то вы почти наверняка сталкивались с регулярными выражениями (regular expressions). Регулярные выражения и машины с конечным числом состояний функционально эквивалентны. Всё, что можно допустить для (или связать с) регулярным выражением, можно допустить для (или связать с) конечным автоматом. Например, шаблон, который мы разбирали выше, можно связать с
Регулярные выражения и машины с конечным числом состояний также имеют и одинаковые ограничения. Точнее, они могут принимать или связывать шаблоны, для обработки которых требуется конечный размер памяти. Так какие же типы шаблонов для них недопустимы? Предположим, что мы хотим найти только строки, состоящие из a и b, где за каким-то количеством букв a следует такое же число букв b. Другими словами, за n a следует n b, где n - какое-то число. Примером могут послужить строки:
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
На первый взгляд это выглядит детской задачей для машины с конечным числом состояний. Проблема в том, что вы или быстро выйдете за пределы заданного числа состояний, или вам придётся допустить бесконечное их количество - и в этот момент ваше устройство перестаёт быть машиной с конечным числом состояний. Допустим, вы создаёте конечный автомат, который может принять двадцать a и следующие за ними двадцать b. Он будет прекрасно работать до те пор, пока на вход не придёт строка из двадцати одной a и двадцати одной b. И тогда вам придётся переписывать вашу машину для обработки более длинных строк. Для любой строки, которую вы можете распознать, всегда есть ещё одна, которая будет лишь немного длиннее, но которую ваша машина уже не способна обработать, не выходя за пределы памяти.
Это положение известно как лемма о накачке для регулярных языков. Её основная мысль: если ваш шаблон имеет блок, который может быть повторён более, чем один раз, то этот шаблон не является регулярным. Другими словами, ни регулярные выражения, ни машины с конечным числом состояний не могут быть сконструированы так, чтобы распознавать все строки, которые можно связать с шаблоном.
Если вы посмотрите внимательнее, то заметите, что тип шаблона, в котором каждая a связана с b, выглядит очень похоже на HTML, где внутри любой пары тэгов можно заключить произвольное количество других пар тэгов. Вот почему вы можете использовать регулярное выражение или машину с конечным числом состояний для распознавания, содержит ли HTML-страница конкретные html , head и body элементы в правильном порядке, но не можете использовать регулярное выражение, чтобы сказать, является ли HTML-страница целиком корректной или нет. HTML - не регулярный шаблон.
Программа для машины Тьюринга
Программа для машины Тьюринга формируется как таблицы, в которых в первой строчке и столбце находятся знаки внешнего алфавита и набор допустимых внутренних состояний автомата, то есть внутренний алфавит. Данные в таблице, по сути, это команды, которые должна исполнять машина Тьюринга. Разрешение задачи выполняется по следующим правилам. Символ, принятый сканером из ячейки, над которой он располагается в текущий момент, и определённое внутреннее состояние сканера автомата определяют, какую команду требуется исполнить. А именно, это команда, расположенная в таблице, и находящаяся в точке пересечения знаков внутреннего и внешнего алфавита.
В 30-е годы XX века английский математик Алан Тьюринг придумал такое странное устройство, которое теперь называют машиной Тьюринга.
Идея его была в том, чтобы придумать устройство, абстрактную машину, которая может делать все, что вообще могут делать машины. Он был не единственным в этот момент, другие люди тоже в других терминах определяли похожие вещи, но в гораздо более абстрактных терминах, по крайней мере, в их работах конкретного механизма работы машины не было.
Оказалось же, что это одно из самых важных открытий XX века. То, что сейчас в разных устройствах — скажем, в телевизоре и в стиральной машине, — может использоваться одна и та же микросхема процессора, — это воплощение одной из идей Тьюринга.
И то, что одна и та же программа может использоваться в самых разных компьютерах, работать с самой разной аппаратурой и выглядеть одинаково, это тоже его идея. Тогда это называлось идеей хранимой программы (программа хранится в памяти и определяет поведение машины), и ещё была идея универсальной машины, — есть машина, которая может делать все, что может делать любая другая машина.
Если бы не Тьюринг, наверно, это придумал бы кто-то другой, он не был единственным, кто над этим работал, но так или иначе такое абстрактное теоретическое устройство оказалось одним из самых важных изобретений в XX веке.
Интересно, что потом Тьюринг, когда настали трудные времена, не только занимался теорией, но и практически участвовал в разных важных проектах.
Он с коллегами расшифровал коды немецкой армии — это известная история. Там использовались шифровальные машины «Энигма», которые пытались расшифровать сначала польские криптографы, а потом английские — при активном участии Тьюринга, и им это удалось.
А после войны Тьюринг уже строил реальную электронную вычислительную машину. Хотя прямой связи с его теоретическими работами не было, но явно это было продолжением той же самой деятельности. Так что хорошая теория — вещь очень практичная, и не надо бояться того, что теоретические работы окажутся бесполезными.
Сейчас это большая наука, которая называется теория сложности вычислений, в ней много всего интересного открыли, но есть самая главная проблема, которая называется проблема перебора, и которая до сих пор не решена.
Ее можно объяснить на таком примере: выпускалась игрушка Eternity — это такая коробочка, в которую уложены плитки, раскрашенные в разные цвета, но они раскрашены так, что видно, какие плитки можно прикладывать друг к другу (там рисунок на краях). Продаются они рассыпанными, и фирма, которая их изготовила, утверждает, что все это можно собрать в одну картинку внутри этой квадратной коробки (там 256 плиток) — то есть что изначально это была одна картинка, разрезанная на плитки.
По современным представлениям, машины такие задачи за обозримое время решать не могут, никакого способа, кроме как перебирать все варианты (а их очень много) сейчас не известно. Но, с другой стороны, никто этого не может и доказать. Это и называется проблемой перебора — доказать, что такой полный перебор каких-то объектов нельзя заменить никаким более коротким вычислением.
В 2000-м году был публично объявлен «список проблем следующего тысячелетия», за которые Институт Клея обещает миллион долларов.
Так вот, первая проблема в этом списке — это проблема перебора, и она там заслуженно. Интересно в теории сложности вычислений то, что не только наличие какого-то алгоритма полезно практически, но, как ни странно, часто бывает полезно отсутствие алгоритма.
Например, есть такой известный вопрос о разложении чисел на множители. Если число небольшое, то легко проверить, что оно простое — можно проверить все меньшие числа, и понять, что там нет делителей. Если число большое, то так просто уже нельзя проверить — но существуют разные алгоритмы, которые позволяют это делать. (Они основаны на малой теореме Ферма и её усовершенствованиях, но это отдельная тема.)
Так или иначе, алгоритмы проверки простоты существуют. А теперь другая задача: возьмём два больших простых числа и их перемножим, сообщим, что у нас получилось, и спросим, какие это были числа. Это задача разложения на множители, и никто не знает, как это быстро сделать. И то, что этого никто не знает, очень хорошо, потому что благодаря этому существует вся вычислительная криптография, это одно из основных её предположений.
Когда кто-нибудь снимает деньги в банке, или в Интернете заходит на сайт с помощью SSL — используются системы криптографии, основанные на том, что быстро разлагать на множители числа нельзя. Если кто-нибудь в какой-то момент обнаружит, что разлагать можно, то, думаю, после этого будет экономический кризис, потому что вся банковская система рухнет, пока люди не заменят это чем-то другим (вообще без использования компьютеров или с какими-то новыми алгоритмами).
Так что отсутствие алгоритма может быть полезнее, чем его наличие. К сожалению, никто не может доказать, что алгоритма нет, хотя все подозревают, что это так — не решена ни общая проблема перебора, ни этот частный ее случай (разложение чисел на множители), особенно важный, и про него тоже все думают, но никто ничего не придумал.
Что такое случайность? Это дело тонкое, вообще, существует ли случайность? Когда в каком-нибудь казино играют в рулетку — может ли наука предсказать, что там выпадет, и как нужно играть, чтобы выиграть, или это в принципе невозможно?
Федор Михайлович Достоевский твердо верил, что если быть хладнокровным и не волноваться во время игры, то можно выиграть, — он говорил, что, к сожалению, ему не удаётся быть хладнокровным, и поэтому он всё время проигрывал.
С другой стороны, теория вероятностей основана на том, что такой системы не существует, что последовательность бросания монеты в какой-нибудь игре, или последовательность выпадения красного и черного в рулетке, случайны и непредсказуемы. Но возникает вопрос, что такое случайность? Как определить, что это значит? Можем ли мы отделить случайное от неслучайного?
Сейчас вы видите две последовательности:
Вам сказано, что одна из них получена бросанием монеты, а другая как-то иначе. Сможете ли вы определить, какая из них получена каким образом?
Я думаю, что сможете, и что более-менее всякий человек, который посмотрит на эту картинку, скажет, что первая последовательность получена не бросанием монеты, а просто чередованием 0 и 1, а вторая вполне может быть получена бросанием монеты.
Но спрашивается, в чём разница? Почему вы смотрите на эту картинку и уверены, что первая последовательность не может быть получена бросанием монеты? Почему монета не может выпасть сначала орлом, потом решкой, потом снова орлом… как это объяснить? Можно сказать так: вероятность того, что это случайно произойдет, очень мала, потому что такая последовательность всего одна, а всего последовательностей очень много. Но ведь то же самое можно сказать и про вторую последовательность, появление конкретно этой последовательности имеет ту же самую малую вероятность, что и для первой. Поэтому вопрос — в чём тут разница, чем первая последовательность «лучше» второй (менее случайна, чем вторая)?
Или другой парадоксальный пример. Представьте себе, как в XIX веке (это написано у Лотмана в его «Беседах о русской культуре») играли в карты. В отличие от нынешней ситуации, когда карты тасуют, тогда карты продавались уже перетасованными заранее.
Поэтому дворяне, которые играли в серьезные игры, каждый раз брали новую колоду и играли с ней. После этого она выбрасывалась и поступала, как пишет Лотман, в распоряжение слуг, которые играли в своего «подкидного дурака».
Так вот, представим себе, что есть фабрика, которая выпускает такие перетасованные колоды и есть машина, которая печатает карты, а есть, которая их тасует — эта машина их как-то внутри себя тасует, потом выкладывает, запаковывает, и они поступают в продажу. Теперь представим себе, что на этой фабрике есть, как говорили в советское время, «отдел технического контроля», который должен проверять, хорошо ли они перетасованы.
Время от времени он из пачки сделанных колод достаёт одну колоду, распаковывает и смотрит, хорошо ли она перетасована. С одной стороны, он должен что-то контролировать, то есть если он никогда никакие колоды не будет браковать как негодные, то зачем он вообще нужен? А с другой стороны, непонятно, что он может контролировать, потому что вся идея того, что карты хорошо перетасованы, состоит в том, что все варианты, все возможные последовательности карт в колоде, имеют совершенно одинаковую вероятность.
Соответственно, ни одна из них, с точки зрения тасовальной машины, не лучше другой. Почему же мы некоторые колоды (некоторые последовательности карт) бракуем, а некоторые оставляем? Это как-то загадочно.
Если, скажем, все карты идут в порядке возрастания их значения, или сначала идут все красные карты, а потом черные — такие комбинации, вроде бы, надо браковать. Но, с другой стороны, непонятно, чем они хуже других. Одной из попыток ответить на этот вопрос (60-е годы XX века) было понятие сложности, то, что сейчас называется колмогоровская сложность или алгоритмическая сложность.
Идея эта совсем простая — что первая из последовательностей
потому выглядит неслучайной, что она проста. «Проста» значит, что существует очень короткий способ объяснить, как она устроена — сказать, что там нули и единицы чередуются. В нашем примере такая разница, может, не сильно заметна — но если там будет тысяча чередующихся нулей и единиц, то ясно, что короче это объяснить словами, чем выписывать всю последовательность.
А для настоящей случайной монеты (как считается в рамках этого объяснения случайности) — никакого способа описать последовательность более коротким способом, чем показав просто все нули и единицы, как они есть, не существует.
Можно сказать, что, если мы начнем «сжимать» последовательности каким-то архиватором, то вторая последовательность не сожмётся, а первая сожмется.
В этом и состоит основная идея Колмогорова и его коллег, которые придумали, что сложность последовательности — это длина кратчайшей программы, которая такую последовательность может напечатать, а случайные последовательности отличаются от неслучайных тем, что нельзя их напечатать никакой программой, которая короче, чем сама последовательность.
Теперь целая наука на эту тему возникла, она называется алгоритмическая теория информации, алгоритмическая случайность, но, конечно, многие вопросы там еще не ясны. Не ясен вопрос о том, что можно сделать с ограничением на сложность вычислений.
Возможно, что последовательность на самом деле неслучайна и имеет какое-то короткое описание, но мы его просто не знаем и не можем найти — или проблема может быть не в том, что мы его не можем найти, а в том, что для того, чтобы восстановить последовательность по этому описанию, нужно очень много времени.
Вот это такая активно развивающаяся и, к сожалению, ещё не очень развитая область, и там, может быть, что-нибудь интересное в ближайшее время (или не в ближайшее время) откроют.
Если вы хотите получать больше статей, подобно этой, то кликните Recommend ниже.
Машина с конечным числом состояний
Машина с конечным числом состояний (finite state machine, FSM), или конечный автомат (finite automaton) — это математическая абстракция, используемая при проектировании алгоритмов. Говоря простым языком, машина с конечным числом состояний умеет считывать последовательности входных данных. Когда она считывает входной сигнал, то переключается в новое состояние. Куда именно переключится, получив данный сигнал, — заложено в её текущем состоянии. Звучит запутанно, но на самом деле всё очень просто.
Представим устройство, которое читает длинную бумажную ленту. На каждом дюйме этой ленты напечатана буква — a или b.
Как только устройство считывает букву, оно меняет своё состояние. Вот очень простой граф переходов для такой машины:
Кружки — это состояния, в которых машина может быть. Стрелочки — переходы между ними. Так что, если вы находитесь в состоянии s и считываете a, то вам необходимо перейти в состояние q. А если b, то просто остаётесь на месте.
Итак, если изначально мы находимся в состоянии s и начинаем читать ленту из первого рисунка слева направо, то сначала будет прочитана a, и мы переместимся в состояние q, затем b — вернёмся обратно в s. Следующая b оставит нас на месте, а a вновь переместит в q. Элементарно, но какой в этом смысл?
Оказывается, если пропустить ленту с буквами через FSM, то по её итоговому состоянию можно сделать некоторые выводы о последовательности букв. Для приведённго выше простого конечного автомата финальное состояние s означает, что лента закончилась буквой b. Если же мы закончили в состоянии q, то последней на ленте была буква a.
Это может показаться бессмысленным, но существует масса задач, которые можно решить с помощью такого подхода. Простейший пример: определить, содержит ли HTML-страница следующие теги в заданном порядке:
Машина с конечным числом состояний может перейти в новой состояние, считав , потом зациклиться до считывания , зациклиться до считывания и т.д. Если она успешно придёт к финальному состоянию, то заданные тэги стоят в правильном порядке.
Также конечный автомат может использоваться для представления механизмов парковочного счётчика, автомата с газировкой, автоматизированного газового насоса и тому подобных штук.
Машина Тьюринга
Алан Тьюринг хотел выполнить описание самой простой модели механического модуля, который обладал бы такими же базовыми возможностями, как и компьютер. Первое описание такой машины Тьюринг опубликовал в 1936-ом году в работе с названием «О вычислимых числах в приложении к проблеме разрешения», появившейся в работах Лондонского математического сообщества.
Машина Тьюринга была вычислительным модулем, который состоит из сканера для чтения и записи информации с бумажной ленты, пропускаемой через него. Лента поделена на квадратики, несущие один знак, а именно нуль или единицу. Механизм предназначен для ввода и вывода информации и одновременно служит рабочей памятью для сохранения итогов промежуточных вычислительных шагов. Машина имеет в своём составе два компонента:
- Лента без ограничений, то есть бесконечная в обоих направлениях лента, разделённая на комплект ячеек.
- Автоматический модуль, то есть головка сканера, которая считывает и записывает информацию под управлением программы. Она способна располагаться в любой момент времени лишь в одном из многих состояний.
Детерминированная машина с конечным числом состояний (Deterministic Finite State Machine)
Машины с конечным числом состояний, которые мы рассматривали выше, являются детерминированными. У них из любого состояния существует только один переход для любого разрешённого входного сигнала. Другими словами, не существует двух различных путей из данного состояния, когда вы считываете, допустим, букву a. На первый взгляд такое ограничение кажется глупым.
Что хорошего в наборе решений, если один и тот же сигнал на входе может переместить вас более, чем в одно состояние? Вы же не можете сказать компьютеру: если x == true , то выполни doSomethingBig() или doSomethingSmall(), не так ли?
Ну, вообще-то, с помощью машины с конечным числом состояний можно провернуть что-то в этом роде. Выход конечного автомата - его финальное состояние. Сначала он проведёт все вычисления, затем прочтёт последнее состояние, и только тогда совершится какое-то действие. А в процессе переходов от состояния к состоянию не будет делаться ровным счётом ничего. FSM обрабатывает поступившие данные, и только дойдя до конца и считав конечное состояние, совершает ожидаемое от неё действие (например, наливает газировку). Этот принцип особенно важен, когда дело доходит до недетерминированных машин с конечным числом состояний.
Функции машины Тьюринга
В составе алгоритма иногда необходимо реализовать некоторые функции. Функция может быть разрешимой алгоритмом или нет, что зависит от того, можно ли написать цепь вычислений. Множеством рациональных или натуральных чисел и слов в не бесконечном алфавитном наборе $N$ для устройства Тьюринга может быть рассмотрен набор множеств $B$, а именно слова в границах бинарного кодового алфавита $B = (0, 1)$. Кроме того, в итоге расчётов необходимо учесть «неопределённую» величину, возникающую при повисании выполнения алгоритма. Для осуществления функции требуется присутствие формализованного языка в не бесконечном алфавите и условие, что задача определения корректности описаний в принципе может быть решена.
Рисунок 1. Функции машины Тьюринга. Автор24 — интернет-биржа студенческих работ
Введение
Машина Тьюринга является одним из наиболее выдающихся научных изобретений двадцатого века. Она представляла несложную и удобную абстрактную модель вычислительного процесса, которая представлена в обобщённом формате и позволяет реализовать практически все компьютерные задачи. Простое описание и выполненный математический анализ позволяют считать её фундаментом теоретической информатики.
Эта научная работа послужила стимулом к более углублённому изучению цифрового исчисления и компьютерных устройств, в том числе осознание мысли, что есть проблематика в сфере вычислений, которую нельзя решить на обычных электронных вычислительных машинах пользователей
Почему это имеет значение?
Так какой во всём этом смысл? Как вышесказанное способно помочь вам при создании очередной PHP-формы? Несмотря на все их ограничения, машины с конечным числом состояний - одна из центральных концепций теории вычислений. В частности, тот факт, что из любого недетермированного конечного автомата, который вы можете спроектировать, возможно получить детерминированный конечный автомат, делающий то же самое. Это ключевой момент, потому что подразумевает, что вы можете спроектировать свой алгоритм, в котором каждый шаг будет наиболее очевидным. А уже имея надлежащий алгоритм, вы сможете легко конвертировать его в ту форму, в которой он будет наиболее эффективен.
Понимание, что машины с конечным числом состояний и регулярные выражения функционально эквивалентны, открывает невероятно интересные способы применения движков регэкспов. Особенно, когда дело доходит до создания бизнес-правил, которые могут быть изменены без перекомпиляции всей системы.
Знание основ теории вычислительных систем позволяет вам брать проблему X, которую вы понятия не имеете как решать, и применять к ней подход: "Я не знаю, как решить X, но я знаю, как решить Y и как привести решение для Y к решению для X. Вот почему теперь я знаю, как решить X".
Машина Тьюринга — это абстрактный исполнитель или абстрактная вычислительная машина.
Принцип работы машины Тьюринга
Машина Тьюринга принципиально отличается от компьютерных модулей, у неё в качестве запоминающего устройства выступает бесконечная лента, а у цифровых устройств память представляет полосу заданной длины. Любой тип заданий может решить лишь одна сформированная машина Тьюринга. Задания другого класса могут быть решены написанием другого алгоритма. Устройство управления находится в определённом состоянии и способно перемещаться в обе стороны вдоль ленты. Оно может записывать в ячейки и считывать из них алфавитные символы. При перемещении определяется пустой компонент, заполняющий места, которые не содержать входных данных. Алгоритм машины Тьюринга формирует условия перемещений управляющего механизма. Он может задать головке, выполняющей запись и чтение данных, следующие команды:
- Записать в текущую ячейку нужный знак.
- Выполнить смену текущего состояния.
- Переместиться в заданную сторону вдоль ленты.
Машина Тьюринга подобно другим системам, предназначенным для вычислений, обладает определёнными особенностями, которые похожи на свойства алгоритмов:
- Свойство дискретности. Цифровое устройство выполняет переход к очередному этапу n+1 лишь после полного завершения предыдущего. Каждый завершенный шаг определяет, каким будет следующий.
- Свойство понятности. Машина осуществляет лишь одну операцию для выбранной ячейки. Она записывает алфавитный символ и выполняет одно перемещение в указанную сторону.
- Свойство детерминированности. Всем позициям в машине сопоставляется только один вариант осуществления задаваемой схемы, и на всех шагах операции и их очерёдность осуществления строго определены.
- Свойство результативности. Окончательный итог на каждом шаге вычисляет машина Тьюринга. Программа работает согласно заданному алгоритму и за не бесконечное количество выполненных этапов доходит до состояния $q_0$.
- Свойство массовости. Каждой машине сопоставлен набор допустимых слов, которые входят в алфавит.
Для чего это нужно?
Тьюринг предложил эту модель для формализации понятия алгоритма . То есть считается, что задачу можно решить с помощью некоторого алгоритма тогда и только тогда, когда ее решение можно представить в виде программы для машины Тьюринга (эта гипотеза называется тезисом Чёрча — Тьюринга).
Так как устройство машины довольно простое, то, очевидно, что каждый шаг в такой программе должен быть элементарен.
Как записать простейшую программу?
Рассмотрим очень простую задачу. Пусть у нас есть последовательность из 0 и 1, и мы хотим в ней заменить все символы 0 на @. Как может выглядеть программа для машины Тьюринга в этом случае?
Программа задается набором правил , которые еще называют правилами перехода. Для записи этих правил нет какого-то единого языка, поэтому в нашей статье запишем их в виде таблицы.
Итак, в качестве входных данных у нас есть последовательность символов 0 и 1 , и мы будем называть ее входным словом . Для простоты мы будем считать, что управляющее устройство указывает на первый слева символ нашего слова (если управляющее устройство указывает на произвольный символ слова, то эта проблема легко решается, но сейчас пропустим этот момент).
В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» — абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом — учёным, которого считают одним из основоположников информатики.
Его кругозор распространялся от квантовой теории и принципа относительности до психологии и неврологии. А в качестве способа познания и передачи своих знаний Тьюринг использовал аппарат математики и логики. Он находил решения, казалось бы, нерешаемых задач, но был сильнее всего увлечен идеей «Универсальной машины», способной вычислить всё, что в принципе вычислимо.
Детство, образование, увлечения
Родители Алана жили в индийском городе Чхатрапур. Отец — Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Имперской государственной службе. Мать — Сара Этель (урожденная Стони), была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне.
Там Алан Тьюринг и родился 23 июня 1912 года. У него был старший брат Джон. Государственная служба Юлиуса Тьюринга продолжалась и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары. Признаки гениальности проявлялись у Тьюринга с раннего детства.
В детстве Алан и его старший брат Джон довольно редко видели своих родителей — их отец до 1926 года служил в Индии; дети оставались в Англии и жили на попечении в частных домах, получая строгое английское воспитание, соответствующее их положению на социальной лестнице. В рамках такого воспитания изучение основ естественных наук фактически не предусматривалось.
Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте 6 лет, он просил у своих воспитателей разрешения читать научно-популярные книги.
В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но её опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School).
В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 км от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.
Увлечение Тьюринга математикой не нашло особой поддержки среди учителей Шерборнской школы, где уделяли больше внимания гуманитарным наукам. Директор школы писал родителям: «Я надеюсь, что он не будет пытаться усидеть на двух стульях разом. Если он намеревается остаться в частной школе, то он должен стремиться к получению «образования». Если же он собирается быть исключительно «научным специалистом», то частная школа для него — пустая трата времени».
О школьных успехах Алана красноречиво свидетельствует классный журнал, в котором можно найти, например, следующее
Я могу смотреть сквозь пальцы на его сочинения, хотя ничего ужаснее в жизни своей не видывал, я пытаюсь терпеть его непоколебимую небрежность и непристойное прилежание; но вынести потрясающую глупость его высказываний во время вполне здравой дискуссии по Новому Завету я, все же, не могу.
Тем не менее, в областях, интересовавших его, Тьюринг проявлял незаурядные способности.
В 1928 году, в возрасте 16 лет, Тьюринг ознакомился с работой Эйнштейна, в которой ему удалось разобраться до такой степени, что он смог догадаться из текста о сомнениях Эйнштейна относительно выполнимости Законов Ньютона, которые не были высказаны в статье в явном виде.
Университет
Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.
Кембриджский университет, обладавший особыми привилегиями, дарованными английскими монархами, издавна славился либеральными традициями, и в его стенах всегда царил дух свободомыслия. Здесь Тьюринг обретает – пожалуй, впервые – свой настоящий дом, где он смог полностью отдаться науке.
Главное место в жизни заняло увлечённое изучение столь интересующих его наук – математики и квантовой физики. Те годы были периодом бурного становления квантовой физики, и Тьюринг в студенческие годы знакомится с самыми последними работами в этой области. Большое впечатление производит на него книга Джона фон Неймана «Математические основы квантовой механики», в которой он находит ответы на многие давно интересующие его вопросы.
Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне – одном из самых известных университетов США. Ещё позже фон Нейман, так же как и Тьюринг, будет назван «отцом информатики». Но тогда, в начале 30-х годов ХХ века, научные интересы обоих будущих выдающихся учёных были далеки от вычислительных машин – и Тьюринг, и фон Нейман занимаются в основном задачами «чистой» математики.
Тьюринг происходил из аристократической семьи, но никогда не был «эстетом»: кембриджские политические и литературные кружки были чужды ему. Он предпочитал заниматься своей любимой математикой, а в свободное время ставить химические опыты, решать шахматные головоломки.
Ставя химические опыты, он играл в особую игру «Необитаемый остров», изобретенную им самим. Цель игры заключалась в том, чтобы получать различные «полезные» химические вещества из «подручных средств» – стирального порошка, средства для мытья посуды, чернил и тому подобной «домашней химии».
Он также находил отдых в интенсивных занятиях спортом – греблей и бегом. Марафонский бег останется его поистине страстным увлечением до конца жизни.
Тьюринг блестяще заканчивает четырёхлетний курс обучения. Одна из его работ, посвященная теории вероятностей, удостаивается специальной премии, его избирают в научное общество Королевского колледжа. В 1935 году Тьюринг публикует работу «Эквивалентность левой и правой почти-периодичности», в которой он упрощает одну идею фон Неймана в теории непрерывных групп – фундаментальной области современной математики. Казалось, его ждет успешная карьера слегка эксцентричного кембриджского преподавателя, работающего в области «чистой» математики.
Однако Тьюринг никогда не удерживался в каких-либо «рамках». Никто не мог предвидеть, какая экзотическая проблема неожиданно увлечет его, и какой математически неординарный способ ее решения ему удастся придумать.
Кроме того, в Кембридже Алан посещал лекции Виттенштейна Людвига. Виттенштейн утверждал теорию о несостоятельности математики. По его словам математика не ищет истину, но сама создаёт её. Алан был с этим не согласен и много спорил с Людвигом. Тьюринг выступал за «формализм» — математическое философское течение, которое не требовало точного перевода слов и ограничивалось примерным смыслом. А Людвиг искал абсолютной точности.
Во время обучения в колледже Алан Тьюринг изучал основы криптографии – то есть расшифровки данных. Это пригодилось ему во время Второй Мировой войны, когда учёный работал над расшифровкой немецких посланий.
Машина Тьюринга
В 1928 году немецкий математик Давид Гильберт привлек внимание мировой общественности к проблеме разрешения (Entscheidungsproblem). В своей работе «On Computable Numbers, with an Application to the Entscheidungsproblem», опубликованной 12 ноября 1936 года. Тьюринг переформулировал теорему Гёделя о неполноте, заменив универсальный формальный арифметический язык Гёделя на простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга.
Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сперва доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.
Хотя доказательство Тьюринга было обнародовано в скором времени после эквивалентного доказательства Алонзо Чёрча, в котором использовались Лямбда-исчисления, сам Тьюринг был с ним не знаком. Подход Алана Тьюринга принято считать более доступным и интуитивным. Идея «Универсальной Машины», способной выполнять функции любой другой машины, или другими словами, вычислить всё, что можно, в принципе, вычислить, была крайне оригинальной. Фон Нейман признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Машины Тьюринга по-прежнему являются основным объектом исследования теории алгоритмов.
На вопрос: «Что такое машина Тьюринга и какое отношение она имеет к программированию?» один из пользователей Toster ответил так:
В общем, МТ — способ определить некоторый класс алгоритмов:
— некоторые задачи можно решить конечным автоматом;
— для некоторых потребуется конечный автомат со стековой памятью;
— для других достаточно машины Тьюринга;
— для остальных требуется божественное откровение или другие неалгоритмизируемые методы.
С сентября 1936 года по июль 1938 Тьюринг работал под руководством Чёрча в Принстоне. Кроме занятий математикой, учёный изучал криптографию, а также конструировал электромеханический бинарный умножитель.
В июне 1938 года Тьюринг защитил докторскую диссертацию «Логические системы, основанные на ординалах», в которой была представлена идея сведения по Тьюрингу, заключающаяся в объединении машины Тьюринга с оракулом. Это позволяет исследовать проблемы, которые невозможно решить с помощью лишь машины Тьюринга.
Криптоанализ
Во время Второй мировой войны Алан Тьюринг принимал активное участие во взломе немецких шифров в Блетчли-парке. Историк и ветеран Блетчли-парка Эйза Бригс однажды сказал:
«Блетчли-парку был нужен исключительный талант, исключительная гениальность, и гениальность Тьюринга была именно такой».
Польский метод основывался на недоработках индикаторной процедуры, которые немцы исправили к маю 1940 года. Подход Тьюринга был более общим и основан на методе перебора последовательностей исходного текста, для которого он разработал начальную функциональную спецификацию Bombe.
Далее машина определяла противоречие, отбрасывала набор параметров и переходила к следующему. Таким образом, бо́льшая часть возможных наборов отсеивалась и для тщательного анализа оставалось всего несколько вариантов.
Первая машина была запущена в эксплуатацию 18 марта 1940 года. Перебор ключей выполнялся за счёт вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов.
Спецификация для «Бомбы» была только первым из пяти важнейших достижений Тьюринга в области военного криптоанализа.
Учёный также определил индикаторную процедуру ВМФ Германии; разработал более эффективный способ использования Bombe, основанный на статистическом анализе и названный «Банбурисмусом»; метод определения параметров колёс машины Лоренца, названный «Тьюринжерией»; ближе к концу войны Тьюринг разработал портативный шифратор речи Delilah.
Статистический подход к оптимизации исследований различных вероятностей в процессе разгадывания шифров, который использовал Тьюринг, был новым словом в науке. Тьюринг написал две работы: «Доклад о применимости вероятностного подхода в криптоанализе» и «Документ о статистике и повторениях», которые представляли для GCCS, а позже и для GCHQ (англ. Government Communications Headquarters) такую ценность, что не были предоставлены национальному архиву вплоть до апреля 2012 года, незадолго до празднования ста лет со дня рождения учёного. Один из сотрудников GCHQ заявил, что этот факт говорит о беспрецедентной важности этих работ.
Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 года по март 1943 года в США.
В 1945 году Тьюринг был награждён орденом Британской империи королём Георгом VI за свою военную службу, но этот факт оставался в секрете многие годы.
Послевоенные годы
После того как фон Нейман в США предложил план создания компьютера EDVAC, аналогичные работы были развернуты в Великобритании в Национальной физической лаборатории, где Тьюринг проработал с 1945 года. Ученый предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), который, однако, так и не был реализован.
Несмотря на то, что постройка ACE была вполне осуществима, секретность, окружавшая Блэтчли-парк, привела к задержкам в начале работ, что разочаровало Тьюринга.
1947–1948 академический год Тьюринг провел в Кембридже. Пока Алан Тьюринг пребывал в Кембридже, Pilot ACE был построен в его отсутствие.
Franklin ACE 1200
Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру, DEUCE и Bendix G-15.
В мае 1948 года получил предложение занять пост преподавателя и заместителя директора вычислительной лаборатории Манчестерского университета, занявшего к этому времени лидирующие позиции в разработке вычислительной техники в Великобритании.
В 1948 году Алан совместно со своим бывшим коллегой начал писать шахматную программу для компьютера, который ещё не существовал.
В том же году Тьюринг изобрёл метод LU-разложения, который используется для решения систем линейных уравнений, обращения матриц и вычисления определителя.
Тест Тьюринга
В 1948 году Алан Тьюринг получил звание Reader в математическом департаменте Манчестерского университета. Там в 1949 году он стал директором компьютерной лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I.
В то же время Тьюринг продолжал работать над более абстрактными математическими задачами, а в своей работе «Computing Machinery and Intelligence» (журнал «Mind», октябрь 1950) он обратился к проблеме искусственного интеллекта и предложил эксперимент, ставший впоследствии известным как тест Тьюринга.
Его идея заключалась в том, что можно считать, что компьютер «мыслит», если человек, взаимодействующий с ним, не сможет в процессе общения отличить компьютер от другого человека. В этой работе Тьюринг предположил, что вместо того, чтобы пытаться создать программу, симулирующую разум взрослого человека, намного проще было бы начать с разума ребёнка, а затем обучать его. CAPTCHA, основанный на обратном тесте Тьюринга, широко распространён в интернете.
В 1951 году Тьюринг был избран членом Лондонского королевского общества.
В первоначальной формулировке «тест Тьюринга» предполагает ситуацию, в которой два человека, мужчина и женщина, по некоторому каналу, исключающему восприятие голоса, общаются с отделенным от них стеной третьим человеком, который пытается по косвенным вопросам определить пол каждого из своих собеседников; при этом мужчина пытается сбить с толку спрашивающего, а женщина помогает спрашивающему выяснить истину.
Вопрос при этом заключается в том, сможет ли в этой «имитационной игре» вместо мужчины столь же успешно участвовать машина (будет ли при этом спрашивающий ошибаться в своих выводах столь же часто). Впоследствии получила распространение упрощённая форма теста, в которой выясняется, может ли человек, общаясь в аналогичной ситуации с неким собеседником, определить, общается он с другим человеком или же с искусственным устройством.
Данный мысленный эксперимент имел ряд принципиальных следствий. Во-первых, он предложил некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?».
Следствием этого стала та важнейшая роль, которую в дальнейшем развитии искусственного интеллекта, во всяком случае, до 1980-х годов играли исследования по моделированию понимания и производства естественного языка. В 1977 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.
Память
• именем ученого назван один из астероидов;
• ежегодная награда Ассоциации вычислительной техники называется Премией Тьюринга;
• на главной площади университета Суррея (Англия) есть статуя Тьюринга и одно из зданий факультета инженерных и физических наук названо в его честь;
• одна из аудиторий отдела информатики при Университете Лилль в Северной Франции назван в честь Алана М. Тьюринга;
• Манчестерский университет, Открытый университет, Университет Оксфорд Брукс и Университет Орхус (Дания) имеют корпуса имени Тьюринга и другие;
Теория вычислительных систем — это то, что позволяет нам программировать. Однако, можно писать программы и без представления о концепциях, скрывающихся за вычислительными процессами. Не то, чтобы это было плохо — когда мы программируем, то работаем на намного более высоком уровне абстракции. В конце концов, когда мы ведём машину, то концентрируемся только на двух или трёх педалях, переключателе передач и руле. Для повседневной неспешной езды этого более чем достаточно. Однако, если мы хотим управлять автомобилем на пределе его возможностей, то тут нужно знать гораздо больше, чем просто три педали, КПП и руль.
Такой подход справедлив и в программировании. Большая часть повседневной мирской работы может быть выполнена при минимальном знании теории вычислительных систем или даже вообще без него. Не нужно понимать теорию категорий, чтобы накидать форму «Контакты» в PHP. Тем не менее, если вы планируете писать код, требующий серьёзных вычислений, то тут уж придётся разобраться с тем, что у этих самых вычислений под капотом.
Цель этой статьи — представить некоторые фундаментальные основы вычислений. Если это окажется интересным, то в дальнейшем я могу написать более продвинутый топик на эту тему, но прямо сейчас я хочу просто рассмотреть логику простейшего абстрактного вычислительного устройства — машины с конечным числом состояний (finite state machine).
Готовые работы на аналогичную тему
Машина осуществляет связь двух конечных рядов информационных данных, а именно алфавит знаков на входе $A = (a_0, a_1, …, a_m)$ и алфавит состояний $Q = (q_0, q_1, . q_p)$. Пассивным считается состояние $q_0$. Предполагается, что машина прекращает выполнение операций, когда считывает именно его. Исходным состоянием является состояние $q_1$, и устройство запускается в работу, когда считывает это стартовое состояние. Слово на ленте, которое является входной информацией, расположено последовательно по одной букве в позиции. При этом, впереди него и за ним расположены нулевые квадраты.
Читайте также: